lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


no, that is another structure with additional pointers. In a treap, each node has two pointers, but also two values that are sorted independently.

A treap is first a normal binary tree, where all left children have a value less than or equal to the node's own value, and all right children have a greater or equal value.
As such, the nbinary tree is sorted left to right for the value.

Additionally, the tree is sorted from root to the leaves as a heap, i.e. each node has a higher or same priority than all its children.

After each operation on the binary tree structure, the heap has to be reestablished with left-right or right-left-rotations of three adjacent nodes until the hep condition is met again. The effort for all operations is O(log n), only peeking at the root, the element with the highest priority, is O(1).

You may look at Wikipedia:


Am 21.04.2015 um 23:04 schrieb Coda Highland:
Your "treap" is probably more accurately referred to as a "threaded binary tree". /s/ Adam