balanced binary search tree implementation

In this blog post “Balanced Binary Search Tree“, I introduce two balanced binary search trees, which are AVLTree and RedBlackTree. AVLTree is efficient for search. Its time complexity is O(logN) for search, insertion and deletion. It usually takes one top-down pass to search a particular element. However, it will take two passes, one top-down pass and another down-top pass, to insert or delete an element. So is the similar case for RedBlackTree.

However, RedBlackTree is a little different from AVLTree. RedBlackTree is not so restrict in tree balance as AVLTree, so it relatively more efficient for RedBlackTree to insert or delete elements. What’s more, RedBlackTree also supports a single top-down pass for inserting or deleting a particular element. This is also more efficient for RedBlackTree. I read the source code for TreeMap in JDK 1.8, but it uses the two-pass algorithm, which uses the top-down and down-top pass for insertion and deletion. I struggled a couple of days and finally managed to implement the AVLTree and RedBlackTree.

AVLTree is relatively easy to implement. Many books about data structures usually include a reference implementation. However, RedBlackTree is a little hard to implement. Not all book about data structures include a full implementation, especially the single top-down pass algorithm. I read two books about RedBlackTree. None of them includes the full implementation of the efficient single pass algorithm for insertion and deletion.

Below is the implementation of AVLTree and RedBlackTree I struggled for a couple of days:



I hope the single top-down implementation for RedBlackTree can give any help when you learn knowledge about RedBlackTree.