Self Balancing Binary Search Trees

How Self Balancing Binary Search Trees can be Balanced

To balance the binary tree, the height of the left and right node should differ by -1,0,1, known as the balance factor.

Balance Factor(bf): Height of Left Subtree(lf)- Height of Right Subtree(rf).

For self-balancing BST, we perform some rotations after performing insert and delete operations—two types of rotations.

Left Rotation

Left rotations (and right) are order-preserving in a binary search tree; it preserves its property.

In a BST, a left rotation is the movement of a node, T, down to the left. We are rotating the mentioned nodes from their left. Here we assume that X has a right child or right subtree. T's right child, R, becomes T's parent node, and R's left child becomes T's new right child. We have done rotation to balance the tree.

Source: Baeldung

Right Rotation

Proper rotations (and left) are order-preserving in a binary search tree; it preserves its property.

In BST, a right rotation is the movement of a node, (T), down to the right. This rotation assumes that T has a left subtree. T's left child, R, becomes T's parent node, and R's right child becomes T's new left child. We have done rotation to balance the tree.

Source: Baeldung

Types of Self-Balancing Binary Search Trees

There are a few types of self-balancing bst.

1. Red Black Tree
2. AVL Tree
3. Splay Trees

Red Black Tree

A red-black tree is a self-balancing BST that nodes two black or red colors. These colors need to remain balanced after insertion and deletion operations. A Red-Black tree's height(h) is always O(log n), where n is the number of nodes. 

Most of the BST operations take O(h) time, where h is the height of the BST. 

AVL Tree

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right child or subtrees cannot be more than one for all nodes.

Most of the BST operations take O(h) time, where h is the height of the BST.  

Splay Tree

A splay tree is a BST with the additional property that recently accessed elements quickly access again. Like self-balancing BST, a splay tree performs basic operations such as insertion, look-up, and removal in O(log n) amortized time.

Comparisons

We will be comparing the self-balancing binary search trees- Red Black Tree, AVL Tree, and Splay Tree based on their operations. 

You can also read about insertion into bst.

FAQs

1. Which self-balancing tree is best for insertions and deletions?
   The AVL and Red-Black trees are useful for getting all basic operations(like insertion, deletion, etc.) done in O(log n) time. Here the AVL trees are more balanced compared to Red-Black Trees, but there is one problem that they may cause more rotations during insertion and deletion.
    
2. What is the maximum height of the AVL tree?
   The maximum height of the AVL tree is 1.44*logn.
    
3. How do Self-Balancing-Tree maintain height? 
   Self-Balancing-Tree maintains height by performing rotations after every operation.

Key Takeaways

This article has covered the following things:

• What are the self-balancing binary search trees, and how are they different from binary search trees.
• How self-balancing binary search trees can be balanced.
• What are the types of self-balancing binary search trees?
• Comparisons between the different types of trees.

You can look towards the insertion operation of the self-balancing binary search trees- Red-Black Trees, AVL Trees.

Check out this problem - Mirror A Binary Tree

Don't forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Coding Ninjas Studio. 

Happy Coding!!!