Those data structures can not be learned from Leetcode — Treap

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) .

Let’s take a look.

Defination

Every BST node store 2 values: key and priority.

key : the value of BST node . left ≤ current ≤ right

priority: the value of (min or max) heap. it is auto randomly generated during insert. current priority (for min heap) ≤ children priority.

Insert Process

First, we are building a treap => min heap + BST .

When inserting new node, a priority is auto generated with random value, binary search find the position and insert the key there; Use rotation (to maintain BST) to “move up or down” the lower priority node, keep doing this until heap looks good (that is ,current node priority ≤ children…