1. Insert the node(order of insertion is irrelevant) in any order according to the binary search tree properties. 2. Compare the j value of node with its parent recursively (bottom up) and then perform rotations to restore the Heap property.
On Thu, Jun 9, 2011 at 12:38 AM, mukesh tiwari <[email protected] > wrote: > What you explained is the property of Treap data structure . You can > have a look at wiki [ http://en.wikipedia.org/wiki/Treap ] or you can > search google for treap. > > On Jun 8, 8:15 pm, Akshata Sharma <[email protected]> wrote: > > A rooted binary tree with keys in its nodes has the binary search tree > > property (BST property) if, for every node, the keys in its left > > subtree are smaller than its own key, and the keys in its right > > subtree are larger than its own key. It has the heap property if, for > > every node, the keys of its children are all smaller than its own key. > > You are given a set of n binary tree nodes that each contain an > > integer i and an integer j. No two i values are equal and no two j > > values are equal. We must assemble the nodes into a single binary tree > > where the i values obey the BST property and the j values obey the > > heap property. If you pay attention only to the second key in each > > node, the tree looks like a heap, and if you pay attention only to the > > first key in each node, it looks like a binary search tree.Describe a > > recursive algorithm for assembling such a tree > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
