Description

Description:

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Transcript

UNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science Division
CS61B P. N. HilﬁngerFall 1999Balanced Searching: Tries, Treaps
∗
1 Balance
We’ve seen that binary search trees have a weakness: a tendency to be become
unbalanced,
so that they are ineﬀective in dividing the set of data they represent into two substantiallysmaller parts. Let’s consider what we can do about this.Of course, we could always rebalance an unbalanced tree by simply laying all the keysout in order and then re-inserting them in such a way as to keep the tree balanced. Thatoperation, however, requires time linear in the number of keys in the tree, and it is diﬃcultto see how to avoid having a Θ(
N
2
) factor creep in to the time required to insert
N
keys.By contrast, only
O
(
N
lg
N
) time is required to make
N
insertions if the data happen to bepresented in an order that keeps the tree bushy. So let’s look at operations to re-balance atree without taking it apart and reconstructing it.What we need is an operation that changes the balance of a BST—choosing a new rootthat moves keys from a deep side to a shallow side—while preserving the binary search treeproperty. The simplest such operations are the
rotations
of a tree. Figure 1 shows two BSTsholding identical sets of keys. Consider the rightRotation ﬁrst (the left is a mirror image).First, the rotation preserves the binary search tree property. In the unrotated tree, the nodesin
A
are the exactly the ones less than
B
, as they are on the right;
D
is greater, as on theright; and subtree
C
is greater, as on the right. You can also assure yourself that the nodesunder
D
in the rotated tree bear the proper relation to it.Turning to height, let’s use the notation
H
A
,
H
C
,
H
E
,
H
B
, and
H
D
to denote the heightsof subtrees
A
,
C
, and
E
and of the subtrees whose roots are nodes
B
and
D
. Any of
A
,
C
, or
E
can be empty; we’ll take their heights in that case to be
−
1. The height of thetree on the left is 1 + max(
H
E
,
1 +
H
A
,
1 +
H
C
). The height of the tree on the right is1 + max(
H
A
,
1 +
H
C
,
1 +
H
E
). Therefore, as long as
H
A
>
max(
H
C
+ 1
,H
E
) (as wouldhappen in a left-leaning tree, for example), the height of the right-hand tree will be less thanthat of the left-hand tree. One gets a similar situation in the other direction.In fact, it is possible to convert any BST into any other that contains the same keys bymeans of rotations. This amounts to showing that by rotation, we can move any node of
∗
Copyright c
1991, 1997, 1998, 1999 by Paul N. Hilﬁnger. All rights reserved.
67
68
P. N. Hilﬁnger
A CBEDC EDAB
D.rotateRight()D.rotateLeft()
Figure 1:
Rotations in a binary search tree. Triangles represent subtrees and circles represent individualnodes. The binary search tree relation is maintained by both operations, but the levels of various nodes areaﬀected.
a BST to the root of the tree while preserving the binary search tree property [why is thissuﬃcient?]. The argument is an induction on the structure of trees.
ã
It is clearly possible for empty or one-element trees.
ã
Suppose we want to show it for a larger tree, assuming (inductively) that all smallertrees can be rotated to bring any of their nodes their root. We proceed as follows:
–
If the node we want to make the root is already there, we’re done.
–
If the node we want to make the root is in the left child, rotate the left childto make it the root of the left child (inductive hypothesis). The perform a rightrotation on the whole tree.
–
Similarly if the node we want is in the right child.Of course, knowing that it is possible to re-arrange a BST by means of rotation doesn’t tellus which rotations to perform. There are various schemes that involve explicitly or implicitlykeeping track of the heights of subtrees and performing rotations when they get too far outof line: AVL trees, red-black trees, 2-3 trees, B-trees are some traditional examples. They areall a bit complicated, and since they are almost never actually used (with the exception of B-trees, and those only in large database systems), I thought we might perhaps look as welllook at something equally unused but perhaps a bit more interesting: a
randomized search tree,
one that is balanced with high probability. One isn’t certain of balance, just prettycertain.
2 Treaps: Probablistic balancing
One example of such a structure is the
treap
, a combination (as the name implies) of a binarysearch tree and a heap
1
More speciﬁcally, each node of a treap contains a search key and a
1
See “Randomized search trees,” Cecilia R. Aragon and Raimund G. Seidel,
30th Annual Symposium on Foundations of Computer Science (FOCS)
, IEEE Computer Society Press, 1989, pp. 540–545. The samedata structure (with a diﬀerent use) was called a
Cartesian tree
by Jean Vuillemin (“A unifying look at datastructures,”
CACM
23
(4) (April, 1980), pp. 229-239).
Balanced Searching
69number called its
priority
. The data structure is maintained in such a way that it is alwaysa binary search tree with respect to the keys, and it is always a binary heap with respect tothe priorities.Searching in a treap is identical to searches in a binary search tree. The priorities areused to keep the tree balanced. Speciﬁcally, every time we add a new node to the tree, weassign it a priority by applying a hashing function to its key, and then re-arrange the treeto keep it both a binary search tree and a heap. (Now, of course, you see the
real
reasonto introduce this data structure; it combines BSTs, heaps, and hashing all into one datastructure.) Likewise, whenever we delete a node from the tree, we “re-heapify” the tree,maintaining its status as a binary search tree. The idea is that
with high probability
, theresulting tree will be reasonably balanced (its height will be within a ﬁxed constant factor of ln
N
), because the priorities eﬀectively choose at random between the many possible binarysearch trees that can hold those keys.Let’s now turn to eﬀects of rotation on the heap structure of the tree. Consider ﬁrstthe left tree in Figure 1, and assume that it satisﬁes the heap property,
except
that node
B
contains a priority that is larger than that of
D
. Then the result of the right rotation is easilyseen to satisfy the heap property completely. Since
C
and
E
were under
D
on the left, theymust contain priorities smaller than that of
D
, so it is valid to put them as children.
D
isclearly a valid child of
B
, and since
A
was srcinally under
B
, it remains a valid child of
B
.Furthermore,
B
is now higher than it previously was.Alternatively, suppose that the left tree is a heap except that node
D
contains a value lessthan either of its children, and that
B
is the larger child. Then it is valid for all the subtrees,
A
,
C
, and
E
to be under
B
, and the right tree is again a heap, except that the priority of
D
may be smaller than those of its children, and
D
now has fewer descendents. Thus bycontinuing to rotate
D
down, we will eventually restore the heap property.The rotations are mirror images of each other. Thus, when we have a tree conﬁgured likethe right tree in Figure 1, and it is a valid heap except that
D
’s priority is larger than
B
’s, a
left
rotation ﬁxes the problem.These considerations indicate the necessary insertion and deletion routines. Here is ourdata structure in outline (as usual, using integers as labels):
class Treap {private int label;protected Treap left, right;protected int priority;/** A singleton Treap. */public Treap(int label){ this.label = label; priority = someHashFunction(L); }public static final Treap EMPTY = new EmptyTreap();public boolean isEmpty() { return false; }public Treap left() { return this.left; }
70
P. N. Hilﬁnger
public Treap right() { return this.right; }public int label() { return this.label; }/* A node in this Treap with label L, or null if none. */public Treap find(int L) { /* same as for BST */ }/* Tree rotations */protected Treap rotateLeft() {...}protected Treap rotateRight() {...}public Treap insert(int L) { ... }public Treap remove(int L) { ... }}
Rotations are routine:
/** The result of performing a right rotation on the root of this* treap, returning the root of the result. Assumes my left child.* is not empty. */protected Treap rotateRight() {Treap result = left;left = left.right;result.right = this;return result;}/* rotateLeft is the same, swapping left for right. */
For insertion, we ﬁrst insert the new label in the appropriate child. We assume recursivelythat if the newly inserted node has a priority larger than that of parent, it will rise to theroot of the child, where a single rotation will restore the heap property.
/** Insert label X into this treap. */public Treap insert(int X){if (X < label) {left = left.insert(X);if (left.priority > this.priority)return rotateRight();} else {right = right.insert(X);if (right.priority > this.priority)return rotateLeft();}return this;}

Search

Similar documents

Tags

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x