Rebalancing a Binary Search Tree

There are numerous ways to keep a binary search tree in relatively good balance. One of them is to employ the AVL tree balancing algorithms. The advantage to such algorithms are that the tree stays fairly well-balanced whenever nodes are added or deleted. However, sometimes we have need to rebalance a poorly balanced tree or to create a well-balanced tree from sorted input data. It is the latter situation that we will address in this document.

We will assume that our input data is located in a sorted array indexed from 0 to n-1 where n is the number of elements in the array. Certainly if we are given a poorly balanced binary search tree we can create such an array using an inorder traversal. Or if we are given an unsorted array of data we may simply sort it.

In order to create a "perfectly balanced tree" one must first have a definition for a "perfectly balanced tree". Several such definitions exist.

One definition requires that the number of nodes in the left and right subtree of any node differ by no more than one.
In this case a very simple algorithm will suffice.
  • Take the value in the middle index of the array and let that value become the root of a new binary search tree.
    The middle index of the array may be defined to be index (n-1)/2 where n is the number of elements in the array.
  • Perform the above step recursively with the left and right subtrees of the newly created binary search tree using the array elements respectively less than and greater than the one selected as root.
    Let your recursive routine be named rootInsert and be a method of a BST. Let rootInsert take 2 parameters. The first is the name (pointer to the first element) of the array, say, A and the second is n, the number of elements in the array. Using this convention your recrusive calls will look something like the following
    bst.left->rootInsert(A, (n-1)/2) and bstroot.right->Insert(A+(n+1)/2, n-(n+1)/2).
    The actual syntax for invoking the method depends upon the syntax of the declaration of your binary search tree.


    In another definition the tree must be filled in top to bottom and left to right.

    Create a balanced binary tree - Top to bottom and left to right

    You can accomplish this by writing a function called rootindex that takes as input the total number of data values, N, and returns the number of nodes less than the root. This is the index of the root.
    For example, if the total number of nodes is 13 and they are numbered 0 - 12 then there are 7 nodes less than the root node so the root of the tree is in position 7.
    You can then perform this same operation recursively with the left subtree and the right subtree to complete the construction of the tree.

    The trick here is, of course, to be able to write the function that returns the root index given the number of values.

    Let the Binary Search Tree we are creating be named BST.
    Observe that a perfectly balanced, top to bottom, left to right tree, consists of a complete binary tree (call it CBT) plus one more level containing 0 or more nodes/values.
    Let r be the root of BST (and CBT). Name the left subtree of CBT, LS, its right subtree RS and let N be the number of values in the full data set. Finally let |X| be the number of nodes in the tree, X and let lg be log2.

    |CBT| = 2⌊lg(N)⌋-1

    |LS| = 2⌊lg(N)⌋-1-1 = |RS|.

    The number of nodes at the bottom level is N - |CBT|.

    The number of nodes at the bottom level less than the root is N - |CBT| - the number of nodes greater than the root. So, in other words, The number of nodes at the bottom level less than the root is
    min(N - |CBT|, 2⌊lg(N)⌋-1)
    where the second parameter is the max possible number of nodes at the bottom level less than the root.
    This is because the number of leaves in a complete binary tree is equal to one more than the number of internal nodes in the tree. So, the total number of nodes less than the root is |LS| + min(N - |CBT|, 2⌊lg(N)⌋-1).


    Top of this page   Top of page      Home page   Home page