introduction to algorithms - binary search trees

03.02.2009

binary search tree(bst) is a binary tree structure. basic operations on a bst are proportional to the height of the tree. for such operations on a bst run o(log n) worst-case time. a bst has the following properties:

· root node is the only node in the tree whose parent field is null.
· left subtree of the node contains the values less than the node's value.
· right subtree of the node contains the values greater than the node's value.

here's what a bst looks like;

please note that like in linked lists revisited post, i'm implementing the bst tree as described in introduction to algorithms, second edition(p. 253)

the best thing about bsts is when we need to print the keys it allows us to print in sorted order which is called inorder tree walk(this is called inorder tree walk 'cos the root node is printed between its left and right subtrees). there are also preoder tree walk which prints the root node before the values, and postorder tree walk which prints the root node after the values.

before start, we need node class

   class Node {
     int data;
     Node left, right;
     
     public Node(int data) {
       this.data = data;
       this.left = null;
       this.right = null;
     }
   }

let's start with inorder tree walk;

   void inorderTreeWalk(Node root) {
     if(root != null) {
       inorderTreeWalk(root.left);
       System.out.print(root.data + " ");
       inorderTreeWalk(root.right);
     }
   }

it takes o(n) time to walk on the tree. method runs recursively twice for each node in the tree, once for the left subtree, and once for the right subtree.

searching

bsts are relatively ease. all you have to remember is if value is less than root goto left subtree, else goto right subtree. in addition to search, bsts can support minimum, maximum, successor, and predecessor as well, and can be supported in o(h) time where h is the height of the tree.

searching is almost same with inserting into tree.

   Node search(Node root, int key) {
     if(root == null || root.data == key) {
       return root;
     }
     if(key < root.data) {
       return search(root.left, key);
     } else {
       return search(root.right, key);
     }
   }

basically what this does is; if root's datum is equal to key that we search or root is null then return the root node. if the key is less than the root's datum then continue searching on the left subtree, else search on the right subtree. running time for search method is o(h) where h is the height of the tree.

for more efficiency search method can be rewritten in iterative version.

   Node search(Node root, int key) {
     while(root != null && key != root.data) {
       if(key < root.data) {
         root = root.left;
       } else {
         root = root.right;
       }
     }
     return root;
   }

minimum and maximum

to find the minimum datum in the tree, we need to follow the left subtree from the root until a NULL is reached.

   Node minimum(Node root) {
     while(root.left != null)
       root = root.left;
     return root;
   }

i guess it's easy to guess maximum method;

   Node maximum(Node root) {
     while(root.right != null)
       root = root.right;
     return root;
   }

like search method both minimum, and maximum method run in o(h) time where h is the height of the tree.

successor and predecessor

ok, now it's time to find the successor of a node. the successor of a node is the node with the smallest key that is greater than the node.

   Node successor(Node root) {
     if(root.right != null)
       return minimum(root.right);
     Node y = root.right;
     while(y.left != null)
       y = y.left;
     return y;
   }

there's no need to write predecessor 'cos you can easily guess what to change. they both run in o(h) time where h is the height of the tree.

insertion and deletion

we almost did everything except the most important part; insertion. insertion follows the same routine like search methods. i'll implement recursive version of insertion as well, introduction to algorithms(p. 261) book provides only iterative pseudocode.

let's begin with recursive implementation.

   Node insert(Node root, int data) {
     if(root == null)
       return new Node(data);
     if(root.data < data)
       root.right = insert(root.right, data);
     else if(root.data > data)
       root.left = insert(root.left, data);
     // else should never happen.
     return root;
   }

else should never happen. however if you want to allow duplicate values, you need to insert the duplicate one on the right subtree.

same code with iteration, look at this, how ugly it is. ;)

   Node insert(Node root, int data) {
     if(root == null)
       return new Node(data);
     Node temp = root;
     Node prev = null;
     while(temp != null) {
       prev = temp;
       if(temp.data < data)
         temp = temp.right;
       else if(temp.data > data)
         temp = temp.left;
       else
         return root;
     }
     if(prev.data < data)
       prev.right = new Node(data);
     else
       prev.left = new Node(data);
     return root;
   }

again, this is also runs in o(h) time. and search method. let's go with recursion again.

   Node delete(Node root, int key) {
     if(root == null)
       return null;
     if(key < root.data)
       root.left = delete(root.left, key);
     else if(key > root.data)
       root.right = delete(root.right, key);
     else {
       if(root.left != null && root.right != null) {
         root.data = successor(root.right).data;
         root.right = 
       }
     }
   }

following examples are not provided in the introduction to algorithms, second edition book but it's good to implement these as well.

size() of the tree

let's find the number of nodes in the tree. as usual, we use recursion. it's easier than iteration.

   int size(Node root) {
     if(root == null)
       return 0;
     else
       return size(root.left) + 1 + size(root.right);
   }

postorder and preorder

we've started with inorder implementation at the beginning of the post, and here are postorder and preorder.

   void postorder(Node root) {
     if(root != null) {
       postorder(root.left);
       postorder(root.right);
       
       System.out.print(root.data + " ");
     }
   }

it's ease to figure out how preorder is going to be.

swap values

let's swap the values in the tree. so the tree:

will be:

this doesn't look like a bst anymore ;) anyway, let's rotate the tree

   void rotate(Node root) {
     if(root != null) {
       rotate(root.left);
       rotate(root.right);
       
       swap(root.left, root.right);
     }
   }
   
   void swap(Node left, Node right) {
     left ^= right;
     right ^= left;
     left ^= right;
   }

here's the thing, when we rotate the tree it doesn't look like a bst anymore. so how can we understand of a tree is bst or not? interesting question, maybe. remember the beginning of the post, all we have to do is start visiting the subtrees, let's say one of the nodes on the left is bigger than its parent node, then it's not a bst.

   boolean isBST(Node root) {
     if(root == null)
       return true;
     if(root.left != null && maximum(root.left) > root.data)
       return false;
     if(root.right != null && minimum(root.right) <= root.data)
       return false;
     return isBST(root.left) && isBST(root.right);
   }

third if statement could be changed, that depends on how you want to store the values, you may want to store duplicated values as well. if so, you need to change it.

so, what happens if we insert 1..5 to a bst? our bst will look like;

suddenly, we lost all the advantages of the bst, and now our tree looks like a linked list! well, it's a linked list :)
this is the part where balanced trees such as red-black trees, and avl trees take place.

i might use generics of java but it might not make sense to someone who codes in python.

faruk akgul