A self-balanced binary search tree or height-balance binary search tree is a special type of binary search tree that attempts to keep the height or number of levels of the tree as small as possible all the time by adjusting automatically. For example, the following diagram shows a binary search tree on the left and a the self-balanced binary search tree on the right:

A height-balanced binary tree is always better as it helps search operations faster compared to a regular BST. There are different implementations of self-balanced or height-balanced binary search trees. Some of the popular ones are as follows:

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

We will discuss few of the height-balanced trees in the following sections.