What is the difference between BST and self-balancing BST?

A binary search tree (BST) is a tree in which every node has exactly two children (left and right), every node’s left child has a smaller value than the node, and every node’s right child has a larger value than the node.

Let’s look at the following BST.

You can see that at each level of the tree, a node either has no child, one child, or two children. When the height of the children nodes differs by more than 1, the BST is considered unbalanced.

Where there is a null child (i.e., no child is present), the height is taken to be -1.

A balanced BST, then, is a tree where the heights of the children nodes differ by at max 1, as shown in the example below.

Self-balancing binary search tree

A self-balancing binary search tree is a type of BST which tries to balance itself, in case of arbitrary insertions and deletions, by using rotations.

For example, consider the following BST.

Now, the last value entered in the tree is 80. If this were a self-balancing BST, it would do some rotation to make the tree balanced. That rotation is shown below.

We can see that the self-balancing BST balances itself by making the parent node a grandparent and moving the grandparent as a left child. Now, the tree is balanced.

The following are some of the types of self-balancing binary search trees:

• Red-black tree
• AVL tree
• 2-3 tree
• Scapegoat tree
• Splay tree