To insert a node into a tree with such a property:
First insert the node into the tree using the rules of Binary Search tree
based on Value i .
Now compare Node-j and Node-Parent-j. Depending upon the result of
comparison perform left rotation or right rotation so that the Heap property
is also maintained. Repeat this process until you fully restore the Heap
property.
On Wed, Dec 15, 2010 at 2:54 PM, Prims topcode...@gmail.com wrote:
Lets assume that the tree node has two keys K1 and K2.
K1 satisfies the BST property
K2 satisfies the Max Heap Property.
Our problem is to build a binary tree which satisfies both the
properties.
For a maximal heap the root node must be the maximum.
So we find the node which has the K2 max. And make it as the root
node.
Among the remaining nodes, The nodes to the left of the tree will be
those whose K1 value is less than that of the Root nodes K1. And rest
will be on the right side of the root. Now again repeat the procedure
for finding the next left node of root and right node of root using
the same logic above
On Dec 15, 2:07 pm, snehal jain learner@gmail.com 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
