Nội dung

Chapter 6: Multiway Trees • Tree whose outdegree is not restricted to 2 while retaining the general properties of binary search trees. Cao Hoang Tru CSE Faculty - HCMUT 1 17 November 2008 M-Way Search Trees • Each node has m - 1 data entries and m subtree pointers. • The key values in a subtree such that: – >= the key of the left data entry – < the key of the right data entry. K1 keys < K1 Cao Hoang Tru CSE Faculty - HCMUT K1<= keys < K2 K2 K3 K2<= keys < K3 K3<= keys 2 17 November 2008 M-Way Search Trees 50 35 45 60 85 100 95 70 150 125 90 110 135 175 120 75 Cao Hoang Tru CSE Faculty - HCMUT 3 17 November 2008 M-Way Node Structure key num entries Cao Hoang Tru CSE Faculty - HCMUT data entry key data rightPtr end entry node ... firstPtr numEntries entries end node 4 17 November 2008 B-Trees • M-way trees are unbalanced. • Bayer, R. & McCreight, E. (1970) created B-Trees. Cao Hoang Tru CSE Faculty - HCMUT 5 17 November 2008 B-Trees • A B-tree is an m-way tree with the following additional properties (m >= 3): – The root is either a leaf or has at least 2 subtrees. – All other nodes have at least ⎡m/2⎤ - 1 entries. – All leaf nodes are at the same level. Cao Hoang Tru CSE Faculty - HCMUT 6 17 November 2008 B-Trees 42 16 11 14 17 19 20 21 21 58 22 23 24 45 52 63 65 74 76 78 81 79 93 85 87 94 m=5 Cao Hoang Tru CSE Faculty - HCMUT 7 17 November 2008 97 B-Tree Insertion • Insert the new entry into a leaf node. • If the leaf node is overflow, then split it and insert its median entry into its parent. Cao Hoang Tru CSE Faculty - HCMUT 8 17 November 2008 B-Tree Insertion Insert 78, 21, 14, 11 11 14 21 78 21 Insert 97 11 14 21 78 97 11 14 78 97 overflow Insert 85, 74, 63 21 11 14 63 74 78 85 97 11 14 21 78 63 74 85 97 overflow Insert 45, 42, 57 21 11 14 42 45 78 57 21 63 overflow Cao Hoang Tru CSE Faculty - HCMUT 74 85 97 11 14 42 45 57 78 63 74 85 9 17 November 2008 97 B-Tree Insertion Insert 20, 16, 19 21 11 14 16 19 57 20 overflow 78 63 42 74 16 85 97 11 14 19 45 21 20 42 11 14 21 19 20 21 30 78 63 74 85 97 45 42 Insert 52, 30, 21 16 57 57 63 42 16 78 45 74 52 85 97 11 14 19 21 21 20 57 30 45 52 63 78 85 74 overflow Cao Hoang Tru CSE Faculty - HCMUT 10 17 November 2008 97