A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:

  • The left sub-tree of a node has a key less than or equal to its parent node's key.
  • The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST

                               

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Basic Operations

 Following are the basic operations of a tree

  • Search − Searches an element in a tree.
  • Insert − Inserts an element in a tree.
  • Pre-order Traversal − Traverses a tree in a pre-order manner.
  • In-order Traversal − Traverses a tree in an in-order manner.
  • Post-order Traversal − Traverses a tree in a post-order manner.

Insertion in a BST

To insert data into a binary tree involves a function searching for an unused node in the proper position in the tree in which to insert the key value.

The insert function is generally a recursive function that continues moving down the levels of a binary tree until there is an unused leaf in a position which follows the following rules of placing nodes.

  • Compare data of the root node and element to be inserted.
  • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,
  • Insert element as left child of current root.
  • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree.
  • Else, insert element as right child of current root.

AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1.

Balance Factor

Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node.

Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree)

The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

An example of a balanced avl tree is:

                           

Rotations in AVL Tree

 To balance itself, an AVL tree may perform the following four kinds of rotations −

  1. Left rotation
  2. Right rotation
  3. Left-Right rotation
  4. Right-Left rotation

The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's understand them one by one.

1.  Left Rotation

 If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation

In our example, node A has become unbalanced as a node is inserted in the right subtree of A's right subtree. We perform the left rotation by making A the left-subtree of B.

2.  Right Rotation

 AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right rotation.

As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.

3.  Left-Right Rotation

Double rotations are slightly complex version of already explained versions of rotations. To understand them better, we should take note of each action performed while rotation.

Let's first check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation followed by right rotation.

State

Action

 

 

A node has been inserted into the right subtree of the left subtree. This makes C an unbalanced node. These scenarios cause AVL tree to perform left-right rotation.

 

 

We first perform the left rotation on the left subtree of C. This makes A, the left subtree of B.

 

 

Node C is still unbalanced, however now, it is because of the left-subtree of the left-subtree.

 

 

We shall now right-rotate the tree, making B the new root node of this subtree. C now becomes the right subtree of its own left subtree.

 

 

The tree is now balanced.

4.  Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by left rotation.

State

Action
     

 

 

A node has been inserted into the left subtree of the right subtree. This makes A, an unbalanced node with balance factor 2.

 

 

First, we perform the right rotation along C node, making C the right subtree of its own left subtree B. Now, B becomes the right subtree of A.

 

 

Node A is still unbalanced because of the right subtree of its right subtree and requires a left rotation.

 

 

A left rotation is performed by making B the new root node of the subtree. A becomes the left subtree of its right subtree B.

 

The tree is now balanced.

 

Algorithm to Insert a new Node

A newNode is always inserted as a leaf node with balance factor equal to 0.

  1. Let the initial tree be:

                             

Let the node to be inserted be:

                                                       

2. Go to the appropriate leaf node to insert a newNode using the following recursive steps. Compare newKey with rootKey of current tree.

    1. If newKey < rootKey, call insertion algorithm on left subtree of current node until the leaf node is reached.
    2. Else if newKey > rootKey, call insertion algorithm on the right subtree of current node until the leaf node is reached.
    3. Else, return leafNode.

                     

3. Compare leafKey obtained from above steps with newKey:

    1. If newKey < leafKey, make newNode as the leftChild of leafNode.
    2. Else, make newNode as rightChild of leafNode.

                                     

4. Update balanceFactor of the nodes.

                               

5. If the nodes are unbalanced, then rebalance the node.

  1. If balanceFactor > 1, it means the height of the left subtree is greater than that of the right So, do right rotation or left-right rotation 
  1. If newNodeKey < leftChildKey do right rotation.
  2. Else, do left-right rotation.

 

b. If balanceFactor < -1, it means the height of the right subtree is greater than that of the left So, do right rotation or right-left rotation

  1. If newNodeKey > rightChildKey do left rotation.
  2. Else, do right-left rotation

6. The final tree is:

                       

Algorithm to Delete a Node

 A node is always deleted as a leaf node. After deleting a node, the balance factors of the nodes get changed. In order to rebalance the balance factor, suitable rotations are performed.

  1. Locate nodeToBeDeleted (recursion is used to find nodeToBeDeleted in the code used below).
  2. There are three cases for deleting a node:
    1. If nodeToBeDeleted is the leaf node (ie. does not have any child), then remove

    nodeToBeDeleted.

    1. If nodeToBeDeleted has one child, then substitute the contents of

    nodeToBeDeleted with that of child. Remove the child.

    1. If nodeToBeDeleted has two children, find the inorder successor w of

    nodeToBeDeleted (ie. node with minimum value of key in the right subtree).                                          

  1. Substitute the contents of nodeToBeDeleted with that of w.
  2. Remove the leaf node w.

         

3. Update balanceFactor of the nodes.

4. Rebalance the tree if balance factor of any of the nodes is not equal to -1, 0 or 1.

    1. If balanceFactor of currentNode > 1,
    2. If balanceFactor of leftChild >= 0, do right rotation.

Else do left-right rotation.

 

              3. If balanceFactor of currentNode < -1,

  • If balanceFactor of rightChild <= 0, do left rotation.
  • Else do right-left rotation.

5. The final tree is:

                 

                   

Searching in a BST

The search function works in a similar fashion as insert. It will check if the key value of the current node is the value to be searched.

If not, it should check to see if the value to be searched for is less than the value of the node, in which case it should be recursively called on the left child node, or if it is greater than the value of the node, it should be recursively called on the right child node.

  • Compare data of the root node and the value to be searched.
  • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,
  • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree. Else,
  • If the value to be searched is equal to the data of root node, return true.
  • Else, return false.

Traversing in a BST

There are mainly three types of tree traversals:

1. Pre-order Traversal:

 In this technique, we do the following:

  • Process data of root node.
  • First, traverse left subtree completely.
  • Then, traverse right subtree.

2. Post-order Traversal

 In this traversal technique we do the following:

  • First traverse left subtree completely.
  • Then, traverse right subtree completely.
  • Then, process data of node.

3. In-order Traversal

 In in-order traversal, we do the following:

  • First process left subtree.
  • Then, process current root node.
  • Then, process right subtree.

Complexity Analysis of BST

The time complexity of search and insert rely on the height of the tree. On average, binary search trees with n nodes have O(log n) height. However in the worst case the tree can have a height of O(n) when the unbalanced tree resembles a linked list. For example in this case:

         

Traversal requires O (n) time, since every node must be visited.