Module 3 (Self Balancing BST)
Self-balancing BST is a binary tree that performs balancing on its own (during operation). In this case, the balancing aims for the height difference between two adjacent sub-trees to be as little as possible during insertion or deletion. Self-balancing BST structure is often used to accelerate lookup in a binary tree. By using self-balancing BST, we can achieve time complexity as little as O(log n).
There are multiple variations of a self-balancing BST: Red Black Trees, AVL Trees, and B-Trees are some of them. Each of these variations has certain conditions in performing self-balancing. In a Red Black Tree, the balancing method uses the property of red/black color for each node.
On C++ Language, STL container std::set and std::map use Red-Black Tree on implementing self-balancing BST.
Red-Black Tree illustration. Source: https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/1200px-Red-black_tree_example.svg.png
In an AVL Tree, balancing is decided based on the height difference between the right and left children. To keep the height balanced, an AVL Tree needs to perform node rotation during insertion and deletion. This module will specifically delve further into AVL Tree.