Non-linear data structures
TREES
TREES
Non-linear data structure Use to represent hierarchical relationship among existing data items.
Tree : definition
It is finite set of one or more data items such that There is special data item called as root of the tree And remaining data items are partitioned into number of mutually exclusive subsets each of which is itself a tree. They are called subtrees.
Trees Data Structures
Tree Nodes Each node can have 0 or more children A node can have at most one parent Binary tree Tree with 02 children per node
Tree
Binary Tree
Node Each data item in a tree. Root no parent. The topmost node (A) Each node in a tree has zero or more nodes B,C,D
Root node child nodes
A edg e
Trees Terminology
Interior nodes Leaf nodes
Height
Terminology
parent node A node that has a child is called the child's parent node
An internal node or inner node
is any node of a tree that has child nodes.
Depth The
of tree distance from root to leaf node. In given tree it is 3. depth of a node n is the length of the path from the root to the node
Degree of node : It is the number of subtrees of node in given tree. Degree of node B is one, A & C is 3. Degree of tree It is the maximum degree of nodes in given tree. In given tree degree of node b is one and A&C is 3 so max degree is 3
Non terminal nodes Any node whose degree is not zero
Leaf or Terminal node no child
Siblings The children nodes of given parent node. They are also called brothers
Level The entire tree is leveled in such way that root node is at level 0, its immediate children are at level 1 and their immediate children at level two and so on. i.e. if node is at level n, then its children will be at level n+1.
Edge Line drawn from one node to another node Path It is the sequence of consecutive edges from source to the destination node. The path between A to F is (A,C)
Binary tree
Set of data items with node subtree subtree
Root Left
Right Tree
with 02 children per node
Strictly binary trees
A binary tree is Strictly binary tree if and only if : Each node has exactly two child nodes or no nodes
full binary
A binary tree is a full binary tree if and only if Each non leaf node has exactly two child nodes All leaf nodes are at the same level
Complete binary tree
A binary tree is a complete binary tree (of height h , we take root node as 0 ) if and only if :Level 0 to h-1 represent a full binary tree of height h-1 One or more nodes in level h-1 may have 0, or 1 child nodes If j ,k are nodes in level h-1, then j has more child nodes than k if and only if j is to the left of k
Extended binary tree
A binary tree T is said to be 2-tree or extended binary tree if each node N has either 0 or 2 children. In such case, node with 2 children are called internal nodes and the nodes with 0 children are called external nodes.
extended binary tree
Binary tree
Binary tree representation
Root node index starts with 0
0 A
A B D
3 1
1 B 2 C 2 3 D 4 E 5 F 6 6 G
C F
4 5
LINK Representation
Each node consist of Data Left child Right child
Lchild
Data
Rchild
LINK Representation
root b d f g leftChild element rightChild h a c e
Maximum Number Of A Nodes tree of a given height h full binary
has 2h 1 nodes.
Maximum number of nodes =1+2+4+8++ 2h-1
Binary Tree Traversal Methods
It is the way in which each node in the tree is visited exactly once in systematic manner. Used to represent arithmetic expressions. Preorder In order Post order
Tree traversals
The order in which the nodes are visited during a tree traversal,
preorder
inorder
postorder
In preorder, the root is visited first In inorder, the root is visited in the middle
In postorder, the root is visited last
Start at the root node
Pre-order traversal
Traverse the left subtree Traverse the right subtree
The nodes of this tree would be visited in the order : DBACFEG
In-order traversal
Traverse the left subtree Visit the root node Traverse the right subtree
ABCDEFG
Post-order traversal
Traverse the left subtree Visit the root node Traverse the right subtree
ACBEGFD
Post-order
Conversion of expression into binary tree A+B
1.A+B*C 2. A/B-C
1.(A-B)+C 2. A-(B+C)
(A+B)*(C-D)
Draw tree:Write preorder, postorder, inorder
A/B+C/D (A+B+C)*(D+E+F)
Inorder: EACKFHDBG preorder: FAEKCDHGB
F A E C K D H B G
Binary Search Tree
The value of the key in the left child or left subtree is less than value of the root The value of the key in right subtree is more than or equal to the value of the root. All subtree of the left and right children observe these two rules.
binary search tree (BST) is a node based binary tree data structure sometimes also be called ordered or sorted binary tree
Searching
Can be recursive or iterative process. begin by examining the root node. If the tree is null, the value we are searching for does not exist in the tree. Otherwise, if the value equals the root, the search is successful. If the value is less than the root, search the left subtree. Similarly, if it is greater than the root, search the right subtree. This process is repeated until the value is found or the indicated subtree is null. If the searched value is not found before a null subtree is reached, then the item must not be present in the tree.
insertion
Check the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than the root.
Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */ void InsertNode(Node* &treeNode,
Node *newNode) { if (treeNode == NULL) treeNode = newNode; else if (newNode->key < treeNode>key) InsertNode(treeNode->left, newNode); else InsertNode(treeNode->right, newNode); }
Deletion
Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree. Deleting a node with one child: Remove the node and replace it with its child. Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays
B-trees
B-trees are balanced sort trees that are optimized for situations when part or all of the tree must be maintained in secondary storage such as a magnetic disk. The B-tree algorithm minimizes the number of times a medium must be accessed to locate a desired record, thereby speeding up the process.
B-tree
A binary-tree, each node of a b-tree may have a variable number of keys and children. The keys are stored in nondecreasing order
Each key has an associated child that is the root of a subtree containing all nodes with keys less than or equal to the key but greater than the preceeding key. A node also has an additional rightmost child that is the root for a subtree containing all keys greater than any keys in the node.
Searching techniques
Searching techniques
Process of finding elements within list of elements. Two categories:Linear search
No prerequisite
Binary search
List must be sorted.
Linear search
Access an element of an array one by one sequentially. Search unsuccessful if element is not found. Average case, we may have to scan half of the list.
Binary search
Searches item in min comparisons, This tech, First find middle element (mid=first + last)/2) Compare mid element with an item There are three cases,
If mid element=search element then search is successful. If it is less than desired item then search only first half array, beg=mid-1
9,12,24,30,36,45,70
Item=45 Beg=0 and last=6 Mid=int(0+6)/2=3 A[3]=30 45>30 then Beg=mid+1 =3+1 =4
New mid is, Int(4+6)=5 A[5]=45 Search is successful
12,14,25,32,35,40,45,48,5 0
Item search=25
