Scribd
Upload
31 views5 pages

02 2003 F Sol

This document contains solutions to exam questions about operations on binary search trees. 1. It summarizes merging two min-heaps by joining their roots with the smaller root value first. 2. It provides two versions of a binary search tree problem due to a typo, and shows the solutions to inserting values in each case. 3. It demonstrates several insertion and rebalancing operations on an example binary search tree, including left, right, left-right cases and the resulting rotations needed.

Uploaded by

Grace Evangelene
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views5 pages

02 2003 F Sol

This document contains solutions to exam questions about operations on binary search trees. 1. It summarizes merging two min-heaps by joining their roots with the smaller root value first. 2. It provides two versions of a binary search tree problem due to a typo, and shows the solutions to inserting values in each case. 3. It demonstrates several insertion and rebalancing operations on an example binary search tree, including left, right, left-right cases and the resulting rotations needed.

Uploaded by

Grace Evangelene
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Fall 2003

Exam02_solution

question 1.

min
|
V
20 3 1
| / \ / / |
25 7 5 13 15 18
| / | |
9 14 26 17
| |
19 30

(a)
delete (1) = min

min
|
V
20 3 13 15 18
| / \ / \ |
25 7 5 14 26 17
| | |
9 19 30

joins two min F-heaps with same degree 2 and degree 1

3 15 18
/ / | / |
(F)13 7 5 (F)20 17
/ | | | |
14 26 9 25 30
|
19

(b) DecreaseKey
3 15 18 14 19
/ / | / |
(T)13 7 5 (F)20 17
| | | |
26 9 25 30

(2) There was a typo in part(a). The balance factor of the root should
be -1 instead of +1. I am very sorry for the problem.

Thus, I provide sample solutions for the two versions.


Remember that you need to identify imbalance type from the node whose
balance factor becomes either +2 or -2 when a node is inserted.

Version 1: The balance factor of the root is -1.


(a)
5
/ \
3 10
/ \ / \
2 4 7 12
/ \ / \
6 9 11 13

(b) insert 8 (RL)

7(0)
/ \
5(1) 10
/ \ / \
3 6 9(1) 12
/ \ / / \
2 4 8 11 13

insert 1 (LL)

7(0)
/ \
3(0) 10
/ \ / \
2(1) 5 9(1) 12
/ / \ / / \
1 4 6 8 11 13
Version 2: The root is "10" and has balance factor +1.

(a)
10
/ \
9 12
/\ / \
4 6 11 13
/ \ / \
2 3 5 7

(b) insert 8 (LR)

10
/ \
5 12
/\ / \
3 7 11 13
/ \ / \
2 4 6 9

7(0)
/ \
5(1) 10
/ \ / \
3 6 9(1) 12
/ \ / / \
2 4 8 11 13

insert 1 (LL)

7(0)
/ \
3(0) 10
/ \ / \
2(1) 5 9(1) 12
/ / \ / / \
1 4 6 8 11 13

(3)
(a)
10 I(5) 10 LLb 8 I(1) 8
// ===> // ===> // \\ ===> // \\
8 8 5 10 5 10
// //
5 1

LLr 8 I(3) 8 LRb 8


===> / \ ===> / \ ===> / \
5 10 5 10 3 10
// // // \\
1 1 1 5
\\
3

I(7) 8 RRr 8
===> / \ ===> // \
3 10 3 10
// \\ / \
1 5 1 5
\\ \\
7 7

(b) Step 1. Follow the left child pointers from the root of B to
first node x whose rank equals rank(S) = 1.

6 <--- x
//
5

Step 2. Combine S, 4, and subtree rooted at 6.

4
/ \
3 6
// //
2 5

Step 3. Combine the result of Step 2 to node "7" through a red pointer.

11
// \
7 13
// \
4 9
/ \ // \\
3 6 8 10
// //
2 5

Step 4. Imbalance (LLb --> rotate)

7
// \\
4 11
/ \ / \
3 6 9 13
// // // \\
2 5 8 10

You might also like