/** * C++ Program to Implement Self Balancing Binary Search Tree. * * Code taken from: * https://www.sanfoundry.com/cpp-program-implement-self-balancing-binary-tree/ * Please ensure the original source is referenced, if you copy this code. * * This doesn't run well in SoloLearn's Code Playground. It is best * to try this code in another C++ build system. I (Xan) have just shown it * here as an example. * * Note: The original code gave some 'dangling else' compiler warnings. I * have fixed these. Otherwise, the rest of the code is as I found it. */ #include #include 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<data<<" "; inorder(r->right); } } /* Function for preorder traversal */ void preorder() { preorder(root); } void preorder(SBBSTNode *r) { if (r != NULL) { cout<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<data<<" "; } } }; int main() { SelfBalancingBinarySearchTree sbbst; cout<<"SelfBalancingBinarySearchTree Test\n"; int val; char ch; /* Perform tree operations */ do { cout<<"\nSelfBalancingBinarySearchTree Operations\n"; cout<<"1. Insert "<>choice; switch (choice) { case 1 : cout<<"Enter integer element to insert: "; cin>>val; sbbst.insert(val); break; case 2 : cout<<"Nodes = " <>val; if (sbbst.search(val)) cout<>ch; } while (ch == 'Y'|| ch == 'y'); return 0; }

Balanced Binary Tree