3.2.10 #

解答 #

官方实现：https://algs4.cs.princeton.edu/32bst/TestBST.java.html

测试结果：

size = 10
min = A
max = X

Testing keys()
---------------------------
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0
X 7

Testing select
---------------------------
0 A
1 C
2 E
3 H
4 L
5 M
6 P
7 R
8 S
9 X

key rank floor ceil
---------------------------
A 0 A A
B 1 A C
C 1 C C
D 2 C E
E 2 E E
F 3 E H
G 3 E H
H 3 H H
I 4 H L
J 4 H L
K 4 H L
L 4 L L
M 5 M M
N 6 M P
O 6 M P
P 6 P P
Q 7 P R
R 7 R R
S 8 S S
T 9 S X
U 9 S X
V 9 S X
W 9 S X
X 9 X X
Y 10 X
Z 10 X
range search
---------------------------
A-Z (11)A C E H L M P R S X
Z-A (0)
X-X (1)X
0-Z (11)A C E H L M P R S X
B-G (3)C E
C-L (4)C E H L

After deleting the smallest 3 keys
---------------------------
H 5
L 11
M 9
P 10
R 3
S 0
X 7

After deleting the remaining keys
---------------------------

After adding back the keys
---------------------------
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0
X 7