Saturday 20 October 2012

Data Structure


Miss.Rohini A. Shinde Notes



Introduction To Data Structure

Introduction to data structure
Introduction:
Data structures are used in almost every program or software system. Specific data structures are essential ingredients of many efficient algorithms, and make possible the management of huge amounts of data, such as large databases and internet indexing services. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design.

Data:
 Data are simply values or set of values.
A data item refers to a single unit of values.
 Data item that are divided into sub items are called group items; those which are not are called elementary items. Computer science is concerned with study of data which involves
Machine that hold the data.
Technologies used for processing data.
Methods for obtaining information from data.
Structure for representing data.
Data are simply values or sets of values.A data item refers to a single unit of values.Data items that are devided into subitems are called as GROUP tem.
Data items which  are not devided into subitems are called as ELEMENTARY item.
For example:
Name of students can be devided into three subitems are first name,middle name and last name.So name is a GROUP item.
The Pin code can not be devided into subitems therefore is called as Elementary items.
Information:
Raw data is of little value in its present form unless it is organized into a meaningful format. If we organize data or process data so that it reflect some meaning then this meaningful or processed data is called information.

Data type:
 Data type is a term used to describe information type that can be processed by a computer system and which is supported by a programming language. More formally we define the data type as “ a term which refers to the kind of data that a variable may take in “. Several different types of data can be processed by a computer system e.g. Numeric data, text data, video data, audio data, spatial data etc. A brief classification of data types is as shown in fig.

Data type
Built in or primary       User defined                  Derived     
int,                                 Enumeration,                 Array                  
real,                                union                            Function
char,                               structure                        Pointer
Boolean                         class
void,
pointer

Data Structure: Data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. When we define a data structure we are in fact creating a new data type of our own i.e. using predefined types or previously user defined types. The basic types of data structure includes : files, lists, arrays, trees etc. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. The choice of a particular data structure for an application depends upon two factors:
1. Structure must reflect the actual relationship of the data in the real world.
2. The structure should be simple enough so that one can efficiently process the data when necessary.

Classification of Data Structure: Data structures are normally classified into two categories:
1. Primitive Data Structure: Primitive data structure are native to machine‟s hardware. Some primitive data structure are
·        Integer
·        Character
·        Real Number
·        Logical Number
·        Pointer

2. Non-primitive Data Structure: These type of data structure are derived from the primitive data structures. Some non primitive data structures are
·        Array
·        List
·        Files
·        Tree
·        Graph

Entity: An entity is something that has certain attributes or properties which may be assign values,The values can be numeric or non numeric.
For example: Employee of an organization is an entity.
The attributes associated with this entity are employee number,name age, sex address,etc.
Every attributes has certain value.The collection of all entities form an entity set.All the employees in an organization forms entity set.
The term Information is also used for data with given attributes.Information means meaningful data.
Field is single elementary unit of information reprenting an attribute of entity.
For example:
Name,age,sex are all fields.
Record: A record is s collection of fields values of a given entity. i.e.one record for one employee.
File: A fileis s collection of records of entities . i.e.collection of  records of all employesss form a file.
A record in a file may contain several fields.There are certain fields having unique value.Such a field is primary key.For example employee no is a primary key.
A file can have fixed length record or variable length record.
fixed length record: In fixed length record all record contain the same data item with same amount of space assigned to each data item.
variable length record: In variable length record, file records may contain different lengths.
Apart from fields,records and files, the data can also be organized into more complex types of structures.Data can be organsed into different ways.The logical mathematical model of a particular organization is called a Data Structure.The model should be reflect the actual relationship of data in real world and it should be simple enough so that data can be processed whenever required.Some of the data structures are arrays,linked lists,trees,queue & graph.
An array is a list of finite no of elements.For example an array of names or an array of marks.
Linked list is a list of elements associated with a link to elements of other list.
Tree represents hierarchical relationship between various elements.
Queue is first in first out linear list where deletion can take place only at one end.
Graph represents relationship between pairs of elements.

Data Structure Operations:
Following are operations can be performed on a data structure.
1.     Traversing: Traversing means accessing each record(element) only once so that it can be processed.
2.     Searching: Searching means finding the location of recors(element) with given key value or finding all records that satisfies condition.
3.     Inserting: Inserting means adding new record(element) to the structure.
4.     Deleting: Deleting means removing the record(element) from the structure.
5.     Sorting: Sorting means arranging the records(elements) in some logical order. For example: arranging names in alphabetical order.
6.     Merging: Merging means combining the records in two different files into a single file.

Algorithms:
 Definition:
 Algorithm is finite set of instructions that can be followed to find a solution for given problem. An algorithm must have following characteristics
1. Input: An algorithm must accept input if supplied externally.
2. Output: An algorithm must give at least one output after processing input data.
3. Definiteness: Each instruction in algorithm must be lucid and unambiguous.
4. Effectiveness: Each instruction in an algorithm must be practicable. Any person either expert or novice user must be able to perform the operation with only pencil and paper. 
5. Finiteness: Algorithm must terminate after a finite number of steps.
An algorithm is a finite step-by-step list of well defined instructions for solving a particular problem.
We will needed to write an algorithm to different data structure operations.
In first part of algorithm we tell the purpose of algorithm,it list for variable & input data.
The second part is list of steps.
The steps in algorithm is executed one after other. 
Control goes transfer to statement n,by using the statement like “Go to step n”.
The exit & stop statements completes the algorithm.The data may be assigned to variable by using read statement & it is displayed by write or print statement.
For example:


Algorithm 1         :               Purpose of algorithm and input data and variables used.
Step 1                   :               ……………………………………..
Step 2                   :               ……………………………………..
                                :
                                :
Step n                   :               ……………………………………..

Control Structures:
There are three types of flow of control(or logic):
1.     Sequential flow(Sequential flow)
2.     Conditional flow(selection logic)
3.     Repetitive flow(Iteration logic)

1.Sequential flow
Algorithms consists of modules.Each module is a set of steps.In sequential flow the module. Are executed one after the other.
Module A
Module B
Module C
:
:
2.Conditional Flow:
In conditional flow, one or other module is selected depending on condition. There are three conditional structure-
1.     Single alternative:
This has the General form-
If condition, then:
[Module A]
[End of if structure]


Explanation:It is a selection statement, we have to choice a single alternative like if statement. If condition is true then it will execute respective module.

1.     Double alternative:
This has the General form-
If condition, then:
[Module A]
ELSE:
[Module B]
[End of if structure]

1.     Multiple alternative:

This has the general form-                                 
If condition(1),then:
[Module A1]
ELSE if(condition2) then:
[Module A2]
:
ELSE if(condition M)then:
[Module AM]
ELSE:
[Module B]
[End of if structure]

Explanation:
In Multiple alternative, first check the condition1,if condition1 is true then it execute first module (moduleA1) otherwise it check condition2.If condition2 is true then it execute second module(module A2). this procedure will continue till last condition(Condition M). If all conditions are failed then it execute else part, i.e. Module B.
-The logic of this structure allows only one module to be executed.



Explanation:
In repeat for loop first set the initial value, then check the condition. If condition is true then it will     execute respective Module(body of loop) then increment or decrement the value of variable. Again it check the condition, code inside the for loop is executed till condition is getting satisfied.






3. Repititive Flow:
Here certain moule is executed repetedly unity condition satisfies.
The repeat for loop has the form:
Repeat for k=R to S by T
[Module]
[End of loop]
          Here k is index variable, Initial value of K is R and final value is S.T. is increment.





Repeat While is another repetitive flow. It has form:
Repeat While Condition:
[Module]
[End of Loop]
Here looping continuous until condition is false.


Explanation:
In while loop first check the condition,if condition is true then it execute the body of loop or Module.Again it check the condition. Again condition is true then it execute Module. This procedure will continue upto condition becomes false.
If condition becomes false it does not execute Module

EXERSIZE:
Write an algorithm to find roots of quadratic equation
Ax2+bx+c=0
Where a≠0 and roots are given by,
X=-b±√b2-4ac∕2a
Solution:
Algorithm—
This algorithm inputs coefficients A,B,C of a quadratic equation & find real roots,if any.
Step1: Read:A,B,C
Step2: Set D= b2-4ac
Step3: if D>0 then
a)     Set X1=(-B+√D)/2A and
Set X2=(-B-√D)/2A
b)    Write:’Unique solution’,X
ELSE
Write:’No real roots’
[End of IF structure]
Step 4: EXIT

Arrays:
A linear array is a list of a finite number n of homogeneous data elements (i.e., data
elements of the same type) such that:
(a) The elements of the array are referenced respectively by an index set consisting of n consecutive numbers.
(b) The elements of the array are stored respectively in successive memory locations.
We will analyze this for Linear Arrays.
The number n of elements is called the length or size of the array. If not explicitly stated,
we may assume the index set consists of the integers 1, 2, 3, ….., n.
The general equation to find the length or the number of data elements of the array is,
Length = UB – LB + 1 (1.4a)
where, UB is the largest index, called the upper bound, and LB is the smallest index,
called the lower bound of the array. Remember that length=UB when LB=1.
Also, remember that the elements of an array A may be denoted by the subscript notation,
A1, A2, A3……..An
Let us consider the following example (a),


The following figures (a) and (b) depict the array DATA.
247
56
429
135
 87
156
Figure (a)

247
56
429
135
87
156
Figure (b)


Length = UB – LB + 1
Here UB=5 & LB=0,
Length = 5 –0 + 1 =6

REPRESENTATION OF LINEAR ARRAYS IN MEMORY
Consider LA be a linear array in the memory of the computer. As we know that the
memory of the computer is simply a sequence of addressed location as pictured in
figure as given below.
1000          

1001

1002

1003

1004
1005

.

.
.
.
.
.
.
.
.
.

                                   Figure: Computer Memory

TRAVERSING LINEAR ARRAYS

Consider let A be a collection of data elements stored in the memory of the computer.
Suppose we want to either print the contents of each element of A or to count the number of elements of A with a given property. This can be accomplished by traversing A, that is, by accessing and processing (frequently called visiting) each element of A exactly once.
The following algorithm is used to traversing a linear array LA.
As we know already, here, LA is a linear array with lower bound LB and upper bound
UB. This algorithm traverses LA applying an operation PROCESS to each element of
LA.
1. [Initialize counter] Set K:= LB.
2. Repeat Steps 3 and 4 while K≤UB
3. [Visit element] Apply PROCESS to LA[K]
4. [Increase counter] Set K:= K + 1
[End of Step 2 loop]
5. Exit.

INSERTING AND DELETING
Let A be a collection of data elements in the memory of the computer. “Inserting” refers to the operation of adding another element to the collection A, and “deleting” refers to the operation of removing one of the elements from A. Let we discuss the inserting and deleting an element when A is a linear array.
Inserting an element at the “end” of a linear array can be easily done provided the
memory space allocated for the array is large enough to accommodate the additional
element. On the other hand, suppose we need to insert an element in the middle of the array. Then, on the average, half of the elements must be moved downward to new locations to accommodate the new element and keep the order of the other elements.
Similarly, deleing an element at the “end” of an array presents no difficulties, but deleting an element somewhere in the middle of the array would require that each subsequent element be moved one location upward in order to “fill up” the array.

Consider the other example

Suppose NAME is an 8-element linear array, and suppose five names are in the array, as in Figure (a). Observe that the names are listed alphabetically, and suppose we want to keep the array names alphabetical at all times. If, Ford is adding to the array, then,
Johnson, Smith and Wagoner must each be move downward one location, as given in Figure (b). Next if we add Taylor to this array; then Wagner must be move, as in Figure (c). Last, when we remove Davis from the array, then, the five names Ford, Johnson, Smith, Taylor and Wagner must each be move upward one location, as in Figure (d). We may observe, clearly that such movement of data would be very expensive if thousands of names are in the array

TRAVERSING LINEAR ARRAYS

Consider let A be a collection of data elements stored in the memory of the computer.
Suppose we want to either print the contents of each element of A or to count the number of elements of A with a given property. This can be accomplished by traversing A, that is, by accessing and processing (frequently called visiting) each element of A exactly once.
The following algorithm is used to traversing a linear array LA.
As we know already, here, LA is a linear array with lower bound LB and upper bound
UB. This algorithm traverses LA applying an operation PROCESS to each element of
LA.
1. [Initialize counter] Set K:= LB.
2. Repeat Steps 3 and 4 while K≤UB
3. [Visit element] Apply PROCESS to LA[K]
4. [Increase counter] Set K:= K + 1
[End of Step 2 loop]
5. Exit.

INSERTING AND DELETING
Let A be a collection of data elements in the memory of the computer. “Inserting” refers to the operation of adding another element to the collection A, and “deleting” refers to the operation of removing one of the elements from A. Let we discuss the inserting and deleting an element when A is a linear array.
Inserting an element at the “end” of a linear array can be easily done provided the
memory space allocated for the array is large enough to accommodate the additional
element. On the other hand, suppose we need to insert an element in the middle of the array. Then, on the average, half of the elements must be moved downward to new locations to accommodate the new element and keep the order of the other elements.
Similarly, deleing an element at the “end” of an array presents no difficulties, but deleting an element somewhere in the middle of the array would require that each subsequent element be moved one location upward in order to “fill up” the array.

Consider the other example

Suppose NAME is an 8-element linear array, and suppose five names are in the array, as in Figure (a). Observe that the names are listed alphabetically, and suppose we want to keep the array names alphabetical at all times. If, Ford is adding to the array, then,
Johnson, Smith and Wagoner must each be move downward one location, as given in Figure (b). Next if we add Taylor to this array; then Wagner must be move, as in Figure (c). Last, when we remove Davis from the array, then, the five names Ford, Johnson, Smith, Taylor and Wagner must each be move upward one location, as in Figure (d). We may observe, clearly that such movement of data would be very expensive if thousands of names are in the array

ALGORITHM FOR INSERTING:

The following algorithm inserts a data element ITEM into the Kth position in a linear
array LA with N elements i.e. INSERT(LA,N,K,ITEM).
Here LA is a linear array with N elements and K is a positive integer such that K<N.
This algorithm inserts an element ITEM into the Kth position in LA.

ALGORITHM FOR DELETING:
The following algorithm deletes the Kth element from a linear array LA and assigns it to
a variable ITEM i.e. DELETE{LA.N,K,ITEM).
Here LA is a linear array with N elements and K is a positive integer such that K<N.
This algorithm deletes the Kth element from LA.

Sorting:
Sorting means rearranging elements of array in increasing order,i.e.
A[0]<A[1] <A[2]………………. <A[n]
Where A is array name.
For example,suppose A originally is the list
8,4,19,2,7,13,5,16
After sorting A is the list
2,4,5,7,8,13,16,19

In sorting we may rearrange the data in decreasing also.There are many sorting techniques,here we discuss the simple sorting technique,Bubble sort.
Suppose the list of numbers, A[0]<A[1] <A[2]………………. <A[n]
In memory.

ALGORITHM FOR BUBBLE SORT:

Step1:                   Compare A[1] and A[2] and arrange them in desired order,so that A[1]<A[2].Then compare A[2] A[2] and A[3] and arrange them so that A[2]<A[3].
Continue this process until we compareA[n-1]<A[N].
Step 1 involves n-1 comparisons.During this step,the largest element is coming like a bubble to the nth position.When step 1 is completed,A[N} will be the largest element.
Step 2:        Repeat step 1 with one less comparision. Step 2 involves N-2 comparision,when step 2 is completed we get second element A[N-2}.
Step 3:        Repeat step 1 with one less comparision. Step 3 involves N-3 comparision,
Step N-1:    Compare A[1] and A[2] and arrange them so that A[1]<A[2].
After N-1 steps,the list will be sorted in increasing order.Each step is called as ‘pass’.So that bubble sort has n-1 passes.

Algorithm: (BUBBLE SORT) BUBBLE (DATA, N)
Here DATA is an array with N elements. This algorithm sorts the elements in DATA.
1. Repeat step 2 and 3 for K=1 to N-1
2. Set PTR :=1 [Initializes pass pointer PTR]
3. Repeat while PTR <= N-K [Executes pass]
a. If DATA [PTR]> DATA [PTR+1], then:
Interchange DATA [PTR] and DATA [PTR+1].
[End of if structure].
b. Set PTR: = PTR+1.
[End of inner loop].
4. EXIT.

Searching

Many times we need to find a record with the help of key. Key is the unique value associated with each record which distinguishes records from each other. Searching is operation that finds the given key value in the list of elements. Searching algorithm accepts two arguments the key and list in which key is to be found. There are two standard algorithm for searching – Linear Search and Binary search. Linear Searching This is the simplest method for searching a element into the list of elements. We start from the beginning of the list and search the element by examining each consequetive element in the list until the element found in the list or the list is finished. Algorithm
1. Read N elements into an array A. 
2. Read the element to be searched into KEY.
3. Repeat step 4 for I=0 to N-1 by 1.
4. IF A[I] = KEY THEN PRINT “Element found”.
5. IF element is not in the list PRINT “Element not found”.

Algorithm:  (Linear Search) LINEAR (DATA, N, ITEM, LOC)
Here DATA is linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in DATA, or sets LOC: = 0 if search is unsuccessful.
1. [Insert ITEM at the end of DATA] Set DATA [N+1]:= ITEM
2. [Initialize counter] Set LOC: =1.
3. [Search for ITEM]
Repeat while DATA [LOC]! = ITEM
Set LOC: = LOC+1.
[End of loop].
4. [Successful?] If LOC= N+1, then Set LOC: =0.
5. EXIT

Binary Search:
Binary Search: Suppose DATA is an array which is stored in increasing numerical order or alphabetically. Then there is an extremely efficient searching algorithm called binary search, which can be used to find the location LOC of a given ITEM of information in DATA.
The Binary Search algorithm applied to our array DATA works as follows. During each stage of our algorithm, our search of ITEM is reduced to a segment of element of DATA:
DATA [BEG], DATA [BEG+1], DATA [BEG+2], …… DATA [END]
Note that the variables BEG and END denote, respectively, the beginning and end location of the segment under consideration. The algorithm compares ITEM with the middle element DATA [MID] of the segment, where MID is obtained by
MID = INT ((BEG + END)/2)
If DATA [MID] =ITEM, then the search is successful and we set LOC:= MID. Otherwise a new segment of DATA is obtained as follows:
a)     If ITEM < DATA[MID], then ITEM can appear only in the left half of the segment:
DATA [BEG], DATA [BEG+1], …. DATA [MID-1]
So we reset END: = MID-1 and begin search again.
b)    If ITEM > DATA[MID], then ITEM can appear only in the right half of the segment:
DATA [MID+1], DATA [MID+2], … DATA[END]
So we reset BEG: = MID +1 and begin search again.
Algorithm: (Binary Search) BINARY (DATA, LB, UB, ITEM, LOC)
Here DATA is stored array with lower bound LU and upper bound UB, and ITEM is given item of                 information. The variables BEG, END and MID denote, respectively, the beginning end and       middle location of the segment of an element of DATA. This algorithm finds the location LOC of   ITEM in DATA or set LOC= NULL.
1. [Initialize segment variable]
Set BEG: = LB, END: = UB and MID: = INT ((BEG+END)/2).
2. Repeat Step 3 and 4 while BEG<= END and DATA [MID]!= ITEM.
3. If ITEM < DATA[MID], then
Set END: = MID-1
ELSE:
Set BEG: = MID+1.
[End of if structure]
4. Set MID: =INT((BIG+END)/2)
[End of Step 2 loop]
5. If DATA[MID]= ITEM then
Set LOC: = MID
ELSE:
Set LOC: = NULL.
[End of if structure]
6. EXIT.

Pointer Arrays:
A variable is called pointer if it points to an element in list.The pointer variable contains the address of an element in the list.
An array is called pointer array if each element of array is a pointer.The use of pointer array can be stored in memory.The most efficient method is to form two arrays.One is member consisting of list of all members one after the other and another pointer array group containing the starting locations of different groups.
It is shown in fig.


Records:
Record is a collection of fields.A record may contain non homogeneous data,i.e.data item in a record may have different data types.In records,the natural ordering of element is not possible.
          The element in records can be described by level numbers.For example,A hospital keeps a record of new born baby.It contains following data items:Name,Sex,Birthday,Father,Mother.
Birthday is a group item consisting month,day,year,
Father & Mother are also group item with subitem name & age.
The structure of this item is shown below.
1.New born
          2. Name
            2. Sex
2. Birthday
            3. Month
            3. Day
            3. Year
2. Father
            3. Name
            3. Age
2. Mother
            3. Name
            3. Age
The number to left of each variable is called a level number.
Each group item is followed by its subitem.The level of subitem is 1 more than the level of group item.
          To indicate number of records in a file we may write
          1 Newborn(20)
It indicates a file of 20 records.
For example:
In above record,if we want to refer to the age of the father then it can be done by writing Newborn.father.Age.
If there are 20 records and we want to refer to sex of sixth newborn then it can be done by writing Newborn.sex[6].
Linked List:
BASIC TERMINLOGY
A linked list, or one-way list, is a linear collection of data elements, called nodes, where
the linear order is given by means of pointers. That is, each node is divided into two parts: the first part contains the information of the element, and the second part, called the link field or next pointer field, contains the address of the next node in the list.
Figure  is a schematic diagram of a linked list with 6 nodes, Each node is pictured with two parts. The left part represents the information part of the node, which may contain an entire record of data items (e.g., NAME, ADDRESS,...). The right part represents the Next pointer field of the node, and there is an arrow drawn from it to the next node in the list. This follows the usual practice of drawing an arrow from a field to a node when the address of the node appears in the given field. The pointer of the last node contains special value, called the null pointer, which is any invalid address.


REPRESENTATION OF LINKED LISTS IN MEMORY

Let LIST be a linked list. Then LIST will be maintained in memory as follows. First of all, LIST requires two linear arrays-we will call them here INFO and LINK - such that INFO[K] and LINK[K] contain the information part and the next pointer field of a node of LIST respectively. START contains the location of the beginning of the list, and a next pointer sentinel-denoted by NULL-which indicates the end of the list.
The following examples of linked lists indicate that more than one list may be maintained in the same linear arrays INFO and LINK. However, each list must have its own pointer variable giving the location of its first node.


START          INFO           LINK



START = 9, so INFO[9] = N is the first character.
LINK[9] = 3, so INFO[3] = O is the second character.
LINK[3] = 6, so 1NFO[6] = (blank) is the third character.
LINK[6] = 11, so INFO[11] = E is the fourth character.
LINK[11] = 7, so INFO[7] = X is the fifth character.
LINK[7] = 10, so INFO[10] = I is the sixth character.
LINK[10] = 4, so INFO[4] = T is the seventh character.
LINK[4] = 0, so the NULL value, so the list has ended.
Tree
 A tree is a connected acyclic graph in which one vertex is singled out as the root & several other vertices connected to it by an edge inherit a parent child relationship. Again each node is further connected to their child nodes making set of trees 
Binary Tree
 In computer science a most important type of tree structure is a binary tree. In this type of tree any node will have atmost two branches i.e. degree of each node will be atmost two. We distinguish the two branches of tree as left subtree and right subtree.
A binary tree T is defined as a finite set of elements, called nodes, such that-
a)     T is empty (called the null tree or empty tree) or
b)    T contains a distinguished node R,called root of T and remaining nodes of T form ordered pair of disjoint binary trees T1 and T2.
If T contains root R,then two trees T1 & T2 are left & right subtrees of R.If T1 is nonempty then its root is called as left successor of R & if T2 is nonempty then its root is called as right successor or R.



T contains 11 nodes (A to L).Root of T is A at the top of fig.B is left successor & C is right successor of node A.Left subtree of node A consist of nodes B,D,E & F. Right subtree of node A consist of nodes C,G,H,J,K & L.
Any node in binary tree has 0,1 or 2 successors. The node with no successors are called terminal nodes.
The two binary trees are said to be similar if they have same structure.
The algebraic expression E=(a-b)/((c*d)+e) can be represented by binary tree as shown in fig.
 Fig. expression E=(ab)/((c*d)+e)

Suppose N is node in T with left successor S1 & right successor S2,Then N is called parent of S1 & S2.S1 is left child of N & S2 is right child of N.The line drawn from node N to a successor is called an edge & sequence of consecutive edge is called a path.
A terminal node is leaf & path ending in a leaf is called a branch. The defth(hight) of tree T is the maximum no of nodes in a branch of T.
The tree T is said to be complete if all its levels,except the last.have maximum mo of possible nodes.
A binary tree T is said to be a 2 tree or an extended binary tree if each node N has either 0 or 2 children.In such a case,the nodes with 2 children are called internal nodes & the nodes with 0 children are called external nodes,It is shown in fig.
Fig.Extended 2-tree
The depth(or hight) of a tree T is the maximum no of nodes in a branch of T.This is one more than the largest level no of T,
For example:Following tree has depth 5.

The maximum no of nodes symmetric binary with depth 5 are 31.
Representation of Binary tree in memory
Let T be a binary tree.T can be represented in memory either by link reprentation or by using array alled sequential representation.The requirement in any representation is that one should have direct access to root R given any node N of T.
          The linked representation uses three parallel arrays,INFO,LEFT & RIGHT & a pointer variable ROOT.Each node N of Y will correspond to a location K such that:
1)    INFO[K] contains the data at node N.
2)    LEFT[K] contains the location of left child of node N.
3)    RIGHT[K] contains the location of right child of node N.
ROOT will contain location of root R of T.
A sample representation is shown in fig.

Another method is sequential representation.Here a linear array is used.The root R is stored in TREE[1].If a node n occupies TREE[K],then its left child in TREE[2*K]& right child TREE [2*K+1].An example shown below.


Stack And Queue:
STACK:
Stacks and Queues are two data structures that allow insertions and deletions operations only at the beginning or the end of the list, not in the middle. A stack is a linear structure in which items may be added or removed only at one end. Figure pictures three everyday examples of such a structure: a stack of dishes, a stack of pennies and a stack of folded towels.
Stacks are also called last-in first-out (LIFO) lists. Other names used for stacks are "piles" and "push-down lists. Stack has many important applications in computer science.The notion of recursion is fundamental in computer science. One way of simulating recursion is by means of stack structure. Let we learn the operations which are performed by the Stacks.


                                                                                                                         Figure Of STACK   

QUEUE
A queue is a linear structure in which element may be inserted at one end called the rear, and the deleted at the other end called the front. Figure  pictures a queue of people waiting at a bus stop. Queues are also called first-in first-out (FIFO) lists. An important example of a queue in computer science occurs in a timesharing system, in which programs with the same priority form a queue while waiting to be executed. Similar to stack operations, operations that are define a queue.

Figure of Queue

**********ALL THE BEST**********







No comments:

Post a Comment