Embedded Files
Tree Traversals
Tree Traversals
Assume we have a binary tree . We can traverse the tree in several ways.
Inorder, PreOrder, PostOrder
For the tree
1
2 3
4 5
Inorder is
Left Root Right
We go to the Left child and run the function in a recursive manner.
So we go to 2 then we apply the same function to get :
4
Now 4 does not have any children so we don't do anything and go to root.
2
Now the right child of 2 :
5
Now we are done with 2 so we print :
1
and process the right child of 1 to get :
3
The order is :
4 2 5 1 3
PreOrder is
Root, Left, Right
1 2 4 5 3
PostOrder is
Left, Right, Root
4 5 2 3 1
File: "order1.cpp"
// C++ program for different tree traversals#include <iostream>using namespace std;/* A binary tree node has data, pointer to left childand a pointer to right child */struct Node { int data; struct Node *left, *right; Node(int data) { this->data = data; left = right = NULL; }};/* Given a binary tree, print its nodes according to the"bottom-up" postorder traversal. */void printPostorder(struct Node* node){ if (node == NULL) return; // first recur on left subtree printPostorder(node->left); // then recur on right subtree printPostorder(node->right); // now deal with the node cout << node->data << " ";}/* Given a binary tree, print its nodes in inorder*/void printInorder(struct Node* node){ if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ cout << node->data << " "; /* now recur on right child */ printInorder(node->right);}/* Given a binary tree, print its nodes in preorder*/void printPreorder(struct Node* node){ if (node == NULL) return; /* first print data of node */ cout << node->data << " "; /* then recur on left sutree */ printPreorder(node->left); /* now recur on right subtree */ printPreorder(node->right);}/* 1 2 34 5*/
void printBfsorder(struct Node* node){ queue<Node*> queueObj ; queueObj.push( node ) ; while( ! queueObj.empty() ) { Node* current = queueObj.front() ; cout << current->data << endl ; queueObj.pop() ; //place children in queue if ( current->left != NULL ) { cout << "Pushing:" << current->left->data << endl ; queueObj.push( current->left ) ; } if ( current->right != NULL ) { cout << "Pushing:" << current->right->data << endl ; queueObj.push( current->right ) ; } } //while}
/* Driver program to test above functions*/int main(){ struct Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); cout << "\nPreorder traversal of binary tree is \n"; printPreorder(root); cout << "\nInorder traversal of binary tree is \n"; printInorder(root); cout << "\nPostorder traversal of binary tree is \n"; printPostorder(root); return 0;}
Exercise:
Determine the inorder , preorder , postorder and bfs for the following trees.
a) 1
2
3
4 5
b)
1
2 3
4 5
c)
1
2 3
4 5 6 7
Binary Search Trees
Binary Search Trees
A binary search tree is a binary tree in which for each node the left nodes are less than the node and all the right nodes are greater than the node. This property applies in turn to the child subtrees that also have to be binary search trees.
Ex:
10
4 14
Exercise
1) Are the following trees binary search trees.
a)
20
10 15
b)
20
10
5
c)
30
20 40
10 25 35 27
d)
30
20 40
10 25 35 45
e)
30
20 40
10 25 35 45
5
Operations on a binary search tree.
1) Search a tree
2) Delete a node .
1) Searching is easy to do . We compare the value at the root node with our search value say x.
If x is less than the root node then we can conclude that the node must be to the left and we look at the left child. We continue this process till we hit a node that matches or we hit a leaf node whose value does not match and in that case the node does not exist in the tree.
2) Deletion of a node.
There are 3 cases .
a) The node to be deleted is a leaf node.
30
20 40
10 25 35 45
If we need to delete 10 we can just delete it. The resulting tree will still be a binary search tree.
b) The node to be deleted has single child node.
30
20 40
25 35 45
Say we need to delete the node 20. It has a single child of 25. We can swap the values and delete the leaf node in this case.
30
25 40
35 45
c)
30
20 40
10 25 35 45
We need to delete the node 30 . We can do this in 2 ways. One way is to look at the right child of 40 and take it's min value which is 35 and place it at the root.
35
20 40
10 25 45
This will work because all the nodes of child 40 were greater than 30 so the left child of 40 is still good as all it's nodes will be less than 35. All the nodes of 40 will be higher than 35 since it was the smallest node in the child of 40 . This is using the inorder successor approach.
Similarly the other approach is to take the highest node of the left child and place it at the root.
25
20 40
10 35 45
This is using the inorder predecessor approach.
File: "bst1.cpp"
// C++ program for different tree traversals#include <iostream>#include <queue>using namespace std;/* A binary tree Node has data, pointer to left childand a pointer to right child */struct Node { int data; struct Node *left, *right; Node(int data) { this->data = data; left = right = NULL; }};/* 1 2 34 5*/// function to search a given key in a given BSTstruct Node* search(struct Node* root, int key){ // Base Cases: root is null or key is present at root if (root == NULL || root->data == key) return root; // Key is greater than root's key if (root->data < key) return search(root->right, key); // Key is smaller than root's key return search(root->left, key);}/* Given a non-empty binary search tree, return the Nodewith minimum key value found in that tree. Note that theentire tree does not need to be searched. */struct Node* minValueNode(struct Node* Node){ struct Node* current = Node; /* loop down to find the leftmost leaf */ while (current && current->left != NULL) current = current->left; return current;}/* Given a binary search tree and a key, this functiondeletes the key and returns the new root */struct Node* deleteNode(struct Node* root, int key){ // base case if (root == NULL) return root; // If the key to be deleted is // smaller than the root's // key, then it lies in left subtree if (key < root->data) root->left = deleteNode(root->left, key); // If the key to be deleted is // greater than the root's // key, then it lies in right subtree else if (key > root->data) root->right = deleteNode(root->right, key); // if key is same as root's key, then This is the Node // to be deleted else { // Node has no child if (root->left==NULL and root->right==NULL) return NULL; // Node with only one child or no child else if (root->left == NULL) { struct Node* temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct Node* temp = root->left; free(root); return temp; } // Node with two children: Get the inorder successor // (smallest in the right subtree) struct Node* temp = minValueNode(root->right); // Copy the inorder successor's content to this Node root->data = temp->data ; // Delete the inorder successor root->right = deleteNode(root->right, temp->data ); } return root;}// Driver Code/* 4 2 51 3*//* Driver program to test above functions*/int main(){ struct Node* root = new Node(4); root->left = new Node(2); root->right = new Node(5); root->left->left = new Node(1); root->left->right = new Node(3); Node* result = search( root, 31 ) ; if ( result != NULL ) cout << "Found " << result->data ; else cout << "Not found." << endl ; root = deleteNode(root, 2 ) ; cout << root->data << endl ; cout << root->left->data << endl ; cout << root->right->data << endl ;}
Deletion
1)
20
15
10 18
Deleting the nodes 10, 18, 15, 20
Exercises
1) Create Binary search tree
Draw the binary trees when the nodes come in the following order.
a)
40 30 20 10
b)
30 20 10 25 40 35 45
2) Search , delete nodes print tree.
Show the paths taken to search for the values 30, 10, 35 , 37
Show the resulting tree when the nodes that are deleted are
10 , 40 , 30 .
The tree starts out in each case as the tree below.
a)
30
20 40
10 25 35 45
b)
30
20
10 25
Show the resulting tree when the node 30, 20 is deleted. Trace through the function deleteNode in each of these cases.
3) Write a function insertnode
Use this function to create a binary search tree.
4) Use maxValueNode instead of minValueNode to delete a node.
5) Print the tree by using BFS and keeping a variable level in the node so that the printout is readable.
6) What is the best case and worst case order for the search operation in a binary search tree.
AVL Trees
AVL Trees
https://www.youtube.com/watch?v=jDM6_TnYIqE&t=1630s
An AVL tree is a self balancing binary search tree. A binary search tree with nodes such as :
50,40,30,20,10 can be drawn as:
50
40
30
20
10
30
20 40
10 50
We notice that the first tree doesn't really offer us the benefit of binary search as it's the same as searching a linear array. We need a binary search to be sort of balanced in order to reduce the number of steps we take the for the worst case search. An AVL tree has the property that for any node the height of the left and right nodes must differ by at most one. We are going to go with the convention that a leaf node has a height of 1. We could also think of the leaf node as having a height of 0 . We have the balance factor of a node as height of left child - height of right child. The balance factor of an AVL tree must be within the range -1 and 1 for all the nodes.
For the above we have :
50 Height 5 Balance factor 4 ( height of left child 4 and height of right child 0 )
40 Height 4 Balance factor 3 ( height of left child 3 and height of right child 0 )
30 Height 3 Balance factor 2 ( height of left child 2 and height of right child 0 )
20 Height 2 Balance factor 1 ( height of left child 1 and height of right child 0 )
10 Height 1 Balance factor 0 ( null nodes have 0 height )
We are going to use the short hand notation (x,y) for height and balance factor
30 ( 3, 0 )
20 ( 2, 1 ) 40 ( 2, 1 )
10 ( 1, 0 ) 50 ( 1, 0 )
The first tree is clearly not balanced as the node 30 has the balance factor of 2. The balance factor indicates that one side is heavier than the other. The second tree is an AVL tree as the balance factor for each node is less than absolute of 1.
Exercises:
Find the height and balance factors of the below trees and determine if it an AVL tree or not.
1)
40
30 50
20
2)
40
30 50
20
10
3)
40
30 50
20 45
10
4)
40
30 50
20 45
Rotations
Let's say we insert a node in the 10 in the following :
30
20
10
That makes the above tree unbalanced. How can we correct it ? We perform a "rotation"
20
10 30
We can have 4 cases LL, RR, LR and RL unbalanced cases.
RR
10
20
30
LR
30
10
20
RL
10
30
20
For the LR and RL we have to do 2 rotations.
LR
30
10
20
First rotate around 10 .
30
20
10
and then rotate around 30 to get
20
10 30
What if the 3 nodes have subtrees ?
LL
30
20 T1
10 T2
Becomes
20
10 30
T2 T1
Similarly
RR
10
T1 20
T2 30
20
10 30
T1 T2
LR
30
10 T1
T2 20
T3 T4
20
10 30
T2 T3 T4 T1
RL
10
T1 30
20 T2
T3 T4
Exercise
1) Perform a RL rotation on the above and draw the resulting tree.
2)
20
10 40
25 50
22
Perform a RL rotation on node 20 .
3)
20
10 40
25 45
22
23
Which nodes are out of balance ?
Some Rules
If we insert a node; what unbalanced node do we correct ? First ancestor that becomes unbalanced is the node we correct.
If the ancestor is many levels above the inserted node such as in the following example:
20
10 30
25 40
22
We insert 22 . Now 20 becomes unbalanced and the operations are :
R L L
We only consider the left most 2 operations which are RL and work with those.
Inserting a node
We follow the normal rules of a binary search tree to do insertion. However inserting a node might produce an unbalanced nod in the ancestor and if that is the case then we correct that ancestor.
We are going to insert
40, 20, 10, 25, 30, 22, 50
40
40
20
10
40 is unbalanced as the left child has height 2 and right child ( null ) has height 0 .
LL Rotation gives us:
20
10 40
20
10 40
25
20
10 40
25
30
The node that becomes balanced is 40. We are doing
LR
20
10 30
25 40
Now we add 22 .
20
10 30
25 40
22
The node 20 becomes unbalanced. We added 22 so the path is
R L L
We only take the first 2 "RL" and ignore the rest.
25
20 30
10 22 40
We add 50 .
25
20 30
10 22 40
50
Now 30 becomes unbalanced and we do a RR .
25
20 40
10 22 30 50
Exercise
Show the tree creation when the following nodes are inserted.
1) 50,22,30,25,10,20,40
2) 30,25,10,20,50,22,40
3) 20,50,22,40,30,24,10
Deletion of a node.
Deletion is done by deleting a node using the BST method and then rebalancing the tree.
20
10 30
22 40
Delete 40 .
Since 40 is a leaf node we can delete it as it is and the ancestors are balanced.
Delete 30
We take the min value ( inorder successor ) of 40 and replace the 30 with that.
20
10 40
22
Delete 10
20
10 30
22 40
20
30
22 40
20 becomes unbalanced.
Following the implementation
// Right Right Case
if (balance < -1 &&
getBalance(root->right) <= 0)
return leftRotate(root);
The balance of 20 is -2 and the balance of 30 is 0 so do a RR .
30
20 40
22
Exercise
1)
20
10 30
5 11 22 40
7
Delete 11 . Then delete 20 from the modified tree. Then delete , 40 and 30. What is the resulting tree.
2)
20
10 30
5 40
Delete 40 and then from the modified tree delete 30 .
3)
20
10 30
15 40
Delete 30 and then from the modified tree delete 40 .
File: "avl1.cpp"
// C++ program to insert a node in AVL tree#include<bits/stdc++.h>using namespace std;// An AVL tree nodeclass Node { public: int key; Node *left; Node *right; int height;};// A utility function to get maximum// of two integersint max(int a, int b);// A utility function to get the// height of the treeint height(Node *N){ if (N == NULL) return 0; return N->height;}// A utility function to get maximum// of two integersint max(int a, int b){ return (a > b)? a : b;}/* Helper function that allocates anew node with the given key andNULL left and right pointers. */ Node* newNode(int key){ Node* node = new Node(); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; // new node is initially // added at leaf return(node);}// A utility function to right// rotate subtree rooted with y// See the diagram given above. Node *rightRotate(Node *y){ Node *x = y->left; Node *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; // Return new root return x;}// A utility function to left// rotate subtree rooted with x// See the diagram given above. Node *leftRotate(Node *x){ Node *y = x->right; Node *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; // Return new root return y;}// Get Balance factor of node Nint getBalance(Node *N){ if (N == NULL) return 0; return height(N->left) - height(N->right);}// Recursive function to insert a key// in the subtree rooted with node and// returns the new root of the subtree. Node* insert(Node* node, int key){ /* 1. Perform the normal BST insertion */ if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys are not allowed in BST return node; /* 2. Update height of this ancestor node */ node->height = 1 + max(height(node->left), height(node->right)); /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int balance = getBalance(node); // If this node becomes unbalanced, then // there are 4 cases // Left Left Case if (balance > 1 && key < node->left->key) return rightRotate(node); // Right Right Case if (balance < -1 && key > node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node;}// A utility function to print preorder// traversal of the tree.// The function also prints height// of every nodevoid preOrder(Node *root){ if(root != NULL) { cout << root->key << " "; preOrder(root->left); preOrder(root->right); }}/* Given a non-empty binary search tree,return the node with minimum key valuefound in that tree. Note that the entiretree does not need to be searched. */ Node * minValueNode(Node* node){ Node* current = node; /* loop down to find the leftmost leaf */ while (current->left != NULL) current = current->left; return current;}//----------------------------------------------------------------// Recursive function to delete a node// with given key from subtree with// given root. It returns root of the// modified subtree. Node* deleteNode(Node* root, int key){ // STEP 1: PERFORM STANDARD BST DELETE if (root == NULL) return root; // If the key to be deleted is smaller // than the root's key, then it lies // in left subtree if ( key < root->key ) root->left = deleteNode(root->left, key); // If the key to be deleted is greater // than the root's key, then it lies // in right subtree else if( key > root->key ) root->right = deleteNode(root->right, key); // if key is same as root's key, then // This is the node to be deleted else { // node with only one child or no child if( (root->left == NULL) || (root->right == NULL) ) { Node *temp = root->left ? root->left : root->right; // No child case if (temp == NULL) { temp = root; root = NULL; } else // One child case *root = *temp; // Copy the contents of // the non-empty child free(temp); } else { // node with two children: Get the inorder // successor (smallest in the right subtree) Node* temp = minValueNode(root->right); // Copy the inorder successor's // data to this node root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } } // If the tree had only one node // then return if (root == NULL) return root; // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE root->height = 1 + max(height(root->left), height(root->right)); // STEP 3: GET THE BALANCE FACTOR OF // THIS NODE (to check whether this // node became unbalanced) int balance = getBalance(root); // If this node becomes unbalanced, // then there are 4 cases // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } // Right Right Case if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); // Right Left Case if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root;}// Driver Codeint main(){ Node *root = NULL; /* Constructing tree given in the above figure */ root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); root = insert(root, 50); root = insert(root, 25); /* The constructed AVL Tree would be 30 / \ 20 40 / \ \ 10 25 50 */ cout << "Preorder traversal of the " "constructed AVL tree is \n"; preOrder(root); return 0;}// This code is contributed by// rathbhupendra
Red Black Trees
Red Black Trees
A Red Black tree is a binary search tree with the following properties.
Each node is either red or black.
All NIL nodes are considered black.
A red node does not have a red child.
Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
The NIL nodes are the NULL nodes. Some documentation insist that the root node is black but others do not. We are not going to list it as a requirement.
Example1:
B
B B
NULL NULL NULL NULL
The NULL nodes are considered black. The number of black nodes are 3 for each path. So it is a Red black tree.
B
R NULL
NULL NULL
The number of black nodes is 2 in the left case and 2 in the right child of the root so it is a RB tree. The following are Binary Search Trees . Determine if they can be RB trees . Try to color them and see if the properties of a RB tree are met.
Exercise
1) 50
40
30
2)
50
40 60
30
3)
50
40 60
30
35
4)
50
40 60
30 45 55 65
Can we have a RB tree that is not an AVL tree . Yes we can.
B
R B
B B
R
The above is a RB tree but not an AVL tree as the root is not balanced. In general a RB tree involves less rotations but may be more imbalanced than an AVL tree.
Insertion
Insertion involved doing a insertion first using the binary tree approach and then correcting it by rotations or re-coloring.
File: "rb1.cpp"
/** C++ implementation forRed-Black Tree Insertion **/#include <bits/stdc++.h>using namespace std;enum Color {RED, BLACK};struct Node { int data; bool color; Node *left, *right, *parent; // Constructor Node(int data) { this->data = data; left = right = parent = NULL; this->color = RED; }};// Class to represent Red-Black Treeclass RBTree {private: Node *root;protected: void rotateLeft(Node *&, Node *&); void rotateRight(Node *&, Node *&); void fixViolation(Node *&, Node *&);public: // Constructor RBTree() { root = NULL; } void insert(const int &n); void inorder(); void levelOrder();};// A recursive function to do inorder traversalvoid inorderHelper(Node *root){ if (root == NULL) return; inorderHelper(root->left); cout << root->data << " "; inorderHelper(root->right);}//------------------------------------------------------------/* A utility function to insert a new node with given keyin BST */ Node* BSTInsert(Node* root, Node *pt){ /* If the tree is empty, return a new node */ if (root == NULL) return pt; /* Otherwise, recur down the tree */ if (pt->data < root->data) { root->left = BSTInsert(root->left, pt); root->left->parent = root; } else if (pt->data > root->data) { root->right = BSTInsert(root->right, pt); root->right->parent = root; } /* return the (unchanged) node pointer */ return root;}//------------------------------------------------------------// Utility function to do level order traversalvoid levelOrderHelper(Node *root){ if (root == NULL) return; std::queue<Node *> q; q.push(root); while (!q.empty()) { Node *temp = q.front(); cout << temp->data << " "; q.pop(); if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); }}//------------------------------------------------------------void RBTree::rotateLeft(Node *&root, Node *&pt){ Node *pt_right = pt->right; pt->right = pt_right->left; if (pt->right != NULL) pt->right->parent = pt; pt_right->parent = pt->parent; if (pt->parent == NULL) root = pt_right; else if (pt == pt->parent->left) pt->parent->left = pt_right; else pt->parent->right = pt_right; pt_right->left = pt; pt->parent = pt_right;}//------------------------------------------------------------void RBTree::rotateRight(Node *&root, Node *&pt){ Node *pt_left = pt->left; pt->left = pt_left->right; if (pt->left != NULL) pt->left->parent = pt; pt_left->parent = pt->parent; if (pt->parent == NULL) root = pt_left; else if (pt == pt->parent->left) pt->parent->left = pt_left; else pt->parent->right = pt_left; pt_left->right = pt; pt->parent = pt_left;}//------------------------------------------------------------// This function fixes violations// caused by BST insertionvoid RBTree::fixViolation(Node *&root, Node *&pt){ Node *parent_pt = NULL; Node *grand_parent_pt = NULL; while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) { parent_pt = pt->parent; grand_parent_pt = pt->parent->parent; /* Case : A Parent of pt is left child of Grand-parent of pt */ if (parent_pt == grand_parent_pt->left) { Node *uncle_pt = grand_parent_pt->right; /* Case : 1 The uncle of pt is also red Only Recoloring required */ if (uncle_pt != NULL && uncle_pt->color == RED) { grand_parent_pt->color = RED; parent_pt->color = BLACK; uncle_pt->color = BLACK; pt = grand_parent_pt; } else { /* Case : 2 pt is right child of its parent Left-rotation required */ if (pt == parent_pt->right) { rotateLeft(root, parent_pt); pt = parent_pt; parent_pt = pt->parent; } /* Case : 3 pt is left child of its parent Right-rotation required */ rotateRight(root, grand_parent_pt); swap(parent_pt->color, grand_parent_pt->color); pt = parent_pt; } } /* Case : B Parent of pt is right child of Grand-parent of pt */ else { Node *uncle_pt = grand_parent_pt->left; /* Case : 1 The uncle of pt is also red Only Recoloring required */ if ((uncle_pt != NULL) && (uncle_pt->color == RED)) { grand_parent_pt->color = RED; parent_pt->color = BLACK; uncle_pt->color = BLACK; pt = grand_parent_pt; } else { /* Case : 2 pt is left child of its parent Right-rotation required */ if (pt == parent_pt->left) { rotateRight(root, parent_pt); pt = parent_pt; parent_pt = pt->parent; } /* Case : 3 pt is right child of its parent Left-rotation required */ rotateLeft(root, grand_parent_pt); swap(parent_pt->color, grand_parent_pt->color); pt = parent_pt; } } } root->color = BLACK;}//------------------------------------------------------------// Function to insert a new node with given datavoid RBTree::insert(const int &data){ Node *pt = new Node(data); // Do a normal BST insert root = BSTInsert(root, pt); // fix Red Black Tree violations fixViolation(root, pt);}//------------------------------------------------------------// Function to do inorder and level order traversalsvoid RBTree::inorder() { inorderHelper(root);}void RBTree::levelOrder() { levelOrderHelper(root); }//------------------------------------------------------------// Driver Codeint main(){ RBTree tree; tree.insert(7); tree.insert(6); tree.insert(5); tree.insert(4); tree.insert(3); tree.insert(2); tree.insert(1); cout << "Inoder Traversal of Created Tree\n"; tree.inorder(); cout << "\n\nLevel Order Traversal of Created Tree\n"; tree.levelOrder(); return 0;}
Exercises:
Show how the Red Black tree gets constructed ( using the above code ) for the following sequences.
1)
1, 2, 3, 4, 5, 6, 7
2)
4,5,6,7 , 1, 2, 3
3)
5,4,6 , 1, 7, 3, 2
M-way trees
https://www.youtube.com/watch?v=aZjYr87r1b8&t=1135s
A M-way tree is a generalized version of a binary tree. It can have multiple keys and children. A M-way tree of order m has m-1 keys and m children .
Example:
File: "m-way.cpp
#include <bits/stdc++.h>using namespace std;#define MAX 2struct node { int count; int value[MAX + 1]; //2 keys struct node* child[MAX + 1]; //3 children node() { for( int i1=0 ; i1<= MAX ; i1++ ) { value[i1] = 0 ; child[ i1 ] = NULL ; } }//node};//-----------------------------------------------------------------int searchnode( int val, struct node* n, int* pos ) ;// Searches value in the nodestruct node* search(int val, struct node* root, int* pos){ // if root is Null then return if (root == NULL) return NULL; else { // if node is found if (searchnode(val, root, pos)) return root; // if not then search in child nodes else return search(val, root->child[*pos], pos); }}//-----------------------------------------------------------------// Searches the nodeint searchnode(int val, struct node* n, int* pos){ // if val is less than node->value[1] if ( val < n->value[1] ) { *pos = 0; return 0; } // if the val is greater else { *pos = n->count; // check in the child array // for correct position while ((val < n->value[*pos]) && *pos > 1) (*pos)--; if (val == n->value[*pos]) return 1; else return 0; }}//-----------------------------------------------------------------// Driver Code// 18, 44// 7,12 19,21 262//x x x x x x x xint main(){ node* root = new node() ; root->value[0] = 0 ; root->value[1] = 18 ; root->value[2] = 44 ; root->count = 2 ; node* node1= new node() ; node1->value[0] = 0 ; node1->value[1] = 7 ; node1->value[2] = 12 ; node1->count = 2 ; node* node2 = new node() ; node2->value[0] = 0 ; node2->value[1] = 19 ; node2->value[2] = 21 ; node2->count = 2 ; node* node3 = new node() ; node3->value[0] = 0 ; node3->value[1] = 262 ; node3->count = 1 ; root->child[ 0 ] = node1 ; root->child[ 1 ] = node2 ; root->child[ 2 ] = node3 ; int pos ; node* ptr = search( 7,root, &pos ) ; cout << ptr->value[1] << endl ; return 0;}//-----------------------------------------------------------------
B Trees
A B tree is a M-way tree but with some constraints
1) A node must have upper m/2 child nodes.
2) The root node can have minimum 2 nodes
3) All leaf nodes must be at the same level.
Output:
Page updated
Google Sites
Report abuse