Data Structures :: Trees - Discussion
13 / 194
B Trees are generally
Avery deep and narrow
Bvery wide and shallow
Cvery deep and very wide
Dcannot say
Show Explanation
Please explain following binary search tree case study
Suppose that a binary search tree stores, at each node, u, the height, u.height, of the subtree rooted at u, and the size, u.size of the subtree rooted at u.
1. Show how, if we perform a left rotation at u, then these two quantities can be updated, in constant time, for all nodes affected by the rotation.
2. Show how, if we perform a right rotation at u, then these two quantities can be updated, in constant time, for all nodes affected by the rotation.
3. Explain why the same result is not possible if we try to also store the depth, u.depth, of each node u.
Asked In ::
Please explain following binary search tree case study
Suppose that a binary search tree stores, at each node, u, the height, u.height, of the subtree rooted at u, and the size, u.size of the subtree rooted at u.
1. Show how, if we perform a left rotation at u, then these two quantities can be updated, in constant time, for all nodes affected by the rotation.
2. Show how, if we perform a right rotation at u, then these two quantities can be updated, in constant time, for all nodes affected by the rotation.
3. Explain why the same result is not possible if we try to also store the depth, u.depth, of each node u.
Read Full Answer
Report Error
Please Login First Click Here
Random
binary search trees have been studied extensively. There are much stronger
results in the literature as well, the most impressive of which is due to Reed who
shows that the expected height of a random binary search tree is
where is the unique solution on the
interval of the equation and . Furthermore, the variance of the
height is constant.
The
name Treap was coined by Seidel and Aragon who discussed Treaps
and some of their variants. However, their basic structure was studied much
earlier by Vuillemin who called them Cartesian trees.
One
possible space-optimization of the Treap data structure is the
elimination of the explicit storage of the priority in each
node. Instead, the priority of a node, , is computed
by hashing 's address in
memory (in 32-bit Java, this is equivalent to hashing ).
Although a number of hash functions will probably work well for this in
practice,to remain valid, the hash function should be randomized and have
the min-wise independent property: For any distinct
values , each of
the hash values should
be distinct with high probability and, for each ,
for some
constant . One such class of hash functions that is easy to implement
and fairly fast is tabulation hashing.
Another Treap variant
that doesn't store priorities at each node is the randomized binary search
tree of MartÃnez and Roura In this
variant, every node, , stores the
size, , of the
subtree rooted at . Both
the and algorithms
are randomized. The algorithm for adding to the
subtree rooted at does the
following:
1.
With probability ,
the value is added
the usual way, as a leaf, and rotations are then done to bring up to
the root of this subtree.
2.
Otherwise (with probability ),
the value is
recursively added into one of the two subtrees rooted at or , as
appropriate.
The first case
corresponds to an operation in a Treap where 's node receives a random priority that is smaller
than any of the priorities in 's subtree, and this case occurs with exactly the same
probability.
Removing
a value from a
randomized binary search tree is similar to the process of removing from
a Treap. We find the node, , that
contains and then
perform rotations that repeatedly increase the depth of until it
becomes a leaf, at which point we can splice it from the tree. The choice of
whether to perform a left or right rotation at each step is randomized.
1.
With probability ,
we perform a right rotation at , making the
root of the subtree that was formerly rooted at .
2.
With probability ,
we perform a left rotation at , making the
root of the subtree that was formerly rooted at .
Again, we can
easily verify that these are exactly the same probabilities that the removal
algorithm in a Treapwill
perform a left or right rotation of .
Randomized
binary search trees have the disadvantage, compared to treaps, that when adding
and removing elements they make many random choices, and they must maintain the
sizes of subtrees. One advantage of randomized binary search trees over treaps
is that subtree sizes can serve another useful purpose, namely to provide
access by rank in expected
time In comparison, the random priorities stored in treap nodes have no use
other than keeping the treap balanced.
Read Full Answer
Report Error
Please Login First Click Here