Balanced BST, Explained and Illustrated
If we store collisions inside a linked list and the list grows long, the search operation becomes O(n). However, if we use a binary search tree, we\'ll have O(l
If we store collisions inside a linked list and the list grows long, the search operation becomes `O(n)`. However, if we use a binary search tree, we\'ll have `O(logn)` search.\n\nThe problem is that if we don\'t balance the tree, it may become as uneffective as linked list.\n\n## Introduction to weight-balanced trees\n\nWeight-balanced trees are a data structure that allows balancing. Let\'s look at the type we use to represent a WBT node:\n\n```\nstruct wbtnode\n{\n        int value;\n        struct wbtnode *left, *right;\n        int height;\n};\n```\n\nWe need `height` to be able to tell whether the tree is balanced or not. To do that, the following formula is used:\n\n```\nweight = rightSubtreeHeight - leftSubtreeHeight\n```\n\n* If `weight` is a negative number, the left subtree is taller than the right one;\n* if `weight` is a positive number, the right subtree is taller that the left one;\n* if `weight` is `0`, the tree is balanced.\n\n## Balancing\n\nBalancing operation is applied after each insertion and removal. That way we limit the number of possible different states an unbalanced tree can take to only 4. Let\'s consider them all in turn.\n\n### Left subtree is taller (1/4)\n\nConsider the following tree:\n\n![image](https://assets.leetcode.com/users/images/69190438-7b48-4cdc-b089-eca2c1e1f479_1651282512.4543638.jpeg)\n\nThe root node has weight `2 - 4 = -2`. That means the left subtree is taller than the right one.\n\nTo balance the tree, we organize the tree in such a way that `40` becomes the new root. And the tree takes the following form:\n\n![image](https://assets.leetcode.com/users/images/a2b9ad02-af1a-4a88-8bd7-55c7ce1a57f7_1651282800.712059.jpeg)\n\nNow the root tree has weight `3 - 3 = 0`.\n\nVisually the operation looks like clockwise rotation.\n\n### Left subtree is taller: continued (2/4)\n\nIt turns out the aforemention operation may not always work when the left subtree is the taller than the right one. Consider the following case:\n\n![image](https://assets.leetcode.com/users/images/f638e913-bcf8-4075-88d7-c21e95e688a1_1651283077.5214343.jpeg)\n\nIf we apply this operation, we\'d get the following tree:\n\n![image](https://assets.leetcode.com/users/images/a9a6bd47-f355-4d91-ada5-b4d7e27619bf_1651283146.9806454.jpeg)\n\nWhy does that happen?\n\nNotice that in the previous example the left subtree has weight `-1` and in this example it is `1`.\n\nThe previous example has worked out because we *raised the node that caused the unbalance*. This example failed because the node causing the unbalance stays that way.\n\nWe can balance this tree in two operations. First, move the node causing the unbalance to the left subtree of the left subtree, this way:\n\n![image](https://assets.leetcode.com/users/images/315c8296-1e8a-483f-be0c-2bc370252b26_1651283631.5510902.jpeg)\n\nWe\'ll get this:\n\n![image](https://assets.leetcode.com/users/images/c2b5dac5-f591-4a6b-b675-c7581f470f11_1651283682.8371248.jpeg)\n\nAnd we already know from the first case how to deal with this kind of unbalance.\n\n### Right subtree is taller (3/4)\n\nConsider the following tree:\n\n![image](https://assets.leetcode.com/users/images/efdffed5-ea6d-4a5e-9a13-bdd6c5bf3ae1_1651284001.7325473.jpeg)\n\nBalancing operation is analogous to the one presented in the first case.\n\n### Right subtree is taller (4/4)\n\nThis case, as well as the balancing operation, is analogous to the one presented in the second case:\n\n![image](https://assets.leetcode.com/users/images/7a730498-6373-4ca9-943a-d8b8f2e1d60c_1651284105.8655593.jpeg)\n\nThe tree becomes:\n\n![image](https://assets.leetcode.com/users/images/cb06f9db-989c-4092-9745-018810002663_1651284197.6211088.jpeg)\n\nAnd we already know how to deal with this kind of unbalance from the previous case.\n\n### Balancing: conclusion\n\n4 different cases may look unfriendly but in fact we only used two operations to do all balancing: clockwise rotation and counterclockwise rotation.\n\n## Removing\n\nRemoving an element is trivial. Consider the following tree:\n\n![image](https://assets.leetcode.com/users/images/1919a662-e025-43bb-aa78-06e19c7a6ad2_1651284531.9158728.jpeg)\n\nTo remove `80`, we should put either `70` or `90` on its place. And the tree would remain a correct BST.\n\n## Code\n\n```c\n// NHASH is the number of buckets.\n//\n#define NHASH 500\n\nstruct wbtnode\n{\n        int value;\n        struct wbtnode *left, *right;\n        int height;\n};\n\ntypedef struct\n{\n        struct wbtnode **dic;\n} MyHashSet;\n\nint min(int a, int b) { return a<b ? a : b; }\nint max(int a, int b) { return a>b ? a : b; }\n\nstruct wbtnode *\nwbtNewNode(int value, struct wbtnode *left, struct wbtnode *right, int height)\n{\n        struct wbtnode *out;\n        out = calloc(1, sizeof(*out));\n        out->value = value;\n        out->left = left;\n        out->right = right;\n        out->height = height;\n        return out;\n}\n\nint\nwbtHeight(struct wbtnode *head)\n{\n        if (!head)\n                return 0;\n        else\n                return head->height;\n}\n\nvoid\nwbtRebuildHeight(struct wbtnode *head)\n{\n        int le = wbtHeight(head->left);\n        int ri = wbtHeight(head->right);\n        head->height = 1 + max(le, ri);\n}\n\nint\nwbtWeight(struct wbtnode *head)\n{\n        if (!head)\n                return 0;\n        else\n                return wbtHeight(head->right) - wbtHeight(head->left);\n}\n\nstruct wbtnode *\nwbtRotLeftClockwise(struct wbtnode *head)\n{\n        struct wbtnode *oldhead = head;\n        head = head->left;\n\n        oldhead->left = head->right;\n        head->right = oldhead;\n\n        wbtRebuildHeight(oldhead);\n        wbtRebuildHeight(head);\n        return head;\n}\n\nstruct wbtnode *\nwbtRotRightCounterclockwise(struct wbtnode *head)\n{\n        struct wbtnode *oldhead = head;\n        head = head->right;\n\n        oldhead->right = head->left;\n        head->left = oldhead;\n\n        wbtRebuildHeight(oldhead);\n        wbtRebuildHeight(head);\n        return head;\n}\n\nstruct wbtnode *\nwbtRebalance(struct wbtnode *head)\n{\n        int hw = wbtWeight(head);\n        int lw = wbtWeight(head->left);\n        int rw = wbtWeight(head->right);\n        if (hw < 0 && lw == -1) {\n                head = wbtRotLeftClockwise(head);\n        } else if (hw < 0 && lw == 1) {\n                head->left = wbtRotRightCounterclockwise(head->left);\n                head = wbtRotLeftClockwise(head);\n        } else if (hw > 0 && rw == 1) {\n                head = wbtRotRightCounterclockwise(head);\n        } else if (hw > 0 && rw == -1) {\n                head->right = wbtRotLeftClockwise(head->right);\n                head = wbtRotRightCounterclockwise(head);\n        }\n        return head;\n}\n\n// wbtPut adds a new element to the tree and rebalances it. If the element is already\n// present in the tree, wbtPut does nothing.\n//\nstruct wbtnode *\nwbtPut(struct wbtnode *head, int value, int *found)\n{\n        if (!head)\n                return wbtNewNode(value, NULL, NULL, 1);\n        if (head->value == value) {\n                *found = 1;\n                return head;\n        }\n        if (head->value > value)\n                head->left = wbtPut(head->left, value, found);\n        else\n                head->right = wbtPut(head->right, value, found);\n        if (!*found) {\n                wbtRebuildHeight(head);\n                head = wbtRebalance(head);\n        }\n        return head;\n}\n\n// wbtRmLeftmost removes a leftmost node of a subtree and stores it in removed.\n//\nstruct wbtnode *\nwbtRmLeftmost(struct wbtnode *head, struct wbtnode **removed)\n{\n        if (!head->left) {\n                *removed = head;\n                return head->right;\n        }\n        head->left = wbtRmLeftmost(head->left, removed);\n        wbtRebuildHeight(head);\n        head = wbtRebalance(head);\n        return head;\n}\n\n// wbtRmRightmost removes a rightmost node of a subtree and stores it in removed.\n//\nstruct wbtnode *\nwbtRmRightmost(struct wbtnode *head, struct wbtnode **removed)\n{\n        if (!head->right) {\n                *removed = head;\n                return head->left;\n        }\n        head->right = wbtRmRightmost(head->right, removed);\n        wbtRebuildHeight(head);\n        head = wbtRebalance(head);\n        return head;\n}\n\n// wbtRemove removes a node from the tree and rebalances the tree. If the value\n// was not found in the tree, wbtRemove does nothing.\n//\nstruct wbtnode *\nwbtRemove(struct wbtnode *head, int value, int *found)\n{\n        if (!head) {\n                return NULL;\n        }\n        if (head->value == value) {\n                *found = 1;\n\n                // If the node doesn\'t have any subtrees, just remove the node.\n                //\n                if (!head->left && !head->right)\n                        return NULL;\n\n                // Otherwise, replace the removing node with a one from its subtrees.\n                //\n                struct wbtnode *newroot = NULL;\n                if (head->left)\n                        head->left = wbtRmRightmost(head->left, &newroot);\n                else\n                        head->right = wbtRmLeftmost(head->right, &newroot);\n                newroot->left = head->left;\n                newroot->right = head->right;\n                free(head);\n                head = newroot;\n                wbtRebuildHeight(head);\n                head = wbtRebalance(head);\n                return head;\n        }\n        if (head->value > value)\n                head->left = wbtRemove(head->left, value, found);\n        else\n                head->right = wbtRemove(head->right, value, found);\n        if (*found) {\n                wbtRebuildHeight(head);\n                head = wbtRebalance(head);\n        }\n        return head;\n}\n\nstruct wbtnode *\nwbtFind(struct wbtnode *head, int value)\n{\n        if (!head)\n                return NULL;\n        if (head->value == value)\n                return head;\n        if (head->value > value)\n                return wbtFind(head->left, value);\n        else\n                return wbtFind(head->right, value);\n}\n\nvoid\nwbtFree(struct wbtnode *head)\n{\n        if (!head)\n                return;\n        wbtFree(head->left);\n        wbtFree(head->right);\n        free(head);\n}\n\nint\nhsHash(int key)\n{\n        return key % NHASH;\n}\n\nMyHashSet *\nmyHashSetCreate()\n{\n        MyHashSet *hs;\n        hs = calloc(1, sizeof(*hs));\n        hs->dic = calloc(NHASH, sizeof(*hs->dic));\n        return hs;\n}\n\nvoid\nmyHashSetAdd(MyHashSet *hs, int k)\n{\n        struct wbtnode *head = hs->dic[hsHash(k)];\n\n        int found = 0;\n        hs->dic[hsHash(k)] = wbtPut(head, k, &found);\n}\n\nvoid\nmyHashSetRemove(MyHashSet *hs, int k)\n{\n        struct wbtnode *head = hs->dic[hsHash(k)];\n\n        int found = 0;\n        hs->dic[hsHash(k)] = wbtRemove(head, k, &found);\n}\n\nbool\nmyHashSetContains(MyHashSet *hs, int k)\n{\n        struct wbtnode *head = hs->dic[hsHash(k)];\n\n        return !!wbtFind(head, k);\n}\n\nvoid\nmyHashSetFree(MyHashSet *hs)\n{\n        struct wbtnode **p;\n        for (p = hs->dic; p != hs->dic+NHASH; p++)\n                wbtFree(*p);\n        free(hs);\n}\n```
['Binary Search Tree', 'C']