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.

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

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS