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.
http://faculty.washington.edu/aragon/...

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:
https://en.wikipedia.org/wiki/Treap

Avrim Blum's CMU lecture that makes use of "Hoeffding’s inequality" to analyze dept of a treap:
https://www.cs.cmu.edu/~avrim/451f11/...

Written and narrated by Andre Violentyev