[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] new module binaryheap 0.1 released
- From: Coda Highland <chighland@...>
- Date: Wed, 22 Apr 2015 07:28:48 -0700
On Tue, Apr 21, 2015 at 9:53 PM, Oliver Kroth <firstname.lastname@example.org> wrote:
> 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: http://en.wikipedia.org/wiki/Treap
> Am 21.04.2015 um 23:04 schrieb Coda Highland:
>> Your "treap" is probably more accurately referred to as a "threaded binary
>> tree". http://en.wikipedia.org/wiki/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.