2024年5月16日发(作者：手机销量排行榜2021前十名最新)

Introduction to Algorithms

Massachusetts Institute of Technology

Professors Erik D. Demaine and Charles E. Leiserson

October 29, 2005

6.046J/18.410J

Handout 18

Problem Set 4 Solutions

Problem 4-1. Treaps

If we insert a set of n items into a binary search tree using T

REE

-I

NSERT

, the resulting tree may

be horribly unbalanced. As we saw in class, however, we expect randomly built binary search

trees to be balanced. (Precisely, a randomly built binary search tree has expected height O(lg n).)

Therefore, if we want to build an expected balanced tree for a fixed set of items, we could randomly

permute the items and then insert them in that order into the tree.

What if we do not have all the items at once? If we receive the items one at a time, can we still

randomly build a binary search tree out of them?

We will examine a data structure that answers this question in the affirmative. A treap is a binary

search tree with a modified way of ordering the nodes. Figure 1 shows an example of a treap. As

usual, each item xin the tree has a key key[x]. In addition, we assign priority[x], which is a random

number chosen independently for each x. We assume that all priorities are distinct and also that all

keys are distinct. The nodes of the treap are ordered so that (1) the keys obey the binary-search-tree

property and (2) the priorities obey the min-heap order property. In other words,

• if v is a left child of u, then key[v] < key[u];

• if v is a right child of u, then key[v] > key[u]; and

• if v is a child of u, then priority(v) > priority(u).

(This combination of properties is why the tree is called a “treap”: it has features of both a binary

search tree and a heap.)

G: 4

B: 7 H: 5

A: 10 E: 23 K: 65

I: 73

Figure 1: A treap. Each node x is labeled with key[x]:p riority[x]. For example, the root has key

G and priority 4.

It helps to think of treaps in the following way. Suppose that we insert nodes x

1

,x

2

,...,x

n

, each

with an associated key, into a treap in arbitrary order. Then the resulting treap is the tree that would

2

Handout18: ProblemSet4Solutions

have been formed if the nodes had been inserted into a normal binary search tree in the order given

by their (randomly chosen) priorities. In other words, priority[x

i

] < priority[x

j

] means that x

i

is

effectively inserted before x

j

.

(a)