A BST powered by heap which solves the BST degeneration problem
Continuing with advanced DSA topic : Skip list , B Tree Step by Step . in this article ,we walk through a powerful yet easier to implement (compare with red-black ,AVL, B-Tree) auto-balanced BST — Treap .
Binary Search Tree + Heap = Treap . sounds a cool idea, isn’t it ?
But first, lets see what problem treap trying to solve .
The Problem — BST Degeneration
When building a BST, when the insert values are sorted. it will be generated as a “normal link-list” as below .
Even there is left and right pointer in each tree node, another pointer not being used at all . so search ,insert, delete now all becomes O(N) . a BST degenerated into linked-list (with N pointer space wasted)
To solve this problem, there must be certain “auto balancing mechanism” built into BST. the tree should be smart enough to maintain its hight to archive best performance for search, insert, delete .
The famous solutions are using data structures like red-black , AVL, 2–3, 2–3–4 (B tree). Treap also one of them , yet an easier version, but not perfect (see the worst case in later section) .
