This exercise explains balanced tree.
(1) Make 2-3-4 tree from the following data. Also, write the state at all stages of the calculation process.
C O C A C O L A
(2) Rewrite the tree made in (1) to red-black tree.
ex11-2-RB.c is a program which generates a red-black tree. Check that a red-black tree is correctly displayed (the place where * is marked is a red link). Although the functions used in this program, void rbtreeinsert(char c); NodePointer rotate(char v, NodePointer y); void split(char v); are much complicated, understand this program as much as possible.
Next, change this program and insert keys from A to Z into red-black tree in order.
Check that the result is balanced compared with the usual binary tree.
Z
Y
X
W
V
U
T
S
R
Q
P
O
N
M
L
K
J
I
H
G
F
E
D
C
B
A
Write the function named int treelevel(NodePointer node), which calculates the height of the tree and change ex11-2-RB.c as follows:
% ./a.out
*U
P
*P
O
N
*L
*H
*G
E
*B
level: 3