DSD Unit 4 Tree Structures

DATA STRUCTURES
DESIGN
Unit – 4
Tree Structures
TREE STRUCTURES
INTRODUCTION
• A tree abstract data type consists of nodes and edges that organize data in a hierarchical fashion. The data
elements are stored in nodes and pairs of nodes are connected by edges.
• The relationships in a tree are hierarchical, with some objects being “above” and some “below” others. A classic
example of a tree structure is the representation of directories and subdirectories in a file system.
Follow study with JBR Trisea You Tube Channel for Tamil Explanation
• Trees also provide a natural organization for data, and consequently have become ubiquitous structures in file
systems, graphical user interfaces, databases, web sites, and other computer systems.
Tree Definitions
• A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each
element in a tree has a parent element and zero or more children elements.
 Subtree: Every node can be the root of its own subtree, which consists of a subset of nodes and edges of the larger tree.
 Root node: A node with no parent is known as root node. It provides the single access point into the structure. The root node is the only
node in the tree that does not have an incoming edge.
 Edge: An edge refers to the link from parent to child.
 Child Node: A node below the given node is called its children. Each node can have one or more child nodes resulting in a parent-child
hierarchy. The children of a node are identified by the outgoing edges.
 Siblings: nodes with the same parent are siblings.
 External nodes or Leaves: A node is external if it has no children. External nodes are also known as leaves.
 Internal Nodes: A node is internal if it has one or more children.
 Ancestors: The ancestors of a node include the parent of the node, its grandparent, its great-grandparent, and so on all the way up to the
root.
 Decendants: All of the nodes in a subtree are descendants of the subtree's root.
 Depth: The length of the path from the root to the node.
 Height: The height of a node is the length of the longest path between the node and a leaf. The height of a tree is the number of levels in
the tree.
 Degree: Number of sub trees of a node.
BINARY TREES
A binary tree is an ordered tree with the following properties,
1. Every node has at most two children.

2. Each child node is labelled as being either a left child or a right child.
3. A left child precedes a right child in the order of children of a node.
The subtree rooted at a left or right child of an internal node is called a left subtree or right subtree, respectively.
Types of binary trees
Proper Binary tree or Strict Binary Tree
A binary tree is called proper or strict binary tree if each node has exactly zero children or two children.
Perfect Binary Tree
• A perfect binary tree is a full binary tree in which all leaf nodes are at the same level. The perfect tree has all
possible node slots filled from top to bottom with no gaps.
Complete Binary Tree
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, from left
to right leaving no gaps. If any of the three leaf nodes labelled A, B, or C in the left tree were missing, that tree
would not be complete.
Properties of Binary Trees
• Binary trees have several interesting properties dealing with relationships between their heights and number of nodes. In a
binary tree, level 0 has at most one node (the root), level 1 has at most two nodes (the children of the root), level 2 has at
most four nodes, and so on. In general, level d has at most 2d nodes.
The properties of binary trees are,

1. The number of nodes in a full binary tree is 2 h+1-1.
2. The number of nodes n in a complete binary tree is between 2 h (minimum) and 2h+1 – 1 (Maximum).
3. The number of leaf nodes in a full binary tree in 2 h.
4. The number of NULL links in a complete binary tree of n nodes is n+1.
Implementations of Binary Trees
There are several choices for the internal representation of trees. The common representations are,
• Linked representation of a binary Trees
• Array-based representation of a binary Trees
Linked Representation of a Binary Trees

A binary tree can be represented using a linked list in a computer’s memory. This type of representation is dynamic,
because memory is dynamically allocated, i.e., when it is needed, and thus it is efficient and avoids wastage of
memory space.
In linked structure of binary tree T, a node maintains references to left child, a data and a reference to the right child.
If the node does not have a left child or right child then, the associated field is None.
A class of the node is declared as follows:
class Node:
def _ _init_ _(self, element):
self. element = element
self. left = None
self. right = None
For linked binary trees, some methods to support for general usage are,
T.add_root(x): Create a root for an empty tree, store x as the element, and return the position of that root; an error occurs if the tree is not empty.
def add_root(self, x):

if self. root is not None:
raise ValueError( Root exists )
self. size = 1
self. root = self. Node(x)
return self. position(self. root)
T.add_left(p, x): Create a new node storing element x, link the node as the left child of position p, and return the resulting position; an error occurs
if p already has a left child.
def add_left(self, p, e):

if node. left is not None:
raise ValueError( Left child exists )
self. size += 1
node. left = self. Node(e, node)
return self. position(node. left)
T.add_right(p, x): Create a new node storing element x, link the node as the right child of position p, and return the resulting position; an error
occurs if p already has a right child.
def add_right(self, p, e):

if node. right is not None:
raise ValueError( Right child exists )
self. size += 1
node. right = self. Node(e, node)
return self. position(node. right)
Array-Based Representation of a Binary Tree
• An array-based representation of a binary tree is based on a way of numbering the positions of tree T. The binary tree requires the root to be stored at 0 th index. For every
element of binary tree,
 the left child at position 2i+1.
 the right child at position 2i+2
 The parent node is at i-1/2
• This numbering is known as a level numbering and it numbers the positions on each level of tree in increasing order from left to right. The level numbering is based on
possible positions within the tree, not actual positions of a given tree, so they are not necessarily consecutive. For example, in Figure, there are no nodes with level
numbering 13 or 14, because the node with level numbering 6 has no children.
Example:
APPLICATIONS OF BINARY TREES
For node F, i=5

1. Expression trees are used in compilers
Its left child at 2i+1 = 2*5 +1
2. Trees are used in hierarchical database management system
= 10 +1=11
3. Binary search trees support search, insertion and deletion on
=J
a collection of items in O(log n)
Its Right child at 2i+2 = 2*5 + 2
4. Priority Queue supports search and deletion of minimum on
=12 a collection of items in logarithmic time.
=k
For a node D, i=3

Its parent at i-1/2 = 3-1/2
= 2/2=1
=B
TREE TRAVERSAL ALGORITHMS
The tree traversal operation, is one of the most common operations performed on trees. A traversal of a tree is a
systematic way of accessing, or visiting, all the nodes in a tree. Each node is processed only once but it may be
visited more than once.
There are three tree traversal algorithms. They are,
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal.
Preorder Traversal
A tree traversal must begin with the root node, since that is the only access into the tree. After visiting the root node,
traverse the nodes in its left subtree followed by the nodes in its right subtree. Since every node is the root of its own
subtree, repeat the same process on each node, resulting in a recursive solution.
Algorithm
• Visit the root
• Traverse the left subtree in preorder
• Traverse the right subtreeFollow
in preorder
study with JBR Trisea You Tube Channel for Tamil Explanation
The preorder traversal of above tree will be,
A, B, D, E, H, C, F, G, I, J.
The recursive function is,
def preorderTraversal( subtree ):

if subtree is not None :
print( subtree.data )
preorderTraversal ( subtree.left )
preorderTraversal ( subtree.right )
Inorder Traversal
In the inorder traversal, first traverse the left subtree and then visit the root node followed by the traverse of the
right subtree.
Algorithm
The inorder traversal of above tree will be,
• Traverse the left subtree in inorder
D, B, H, E, A, F, C, I, G, J.
• Visit the root
The recursive function is,
• Traverse the right subtree in inorder
def inorderTraversal( subtree ):
Example if subtree is not None :
inorderTraversal ( subtree.left )
inorderTraversal ( subtree.right )
Postorder Traversal
In a postorder traversal, first traverse the left subtree The postorder traversal of above tree will be,
then traverse the right subtree and finally the root
node is visited.
Algorithm D, H, E, B, F, I, J, G, C, A.
Traverse the left subtree in postorder
Traverse the right subtree in postorder The recursive function is,
Visit the root

def postorderTraversal( subtree ):
Example
if subtree is not None :
postorderTraversal ( subtree.left )
postorderTraversal ( subtree.right )
Follow study with JBR Trisea You

Tube Channel for Tamil Explanation
EXPRESSION TREES
• Expression tree is a binary tree in which the leaf To evaluate the expression tree, apply the operator at
nodes are operands and the interior nodes are the root to the values obtained by recursively
operators.
evaluating the left and right subtrees.
• The expression tree is a binary tree because all of
the operations are binary. Inorder traversal of the above tree is,
• It is also possible for a node to have only one a+b*c+d*e+f*g
child, if it is a unary minus operator. Preorder traversal
• Example: Expression tree for (a + b * c) + ((d * e ++a*bc* +*defg
+ f) * g)
Postorder traversal.
abc* +de*f+g*+

Constructing an Expression Tree
Algorithm to convert a postfix expression into an expression tree.

1. Convert infix to postfix expression.
2. Read one symbol at a time from the postfix expression.
3. If the symbol is an operand then create a one-node tree and push a pointer onto a stack.
4. If the symbol is an operator, pop pointers to two trees T 1 and T2 from the stack (T1 is popped first) and form a
new tree whose root is the operator and whose left and right children point to T 2 and T1. A pointer to this new
tree is then pushed on to the stack.
Hashing Techniques
BINARY SEARCH TREES
• Binary search tree is a binary tree, in which for every node X in the tree, the values of all the keys in its left sub
tree are smaller than the key value in X and the values of all the keys in its right subtree are greater than the key
value in X.
• Consider the binary search tree in Figure 6.8, in which the root node contains key value 82 and all keys in the
root's left subtree are less than 82 and all of the keys in the right subtree are greater than 82. The inorder traversal
of binary search tree will visit the nodes in increasing key order. For the above binary search tree, the inorder
traversal would be 1, 3, 15, 23, 25, 35, 40, 82, 83, 86, 90, 102.
Binary Search Tree Declaration
There is no difference between regular binary tree declaration and binary search tree declaration. The difference is
only in data but not in structure.
class BSTNode:
def __init__(self, element):
self. element = element
self. left = None
self. right = None
Operations on Binary Search Trees

Find
The find operation starts from the root. That is the target key value is compared to the key in the root node. If the
root contains the target key value, the search is successful. But if the target key is not in the root and key is smaller
than the root then perform the find operation in the left subtree. If the target key is greater than the root then perform
the find operation in the right subtree. This process is repeated until target key is located or a null child link is end
up.
Example:
• To search a key value 25 in the binary search tree from Figure 6.9 Start comparing the target key 25 to root node
82. Since the target key 25 is less than 82, then move left. The target key is then compared to 15. This time move
right since the target key is greater than 15. Next, the target key is compared to 40, resulting in a move to the left.
Then, compare the left child of node 40, and the target key is matched so report a successful search.
• To search a key value 110. First compare target key 110 with the root node. Since 110 is greater than 82, move
right. Repeating the same process 110 is compared with 90, 102 and moving right. Now 102 does not have any
right subtree and reaching a null child indicates an unsuccessful search.
Recursive Function to perform Find Operation
def bstFind( self, subtree, target ):

if subtree is None :
return None
elif target < subtree.key :
return self.bstFind( subtree.left )
elif target > subtree.key :
return self.bstFind( subtree.right )
else :
return subtree
Find Min
In binary search trees the minimum element is the left most node, which does not have any left child. It can be located by starting
at the root and following the left child links until a null link is encountered.
def bstFindMin( self, subtree ):

return None
elif subtree.left is None :
return subtree
else :
return self.bstFindMin( subtree.left )
This method requires the root of the tree or as an argument. It returns either a reference to the node containing the smallest key
value or None when the tree is empty.
Find Max
In binary search trees the maximum element is the right most node, which does not have any right child. It can be located
by starting at the root and following the right child links until a null link is encountered.
def bstFindMax( self, subtree):

if subtree is None:
return None
elif subtree.right is None :
return subtree
else :
return self.bstFindMax( subtree.right)
Insertion
• When a binary search tree is constructed, the keys are added one at a time. To insert a key, a new node is created
for each key and linked into its proper position within the tree. That is, first the root node is inserted, then the
next key is compared with the root node. If the new key is greater than root, it is added to the right subtree, and if
it is smaller than the root, it is added to the left subtree. The new nodes are always inserted as a leaf node in its
proper position such that the binary search tree property is maintained.
• Example: Build a binary search tree for the key list 82, 15, 90, 40, 3, 83.
• To insert a value 82, a node is created and its data field set to 82. Since the tree is initially empty, this first node becomes
the root of the tree. Next, insert value 15. Since it is smaller than 82, it has to be inserted to the left of the root, which
means it becomes the left child of the root. Value 90 is then inserted in a node linked as the right child of the root since it
is larger than 82. Similarly, all other values are inserted in the binary search tree inserted as a leaf node in its proper
position such that the binary search tree property is maintained.
Recursive function to perform insert operation
def bstInsert( self, subtree, key, value ):

subtree = BSTMapNode( key, value )
elif key < subtree.key :
subtree.left = self.bstInsert( subtree.left, key, value )
elif key > subtree.key :
subtree.right = self.bstInsert( subtree.right, key, value )
return subtree
Deletion
Deleting an element from a binary search tree is a bit more complicated than searching for an element or inserting a new element into the tree.
A deletion involves searching for the node that contains the target key and then unlinking the node to remove it from the tree. When a node is
removed, the remaining nodes must preserve the search tree property.
There are three cases in the deletion:
1. The node is a leaf.

2. The node has a single child.
3. The node has two children.
Deleting a Leaf Node
Removing a leaf node is the easiest among the three cases. To delete leaf node from the binary search tree first find that node, then it has to be
unlinked. This can be done by setting the left child field of its parent to None/ Null.
To delete key value 23 from the binary search tree in Figure set the left child field of its parent node 25, to None.
Deleting an Interior Node with One Child
• If the node to be removed has a single child, it can be deleted after changing the link of the parent to reference the
child of the node being deleted.
• To delete key value 83 from the binary search tree, it has a subtree 86 linked as the right child. If the left child of
90 is set as none it will lose all of its descendants. In this example 86 also unlinked. To avoid this set the left child
of 90 as the right child of 83. So, 83 is unlinked and its descendant is linked to the parent node.
Removing an Interior Node with Two Children
• If the node to be deleted has two children, then find the node with smaller value in the right subtree or find the
node with bigger value in the left subtree. Replace the node in place of deleted node.
• Node 15 has two children, both of which are the roots of their own subtrees. To delete node 15, find the smallest
node in the right subtree. That is 23. After finding the element, replace it to the node containing the element being
removed. Now the node 15 is deleted.
• Function to delete elements from the binary Search tree elif subtree.left is None or subtree.right is None :
if subtree.left is not None :
def bstRemove( self, subtree, target ): return subtree.left
if subtree is None : else :
return subtree return subtree.right
elif target < subtree.key : else
subtree.left = self.bstRemove( subtree.left, target ) successor = self.bstMinimum( subtree.right )
return subtree subtree.key = successor.key
elif target > subtree.key : subtree.value = successor.value
subtree.right = self.bstRemove( subtree.right, target ) subtree.right = self.bstRemove( subtree.right,
successor.key )
return subtree
return subtree
else :
if subtree.left is None and subtree.right is None :
return None
AVL TREE
• The AVL tree, was invented by G. M. Adelson-Velskii and Y. M. Landis in 1962, improves on the binary search
tree by always guaranteeing the tree is height balanced, which allows for more efficient operations.
 A binary tree is balanced if the heights of the left and right subtrees of every node differ by at most 1.
 Balance Factor = Height of Left Sub Tree – Height of Right Subtree
 Maintaining a balanced tree, ensure its height never exceeds 1.44 log n. This height is sufficient for providing O
(log n) time operations even in the worst case.
 Example 1: Balanced AVL tree
• Example 2: Imbalanced tree. Not an AVL tree
 The search and traversal operations are the same with an AVL tree as with a binary search tree.
 The insertion and deletion operations have to be modified in order to maintain the balance property of the tree as
new keys are inserted and existing ones removed.
Insertion
In AVL tree, the new key is added at the child node. When the new key is inserted into an AVL tree, the balance property of the
tree must be maintained. If the insertion of the new key causes any of the subtrees to become unbalanced, they must be
rebalanced.
Rotations
Multiple subtrees can become unbalanced after inserting a new key. To handle this the first subtree encountered this out of
balance has to be rebalanced. The root node of this subtree is known as the pivot node.
An AVL subtree is rebalanced by performing a rotation around the pivot node. This involves rearranging the links of the pivot
node, its children, and possibly one of its grandchildren. The actual modifications depend on which descendant's subtree of the
pivot node the new key was inserted into and the balance factors.
• There are four possible cases:
• Case 1: Inserting a node as a left child of left subtree
• Case 2: Inserting a node as a right child of right subtree
• Case 3: Inserting a node as a right child of left subtree
• Case 4: Inserting a node as a left child of right subtree.
 If the insertion occurs on the outside of the subtree (left- left or right-right) then it is handled by the single rotation
 If the insertion occurs on the inside of the subtree (left-right or right-left) then it is handled by the double rotation
• Case 1: Single Rotation with Left
Routine to perform Single Rotation with Left
def avlSingleRotateRight( self, k2 ):

k1 = k2.left
k2.left = k1.right
k1.right = k2
k2.height = 1 + max(self.Height(k2.left), self.Height(k2.right))
return k1
• Case 2: Single Rotation with Right
Routine to perform Single Rotation with Right
def avlSingleRotateLeft( self, k1 ):

k2 =k1.right
k1.right = k2.left
k2.left = k1
return k2
• Case 3: Left Right Double Rotation
Routine to perform double rotation with left
def avlDoubleRotateLeft( self, k3 ):

k3.left= avlSingleRotateRight(k3.left)
return avlSingleRotateLeft(k3)
• Case 4: Right Left Double Rotation
Routine to perform double rotation with left
def avlDoubleRotateRight( self, k1 ):

k1.Right= avlSingleRotateLeft(k1.left)
return avlSingleRotateRight(k1)
After a rotation is performed, the balance factor of the impacted nodes has to be changed to reflect the new
node heights.
Implementation for insertion BF = self.calculateBalance(root)
If BF > 1 and key < root.left.data:
def insert(self,root,key):
Return self. avlSingleRotateRight (root)
if not root:
If BF < -1 and key > root.right.data:
return node(key)
Return self. avlSingleRotateLeft (root)
elif key < root.data:
If BF > 1 and key < root.left.data:
root.left = self.insert(root.left,key)
Root.left=self. avlDoubleRotateLeft (root.left)
else:
If BF < -1 and key < root.right.data:
root.right = self.insert(root.right,key)
Root.right=self. avlDoubleRotateright (root.right)
root.height = 1 + max(self.Height(root.left),
Return root
self.Height(root.right))
Example: Insert 4
Insert 1, 2, 3, 4, 5, 6, 7
Insert 1
Insert 2 Insert 5
Insert 3
• Insert 6 • Insert 7

• Insert 14
• Insert 16
• Insert 13
• Insert 15

• Insert 12
• To Insert 11
• Insert 10
• Insert 8 • Insert 9

• Deletion
• When a node is removed from an AVL tree, it must ensure that the balance property is maintained. In the insertion
operation, at most one subtree can become unbalanced. After the appropriate rotation is performed on the subtree,
the balance factors of the node's ancestors do not change. Thus, it restores the height-balance property both locally
at the subtree and globally for the entire tree.
• This is not the case with a deletion. When a subtree is rebalanced due to a deletion, it can cause the ancestors of
the subtree to then become unbalanced. This effect can ripple up all the way to the root node. So, all of the nodes
along the path have to be evaluated and rebalanced if necessary
HEAPS
A heap is a complete binary tree in which every node satisfies a structure property and a heap order property.
Structure Property
A heap is a binary tree that is completely filled with the possible exception at the bottom level, which is filled from left to
right.
Heap order Property
Based on the heap order property, heaps can be classified as Max heap and Min Heap.
Max-Heap
In a maximum heap, for every node X in a tree, the key in the parent of X is greater than (or equal to) the key in X, with
the exception at the root.
The largest value in a max-heap will always be stored in the root while the smallest values will be stored in the leaf nodes.
Min- Heap
In a minimum heap, for every node X in a tree, the key in the parent of X is smaller than (or equal to) the key in X, with
the exception at the root.
The smallest value in a min-heap will always be stored in the root while the largest values will be stored in the leaf nodes.
Insertion
• When a new value is inserted into a heap, the heap order property and the heap structure property (a complete
binary tree) must be maintained.
• Algorithm
1. Create a new node and fill it with the new value.
2. The node is then attached as a leaf node at the only spot in the tree where the heap structure property can be
maintained. Remember, a heap is a complete tree in which, the leaf nodes must be filled from left to right.
3. To restore the heap order property, the new value has to move up along the path in reverse order towards root
until a node is positioned properly. This operation is known as a sift-up. It can also be known as an up-heap,
bubble-up, percolate-up, or heapify-up, heapup-bubbling etc.,
Hashing Techniques
• Example
• To insert 89 in the above max heap, create a new node and it is inserted in the next available location.
Hashing Techniques
• Inserting node 89 would violate the heap order property. So, the sift-up operation compares the new value 89 in the new node to the
value in its parent node, 23. Since its parent is smaller, the two values are swapped.
• Value 89 is then compared to the value in its new parent node 86. Again, the parent is smaller and the two values have to be swapped.
• The comparison is repeated again, but this time 89 is less than its parent 110 and the process ends.
Deletion/ Extractions
When a value is extracted and removed from the heap, it can only come from the root node.
Thus, a max-heap, always extract the largest value and a min-heap, always extract the smallest value.
After the value in the root has been removed, the binary tree is no longer a heap since there is now a gap in the root
node.
To restore the tree to a heap, another value will have to take the place of the value extracted from the root and a node
has to be removed from the tree since there is one less value in the heap.
Since a heap requires a complete tree, there is only one leaf that can be removed. That is, the rightmost node on the
lowest level.
• To maintain a complete tree and the heap order property, an extraction requires several steps.
1. Copy and save the value from the root node, which will be returned after the extraction process has been
completed.
2. The value from the rightmost node on the lowest level is copied to the root and that leaf node is removed from
the tree.
3. To restore the heap order property, starting at the root node, the node's value is compared to its children and
swapped with the larger of the two.
4. The sift-down is then applied to the node into which the smaller value was copied. This process continues until
the smaller value is copied into a leaf node or a node whose children are even smaller.
• Example
• In the above max heap, the maximum value 110 is deleted. To fill the gap and to restore the heap order property,
the rightmost node on the lowest level 23 is copied and saved to the root node.
• To restore the heap order property, value 23 has to be sifted-down the tree. The sift-down operation applied to
value 23 in the root node. So, value 23 is swapped with 89, then with 86 resulting in a proper heap.
• Implementation
The array-based representation of a binary tree is suitable for a complete binary tree. Since a heap is a complete tree, array can be used to illustrate the heap
structure. If the nodes are numbered in the heap from left to right by level starting with zero then a tree can be represented as follows.
Node Access
Since a heap is a complete tree, it will never contain missing internal nodes or holes. Thus, the root will always be at position 0 within the array and its two
children will always occupy elements 1 and 2.
Given the array index i of a node, the index of the parent or children of that node
can be computed as:
parent = (i-1) // 2
left = 2 * i + 1
right = 2 * i + 2
This allows us to quickly locate the parent of any node or the left and right child of any node.
Array-based implementation of the max-heap self._count += 1 tmp = self._elements[i]
# Sift the new value up the tree. self._elements[i] = self._elements[parent]
class MaxHeap : self._siftUp( self._count - 1 ) self._elements[parent] = tmp
# Create a max-heap with maximum capacity of maxSize. self._siftUp( parent )
def _init_( self, maxSize ): # Extract the maximum value from the heap.
self._elements = Array( maxSize ) def extract( self ): # Sift the value at the i element down the tree.
self._count = 0 if self._count > 0: def siftDown( self, i ):
print("Cannot extract from an empty heap.") left = 2 * i + 1
# Return the number of items in the heap. # Save the root value and copy the last heap value to the right = 2 * i + 2
root.
def _len_( self ):
value = self._elements[0]
return self._count # Determine which node contains the larger value.
self._count -= 1
largest = i
self._elements[0] = self._elements[ self._count ]
# Return the maximum capacity of the heap. if left < count and self._elements[left] >=
# Sift the root value down the tree. self._elements[largest] :
def capacity( self ):
self._siftDown( 0 ) largest = left
return len( self._elements )
elif right < count and self._elements[right] >=
self._elements[largest]:
# Sift the value at the i element up the tree.
# Add a new value to the heap.
largest = right
def _siftUp( self, i ):
def add( self, value ):
# If the largest value is not in the current node (i), swap it
if i > 0 :
if self._count < self.capacity(): with the largest value and repeat the process.
parent = i // 2
print("Cannot add to a full heap.") if largest != i :
if self._elements[i] > self._elements[parent] : # swap
# Add the new value to the end of the list. swap( self._elements[i], self._elements[largest] )
elements
self._elements[self._count ] = value _siftDown( largest )
MULTIWAY SEARCH TREES
• A multiway search tree is a general tree, in which internal nodes may have more than two children. It stores a
collection of items of the form (k, x), where k is a key and x is an element.
• By definition an m-way search tree is a m-way tree in which:
 Each node has m children and m-1 key fields
 The keys in each node are in ascending order.
 The keys in the first i children are smaller than the i th key
 The keys in the last m-i children are larger than the i th key
 The leaves store no items and serve as placeholders
• These external nodes can be efficiently represented by None references. Based on this definition, there is an
interesting relationship between the number of key-value pairs and the number of external nodes in a multiway
search tree. The height of a (2,4) tree storing n items is O(logn).
(2,4) Trees
• The (2-4) tree maintain two simple properties. They are,

Size Property: Every internal node has at most four children.
• Depth Property: All the external nodes have the same depth.
• A 2-4 tree or a 2-3-4 tree is a balanced search tree having following three types of nodes.
1. 2-node has one key and two child links.

2. 3-node has two keys and three child links.
3. 4-node has three keys and four child links.
• If a node has more than one keys (3-node and 4-node), the keys must be in the sorted order.
 An interior node contains one key, always contains two child links, one for the keys less than its key and one for the
keys greater than its key.
 An interior node contains two keys, always contain three child links that have one of the value ranges: (1) keys less
than the node's first key, (2) keys greater than the node's first key but less than its second key, and (3) keys greater
than the node's second key.
 An interior node contains three keys, always contain four child links that have one of the value ranges: (1) keys less
than the node's first key, (2) keys greater than the node's first key but less than its second key, (3) keys greater than
the node's second key but less than its third key and (4) ) keys greater than the node's third key.
Searching
• Searching a 2-4 tree is very similar to that of a binary search tree. Start at the root and follow the appropriate branch
based on the value of the target key.
 The only difference is that compare the target against both keys if the node contains two keys, and possibly three
branches.
 A successful search will lead to a key in one of the nodes while an unsuccessful search will lead to a null link. That null
link will always be in a leaf node.
Successful search for key 24
 Unsuccessful search for key 12
• Insertion
• To insert a new key k, into a (2,4) tree, first perform a search for k. If the tree has no item with key k, this search
terminates unsuccessfully at an leaf node z. Let w be the parent of z. Now insert the new item into node w and add
a new child y (an external node) to w on the left of z.
• The insertion method must preserve the depth property, since add a new external node at the same level as
existing external nodes. Nevertheless, it may violate the size property.
• If a node w was previously a 4-node, then it would become a 5-node after the insertion, which causes the tree T to
no longer be a (2,4) tree. This type of violation of the size property is called an overflow at node w, and it must be
resolved in order to restore the properties of a (2,4) tree.
• Let c1, . . . ,c5 be the children of w, and let k1, . . . ,k4 be the keys stored at w. To remedy the overflow at node w,
we perform a split operation on w as follows.
•
• As a consequence of a split operation on node w, a new overflow may occur at u. If such an overflow occurs, it
triggers in turn a split at node u. A split operation either eliminates the overflow or propagates it into the parent of
the current node.
• Example 1:
• A 2-4 tree may have maximum 3 children in a node. Inserting key 17 in a node creates an overflow. So that is splited
and third key 15 is promoted to its parent node. Now overflow occurs in that parent node this leads to another split.
The parent node is splited and its third key 12 is promoted to its parent node. That is the final tree.
Hashing Techniques
• Example 2:
• Creating 2-4 tree with following keys, 4,6,12,15,3,5,10,8.
• Insert 15
• Inserting key 15 in a node causes an overflow. Now split this node ie., 12 is promoted to its parent.
• Insert 3
• Insert 5
• Inserting key 5 also causes an overflow. Now split that node and key 5 is promoted to its parent.
• Insert 10
• Insert 8
• Analysis of Insertion in a (2,4) Tree

• Insertion of a new key and child can be implemented in O(1) time, as can a single split operation. The number of cascading split
operations is bounded by the height of the tree, and so that phase of the insertion process also runs in O(log n) time. Therefore, the
total time to perform an insertion in a (2,4) tree is O(logn).
• Deletion
• The removal of a key k from a (2,4) tree begin with search that in a tree. Removing an item from a node should
preserves the depth property and the size property. If a node was previously a 2-node, then it becomes a 1-node
with no items after the removal, which is not allowed in a (2,4) tree. This type of violation of the size property is
called an underflow at node w.
• To remedy an underflow at node w, check whether an immediate sibling of w is a 3-node or a 4-node. If such a
sibling node s is found, then perform a transfer operation, in which move a child of s to u and a key of u to w.
• If w has only one sibling, or if both immediate siblings of w are 2-nodes, then perform a fusion operation, in
which merge w with a sibling, creating a new node w’, and move a key from the parent u to w’.
• Example:
• Delete keys 4, 12, 13, 14 from the following (2,4) tree.
• To delete 4
• Let key to be deleted node is w, its sibling node is s and its parent node is u. Removal of
key 4 causing underflow at w. So, perform transfer operation. That is transfer key 6 from its
sibling s to its parent u and transfer key 5 from parent u to node w.
• To delete 12
• Deleting key 12 causing underflow at root. So, perform fusion operation.
• To delete 13
• To delete 14
• Deleting key 14 causes underflow. So, perform fusion, which causes another underflow.
Second fusion operation causes the root to be removed.
Performance of (2, 4) Trees
• The time complexity analysis for a (2,4) tree having n key-value pairs is based on the following:
• • The height of a (2,4) tree storing n entries is O(logn),
• • A split, transfer, or fusion operation takes O(1) time.
• • A search, insertion, or removal of an entry visits O(logn) nodes.
• Thus, (2,4) trees provide for fast map search and update operations.
Advantages of multiway search trees
1. Multi-way trees are often required fewer internal nodes than binary search trees to store items.
2. They are efficient for all dictionary methods.
3. They are easy to maintain and balance.
4. This type of tree will be used when the data to be accessed/stored is located on secondary storage devices because they allow
for large amounts of data to be stored in a node.
5. They provide fast information retrieval.
thank you

DSD Unit 4 Tree Structures

Uploaded by

Copyright:

Available Formats

DSD Unit 4 Tree Structures

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DSD Unit 4 Tree Structures

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES

A binary tree is an ordered tree with the following properties,

1. Every node has at most two children.

Types of binary trees

Proper Binary tree or Strict Binary Tree

Complete Binary Tree

The properties of binary trees are,

Linked Representation of a Binary Trees

def add_root(self, x):

def add_left(self, p, e):

def add_right(self, p, e):

For node F, i=5

For a node D, i=3

def preorderTraversal( subtree ):

Visit the root

Follow study with JBR Trisea You

Follow study with JBR Trisea You

Algorithm to convert a postfix expression into an expression tree.

Operations on Binary Search Trees

def bstFind( self, subtree, target ):

def bstFindMin( self, subtree ):

def bstFindMax( self, subtree):

def bstInsert( self, subtree, key, value ):

There are three cases in the deletion:

1. The node is a leaf.

Deleting a Leaf Node

 Example 1: Balanced AVL tree

Routine to perform Single Rotation with Left

def avlSingleRotateRight( self, k2 ):

Routine to perform Single Rotation with Right

def avlSingleRotateLeft( self, k1 ):

Routine to perform double rotation with left

def avlDoubleRotateLeft( self, k3 ):

Routine to perform double rotation with left

def avlDoubleRotateRight( self, k1 ):

Follow study with JBR Trisea You

Follow study with JBR Trisea You

Follow study with JBR Trisea You

• The (2-4) tree maintain two simple properties. They are,

1. 2-node has one key and two child links.

Successful search for key 24

 Unsuccessful search for key 12

• Analysis of Insertion in a (2,4) Tree

Advantages of multiway search trees

You might also like