Binary search tree

Binary search tree or BST is a family of tree-based data structures, with maximum of two children and which follow to the general restriction that any node in a tree is larger than all nodes in it’s left sub-tree and smaller than all nodes in it’s right sub-tree.

bst

 

BST doesn’t support duplicates, thus it can be used to construct sets or associative arrays.

Some tree-related terminology
  1. Root – is a vertex of the tree which does not have parent.bst_root
  2. Parent – A node that has at least one child. Any node except a root node  have a parent.bst_parentsNodes 2, 3, 6, 22 and 34 are parent nodes.
  3. Child – a node is a child if it has a parent.bst_children
  4. Descendant  All the nodes that can be accessed from a particular node are the descendants of that node.bst_descendantsNodes 14, 34 and 50 are descendants of the node 22.
  5. Ancestor -A set of nodes that can be accessed from a particular node to the root.bst_ancestors
    Nodes 34, 22 and 6 are ancestors of the node 50.
  6. Leaves—The leaves are nodes that do not have any children.bst_leavesNodes 1, 4, 14 and 50 are leaves.

 

Implementation

Let’s have a look on basic operations :

  1. Insert – Inserts a new value.  The algorithm is straightforward, it Iteratively, starting from a root node (current node) checks three possible cases:a) Given value is equal to current node, if so – end insertion, otherwise check case b.

    b) Given value is lesser than current node. If this is not our case go to the case c, otherwise check whether current node has left child. If left child exist, then set left child to current node and goto the case a, else insert a new node as a left child.

    c) Given value is greater than current node. Check whether current node has right child. If right child exist, then set right child to the current node and goto case a, else insert a new node as a right child.

  2. Delete – Removes a node from the tree. There are three possible cases which can be handled:

    1)
    The removing node is a leaf node. In this case we simply remove this node from the end of tree.2) The node has one child. If so – copy child on the
    place of the removed node and remove child.

    3) The most complex case when the node has two children. To handle this case we have two approaches:

    Solution #1: find maximum node from the left sub-three. Copy maximum node on the place of node which is going to be removed. Remove maximum node from the end of the left sub-three.

    Solution #2: almost the same as  solution #1, the only difference is that you ned to find minimum element from right sub-tree.

  3. Search – searches node by value.
  4. Preorder traversal – visits node itself, then its left descendants, and finally its right descendants.
  5. Inorder traversal – visits left descendants, then node itself, and finally right descendants.
  6. Postorder traversal – visits left descendants, then right descendants, and finally node itself.
  7. Find max/min – returns maximum or minimum node in the tree.

Here is version on GitHub:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/BinarySearchTree.java

Complexity

Insertion, deletion and look up operations can be done in O(log n) time, traversal remains linear. But please note that O(log n) times for these operations can be achieved if a tree is balanced (for instance, AVL tree). Let say we have five elements [1, 2, 3, 4, 5] that were inserted into the tree one by one as they appeared in the list. In this case our tree will look like this:

unbalanced_tree

Thus,  Insertion, deletion and look up operations will be done in O(n) time.

Leave a Reply