C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Implement Self Balancing Binary Search Tree Program to Implement Self Balancing Binary Search Tree This C++ Program demonstrates the implementation of Self Balancing Binary Search Tree. #include <iostream> #include <cstdlib> using namespace std; /* Class SBBSTNode */ class SBBSTNode { public: int height, data; SBBSTNode *left, *right; /* Constructor */ SBBSTNode() { left = NULL; right = NULL; data = 0; height = 0; } /* Constructor */ SBBSTNode(int n) { left = NULL; right = NULL; data = n; height = 0; } }; /* Class SelfBalancingBinarySearchTree */ class SelfBalancingBinarySearchTree { private: SBBSTNode *root; public: /* Constructor */ SelfBalancingBinarySearchTree() { root = NULL; } /* Function to check if tree is empty */ bool isEmpty() { return root == NULL; } /* Make the tree logically empty */ void makeEmpty() { root = NULL; } /* Function to insert data */ void insert(int data) { root = insert(data, root); } /* Function to get height of node */ int height(SBBSTNode *t) { return t == NULL ? -1 : t->height; } /* Function to max of left/right node */ int max(int lhs, int rhs) { return lhs > rhs ? lhs : rhs; } /* Function to insert data recursively */ SBBSTNode *insert(int x, SBBSTNode *t) { if (t == NULL) t = new SBBSTNode(x); else if (x < t->data) { t->left = insert(x, t->left); if (height(t->left) - height(t->right) == 2) if (x < t->left->data) t = rotateWithLeftChild(t); else t = doubleWithLeftChild(t); } else if (x > t->data) { t->right = insert(x, t->right); if (height(t->right) - height(t->left) == 2) if (x > t->right->data) t = rotateWithRightChild(t); else t = doubleWithRightChild(t); } t->height = max(height(t->left), height(t->right)) + 1; return t; } /* Rotate binary tree node with left child */ SBBSTNode *rotateWithLeftChild(SBBSTNode* k2) { SBBSTNode *k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max(height(k2->left), height(k2->right)) + 1; k1->height = max(height(k1->left), k2->height) + 1; return k1; } /* Rotate binary tree node with right child */ SBBSTNode *rotateWithRightChild(SBBSTNode *k1) { SBBSTNode *k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = max(height(k1->left), height(k1->right)) + 1; k2->height = max(height(k2->right), k1->height) + 1; return k2; } /* Double rotate binary tree node: first left child with its right child; then node k3 with new left child */ SBBSTNode *doubleWithLeftChild(SBBSTNode *k3) { k3->left = rotateWithRightChild(k3->left); return rotateWithLeftChild(k3); } /* Double rotate binary tree node: first right child with its left child; then node k1 with new right child */ SBBSTNode *doubleWithRightChild(SBBSTNode *k1) { k1->right = rotateWithLeftChild(k1->right); return rotateWithRightChild(k1); } /* Functions to count number of nodes */ int countNodes() { return countNodes(root); } int countNodes(SBBSTNode *r) { if (r == NULL) return 0; else { int l = 1; l += countNodes(r->left); l += countNodes(r->right); return l; } } /* Functions to search for an element */ bool search(int val) { return search(root, val); } bool search(SBBSTNode *r, int val) { bool found = false; while ((r != NULL) && !found) { int rval = r->data; if (val < rval) r = r->left; else if (val > rval) r = r->right; else { found = true; break; } found = search(r, val); } return found; } /* Function for inorder traversal */ void inorder() { inorder(root); } void inorder(SBBSTNode *r) { if (r != NULL) { inorder(r->left); cout<<r->data<<" "; inorder(r->right); } } /* Function for preorder traversal */ void preorder() { preorder(root); } void preorder(SBBSTNode *r) { if (r != NULL) { cout<<r->data<<" "; preorder(r->left); preorder(r->right); } } /* Function for postorder traversal */ void postorder() { postorder(root); } void postorder(SBBSTNode *r) { if (r != NULL) { postorder(r->left); postorder(r->right); cout<<r->data<<" "; } } }; int main() { SelfBalancingBinarySearchTree sbbst; cout<<"SelfBalancingBinarySearchTree Test\n"; int val; char ch; /* Perform tree operations */ do { cout<<"\nSelfBalancingBinarySearchTree Operations\n"; cout<<"1. Insert "<<endl; cout<<"2. Count nodes"<<endl; cout<<"3. Search"<<endl; cout<<"4. Check empty"<<endl; cout<<"5. Make empty"<<endl; int choice; cout<<"Enter your Choice: "; cin>>choice; switch (choice) { case 1 : cout<<"Enter integer element to insert: "; cin>>val; sbbst.insert(val); break; case 2 : cout<<"Nodes = " <<sbbst.countNodes()<<endl; break; case 3: cout<<"Enter integer element to search: "; cin>>val; if (sbbst.search(val)) cout<<val<<" found in the tree"<<endl; else cout<<val<<" not found"<<endl; break; case 4 : cout<<"Empty status = "; if (sbbst.isEmpty()) cout<<"Tree is empty"<<endl; else cout<<"Tree is non - empty"<<endl; break; case 5 : cout<<"\nTree cleared\n"; sbbst.makeEmpty(); break; default : cout<<"Wrong Entry \n "; break; } /* Display tree*/ cout<<"\nPost order : "; sbbst.postorder(); cout<<"\nPre order : "; sbbst.preorder(); cout<<"\nIn order : "; sbbst.inorder(); cout<<"\nDo you want to continue (Type y or n): "; cin>>ch; } while (ch == 'Y'|| ch == 'y'); return 0; }
