lua-users home
lua-l archive

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

On Tue, Apr 21, 2015 at 9:53 PM, Oliver Kroth <> wrote:
> Coda,
> 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:
> --
> Oliver
> 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

Learn something new every day. Also I was improperly taught the
definition of threaded binary trees in school, now that I've read the
Wikipedia article more closely.

/s/ Adam