2-3-4 Tree and how it relates to Red Black Tree

Outline B Tree, B* Tree, B+ Tree 2-3 Tree, 2-3-4 Tree Red-Black Tree (RBT) Left-Leaning Red-Black Tree Double Red & Double Black RBT “Insert” Example       The Same Example with 2-3-4 tree

B Tree

B-Tree is in memory of R. Bayer It is a generalization of binary search tree in that a node (or, an entry) can have more than two children [wiki]. Degree 為 d 的 B tree: 1) 每個 node 含至多 d 個 child pointers (或 d-1個 elements) 2) 每個 node 至少 1/2 滿 (即至少 [ (d-1)/2]個 elements)

B-Tree of Degree 3 20 28 10 25 30

B* Tree B-tree 的 node 至少 2/3 滿

B* Tree of Degree 4 6 20 28 2 4 10 15 23 26 30 35

B+ Tree 含 index pages 和 data pages root node 和 internal nodes 為 index pages (keys only). leaf nodes 為 data pages (排序的data ) data 即 element (含有 key) 每個 node 至少 1/2 滿 (Fill Factor 50%).

B+ Tree index page data page This B+ tree: Number of Keys 4 Number of Pointers 5 Fill Factor 50% Minimum Keys in each page 2

2-3 Tree

2-3 Tree 為 search tree 可為空或: 每個 internal node 為 2-node (有2 child pointers) 或 3-node (有3 child pointers) A 2-node 40 B C 3-node 10 20 80

2-3 Tree Insertion insert Case 1: 插入 70 先尋找 70. 發現不在其中. 須知尋找70時 遇到哪node? 是 含 80 的 node C node C 只有一個 element, 所以70 可放 C A 40 10 20 70 80 B C

2-3 Tree insert Case 2: 插入 30 會遇到 30 的是 node B B 為 3-node, 須產生新 node D. B 含 elements 10, 20, 30 其中最大element 30 放D 最小element 10 放 B. 中間20放B的parent A 這叫 Split (分裂): 1.產生新node D. 2.中間 20 推升上層 2-3 Tree 80 C A 20 40 10 70 B Figure 3 30 D

2-3 Tree Insertion (Cont.) insert case 3: 插入 60 尋找60會遇 node C C 為 3-node,需產生新 node E C 含 elements 60,70,80 中間值 70 放在C的parent A 最小值 60放C 最大值80放E A 為 3-node,產生新 node F A含 elements 20, 40, 70 中間值 40 放在A的parent G (需產生 G) 最小值 20放A 最大值70放F

2-3 Tree Insertion (Cont.) 40 G 70 F 80 E 60 C 20 A 10 B 30 D Figure 4 Insertion of 60 into the 2-3 tree of Figure 3

2-3 Tree Deletion (a) Initial 2-3 tree (b) 70 deleted A D B C A D B C 50 80 D B C 10 20 60 70 90 95 (a) Initial 2-3 tree A 50 80 B C D 10 20 60 90 95 (b) 70 deleted

2-3 Tree Deletion (Cont.) (c) 90 deleted A 50 80 C D B 10 20 60 95 (c) 90 deleted A 20 80 B C D 10 50 95 (d) 60 deleted Next, delete 95

2-3 Tree Deletion (Cont.) 這叫 Merge (融合): 1.消去 node D 2.上層 80 併入下層 A 20 這叫 Merge (融合): 1.消去 node D 2.上層 80 併入下層 B C 10 50 80 (e) 95 deleted A 20 A B C 20 80 10 80 (g) 10 deleted (f) 50 deleted

2-3-4 Tree

2-3-4 Tree 它為 search tree 可為空或: 每個 internal node 為 2, 3,或 4 node. (2-node有2 child pointers, 3-node有3 child pointers, 4-node 有4 child pointers) 所有external nodes 都在相同 level. 2-3-4 tree 類似2-3 tree, 但它有 4-node 如下圖 50 60 70

2-3-4 Tree Insertion There are 3 cases for a 4-node: Case 1: It is the root Case 2: Its parent is a 2-node Case 3: Its parent is a 3-node (fig. omitted)

2-3-4 Tree Insertion Case 1: It is the root. t t (root) a b c d a b c y x y z x z a b c d a b c d Figure1 when the root is a 4-node

2-3-4 Tree Insertion Case 2: Its parent is a 2-node e e a b c d a b c z x z e w x y w e y a b c d a b c d Figure 2 when the child of a 2-node is a 4-node

2-3-4 Tree 2-3-4 tree 轉成binary search tree 則稱為 red-black tree red-black tree比2-3-4 tree節省空間 因為2-3-4 node 會浪費不少 未存資料的空的空間

Red-Black Tree (RBT)

Red-Black Tree red-black tree 為 binary search tree: 每個 node 不是red就是black 每個leaf (NULL) 都為black red node 的兩個children都為black. 每個 path 含相同數目的 black nodes. red node不可接著red node (不可紅紅) implies that on any path from the root to a leaf, red nodes must not be adjacent. However, any number of black nodes may appear in a sequence. A basic red-black tree

Red-Black Tree A red-black tree with n internal nodes has height at most 2 log(n+1). Red-Black tree can always be searched in O (log n) time.

Red-Black Tree a b c c L S L OR  Left- Right- S leaning leaning S for Small L for Large Figure 1 Transforming a 3-node into two red-black nodes

Red-Black Tree M S M L S L c a d b a d b c  S for Small M, Middle L, Large b c Figure 2 Transforming a 4-node into two red-black nodes

1. 將下圖的 Red-Black Tree 轉成 2-3-4 Tree 2. 依序 (1)刪除60 (2)加入8 3 1. 將下圖的 Red-Black Tree 轉成 2-3-4 Tree 2. 依序 (1)刪除60 (2)加入8 3. 再轉回 Red-Black Tree 50 10 70 80 5 7 9 30 40 60 75 90 85 92

上圖轉成的 2-3-4 Tree 50 10 70 80 5 7 9 30 40 60 75 85 90 92

刪除 60 70 wasted space

加入 8 7 8

轉回 Red-Black Tree 50 7 80 5 10 70 90 8 30 75 85 92 9 40

Red Black Tree Saves Space In the example above, the 2-3-4 tree wastes 10 unused space of elements. The corresponding red-black tree cuts this waste!

Left-Leaning Red-Black Tree

LLRBT is easier to implement than RBT, especially the deletion It requires 3-nodes are left-leaning, thus maintains 1-1 correspondence with 2-3-4 trees (see next page).

LL Red-Black Tree (LL) a b c L S L  Left-Leaning S S for Small L for Large Transforming a 3-node into LL red-black nodes

Double Red & Double Black

During Red-Black Tree insertion, abnormal Double Red may occur as shown next.

2) 依 red black tree 新加入者為red 故 3,4 形成右圖 Double Red 違反 Red Rule Red-Black Tree Insertion 我們要對左圖　insert 4 1) 依 binary search tree 　　把 4 當 3 的 right child 2) 依 red black tree 新加入者為red 故 3,4 形成右圖 Double Red 違反 Red Rule 2 3 1 4 2 3 1

Double Red in 2-3-4 Tree 已滿, 此時 insert 4 這 node 爆掉了,故要調整之 1 2 3 已滿, 此時 insert 4 1 2 3 4 這 node 爆掉了,故要調整之 對應的 Red-Black Tree: 2 1 3 4 3 4 此時 叫 Double Red 雙紅, 表示原來 node 爆掉了

During Red-Black Tree deletion, again, abnormal Double Black may occur as shown next.

Double Black in 2-3-4 Tree 7 8 5 3 7 8 3 7 3 8 此時 Delete 5 對應的 Red-Black Tree: 3 7 3 8 Double BLACK 雙黑線,表示 其中有個空 2-3-4 node.故要調整之

This is textbook exercise 12.7 RBT “Insert” Example This is textbook exercise 12.7 Insert 30, 40, 20, 90, 10, 50, 70, 60, 80 to an initially empty red-black tree.

RBT insert 30 When any node is inserted, it must be red. The root 30 must be black.

RBT insert 40 30 40 Because 40 is greater than 30, 40 is inserted as the right child of 30.

RBT insert 20 30 20 40 Because 20 is less than 30, 20 is inserted as the left child of 30.

RBT insert 90 Case 1: red uncle 20 30 30 30 20 40 20 40 20 40 Case 1: red uncle 20 1.change parent 40 & uncle 20 to black 2.change granspa 30 to red 90 90 90 The root 30 must be black.

RBT insert 10 Because 10 is less than 20, 10 is inserted as the left child of 20. 30 20 40 10 90

RBT insert 50 Case 2: no uncle & RL rotate right around 90 30 30 20 40 20 40 10 90 10 50 Case 3: no uncle &RR 1.rotate left around 40 2.40,50 change color 50 90 Case 2: no uncle & RL rotate right around 90 30 20 50 10 40 90

RBT insert 70 Case 1: red uncle 40 1.change parent 90 & uncle 40 to black 2.change granspa 50 to red 30 30 20 50 20 50 10 40 90 10 40 90 70 70

RBT insert 60 Case 3: no uncle & LL 1.rotate right around 90 2.70,90 change color 30 30 20 50 20 50 10 40 90 10 40 70 70 60 90 60

RBT insert 80 Case 1: red uncle 60 1.change parent 90 & uncle 60 Double red (50,70). recurs upward! Case3:black uncle 20 & RR 1. rotate left around 30 2. 30,50 change color 3. 40 as right child of 30 RBT insert 80 30 30 20 50 20 50 10 40 70 10 40 70 60 90 60 90 80 80 Case 1: red uncle 60 1.change parent 90 & uncle 60 to black 2.change granspa 70 to red 50 30 70 20 40 60 90 10 80

The Same Insert Example with 2-3-4 tree to an initially empty 2-3-4 tree.

2-3-4 tree insert 30 30

2-3-4 tree insert 40 30 40

2-3-4 tree insert 20 20 30 40

2-3-4 tree insert 90 Node 20,30,40,90 overflows! create 2 nodes. SPLIT as below: 1.move the middle 30 upward. 2. 20 in lower left node 3. 40,90 in lower right node 30 20 40 90

2-3-4 tree insert 10 30 10 20 40 90

2-3-4 tree insert 50 30 10 20 40 50 90

2-3-4 tree insert 70 30 50 10 20 40 70 90

2-3-4 tree insert 60 30 50 10 20 40 60 70 90

2-3-4 tree insert 80 浪費空間 = 6 elements / 15 elements = 40 % 30 50 70 10 20 40 60 80 90 浪費空間 = 6 elements / 15 elements = 40 %