Treap (Tree + Heap) Data Structure - Tutorial with Statistical Analysis

A computer science data structure called "Treap" is a combination of a Binary Search Tree and a Heap. This introductory tutorial explains how Treap data structure uses randomly generated numbers, called "priority" to construct and maintain a reasonably balanced tree.

The tree is constructed as if it’s a heap, with maximum priority value being at the root of the tree. Note that the tree construction needs to satisfy two conditions simultaneously:

1) each left child value is smaller than its parent’s, while each right child value is greater than its parent’s (this is the old binary search tree rule).
2) each child priority is smaller than its parent's priority (this is the max heap rule)

To we ensure that both of these conditions are satisfied, when inserting a node, we still walk down from the root, following the rules of a standard binary search tree (BST), comparing values to each other - we go left if the value is smaller than the parent, right if the value is bigger than the parent, and eventually create a new leaf node. Then, if we find that the priority of the node is greater than parent’s priority, we do tree rotations to fix this.

Cecilia R. Aragon and Raimund Seidel, in their 1989 paper, called "Randomized Search Trees", show that while there is no hard guarantee that the resulting tree will be balanced, the probability of the height of a Treap with n nodes being greater than natural log of n by a factor of some constant c, is bounded by a formula.

In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys:

Avrim Blum's CMU lecture that makes use of "Hoeffding’s inequality" to analyze dept of a treap:

Written and narrated by Andre Violentyev

[neeter]

Probably the best video on Treaps, hope your channel gets bigger!

[maridavies]

Nice! It’s great that you mention the statistical guarantees made about the tree structure being balanced.

[WAAGOM]

This is the best video on Treaps! Thanks for your help understanding this.

[walt]

Good enough for government work is always my favourite statement to use

[pratyushtiwari]

Your explanations are awesome and such a calm environment.

[robertogarcia]

Awesome tutorial, please keep making videos like this.

[archiefayzullaev]

Great Explanation! Thank you! I hope you will keep working on the channel !

[Avighna]

std::set has finally been un-blackboxed. Thank you! (yes, I know it uses RB trees, but treaps are a valid way to do it too)

[mahmoudaymantv]

Hey sir, We are missing you please come back soon,
best wishes

[futurexy]

Thanks! Your video is awesome, I learn a lot

[kidusadugna]

"It probably won't be perfectly balanced, but good enough for government work" 😂😂😂😂😂😂😂

[sineltor]

As for use cases, could you store a treap in an array like you can with a heap? If so, you'd probably end up with better performance than AVL trees because of cache locality.

[dawodujohnson]

Are you related to secondthread on codeforces?

[alex-gzud]

Awesome explanation! I'd like to give you 1000 likes if I can.