Tim Koval
Geek; Embedded Systems Developer; Firmware, Hardware and System Software Engineer;

BST and AVL Trees

In this article I am going to continue 6.006 course observation. As you can notice, the topic is about Binary Search Trees and AVL trees (self-balancing binary trees).

Binary Search Tree – node based binary (each node can have no more than two children) tree.

Node properties:

  • Each node has a value/key inside;
  • Other than root nodes have a parent ;
  • Nodes may have a left and/or right child;
  • Every node in the right subtree are always bigger than the current node;
  • Every node in the the left subtree are always smaller than the current node.

According to the given properties of the node we can understand how to implement the main operations needed.

Insertion: Follow left and right pointers till you reach the position that fits last 2 properties.

Search: Follow left and right pointers until you find the element or null – if the searching element is not in the tree.

Find minimum element: Go left till you cannot go left anymore.

Next larger element: If the node x has right child, you should return minimum element of the x subtree, else go up while you are not on the root or x is not the left child.

Complexity: Generally, all operations with the BST takes O(h) amount of time, where h is a height of the tree (the path from the root to the furthest leaf). h will be log(n) for perfectly balanced tree on the picture given below. However, it may become O(n) if tree is not balanced (looks like a simple path).

Given that, you can understand that it is very important to make your tree balanced. So let’s consider AVL trees or Balanced BST.

AVL tree specific properties:

  • Every node stores it’s height;
  • Every node’s children heights differ at most by 1;
  • Treat empty tree as height -1.

For the insertion operation it is needed to insert it as we did for BST and restore AVL property step-by-step:

  • suppose x is lowest node violating AVL
  • assume x is right-heavy (left case symmetric)
  • if x‘s right child is right-heavy or balanced:
  • else:
  • then continue up to x‘s grandparents till the root.

Example:

I suggest you to make a conclusion by yourself, but I want just say that binary trees are often useful to make your algorithms much faster.

As you could see, I decided not to use any programming language and I hope it will help you to understand the given algorithms even if you don’t use C/C++ in your life.

Information for this post has been taken from the MIT OCW course 6.006 “Introduction to Algorithms”

Share

You may also like...

Leave a Reply