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