tree

B+ Trees : 

28/10/2010 1 B+ Trees Similar to B trees, with a few slight differences All data is stored at the leaf nodes (leaf pages); all other nodes (index pages) only store keys Leaf pages are linked to each other Keys may be duplicated; every key to the right of a particular key is >= to that key

Slide 2: 

Presented By : ITG lifeline1976@gmail.com 28/10/2010 2

B+ Tree Example : 

28/10/2010 3 B+ Tree Example 9, 16 2, 7 12 18 1 7 9 3, 4, 6 12 16 19

B+ Tree Insertion : 

28/10/2010 4 B+ Tree Insertion Insert at bottom level If leaf page overflows, split page and copy middle element to next index page If index page overflows, split page and move middle element to next index page

B+ Tree Insertion Example : 

28/10/2010 5 B+ Tree Insertion Example 9, 16 2, 7 12 18 1 7 9 3, 4, 6 12 16 19 Insert 5

B+ Tree Insertion Example : 

28/10/2010 6 B+ Tree Insertion Example 9, 16 2, 7 12 18 1 7 9 3, 4, 5,6 12 16 19 Insert 5

B+ Tree Insertion Example : 

28/10/2010 7 B+ Tree Insertion Example 9, 16 2, 5, 7 12 18 1 7 9 3, 4 12 16 19 Split page, copy 5 5, 6

B+ Tree Insertion Example 2 : 

28/10/2010 8 B+ Tree Insertion Example 2 9, 13, 16 9 3, 4, 6 14 16, 18, 20 Insert 17

B+ Tree Insertion Example 2 : 

28/10/2010 9 B+ Tree Insertion Example 2 Insert 17 9, 13, 16 9 3, 4, 6 14 16, 17, 18, 20

B+ Tree Insertion Example 2 : 

28/10/2010 10 B+ Tree Insertion Example 2 Split leaf page, copy 18 9, 13, 16, 18 9 3, 4, 6 14 16, 17 18, 20

B+ Tree Insertion Example 2 : 

11 B+ Tree Insertion Example 2 Split index page, move 13 16, 18 9 3, 4, 6 14 9 13 16, 17 18, 20 28/10/2010

B+ Tree Deletion : 

12 B+ Tree Deletion Delete key and data from leaf page If leaf page underflows, merge with sibling and delete key in between them If index page underflows, merge with sibling and move down key in between them 28/10/2010

B+ Tree Deletion Example : 

13 B+ Tree Deletion Example Remove 9 9 3, 4, 6 9 13 16, 18 14 16, 17 18, 20 28/10/2010

B+ Tree Deletion Example : 

14 B+ Tree Deletion Example Remove 9 3, 4, 6 9 13 16, 18 14 16, 17 18, 20 28/10/2010

B+ Tree Deletion Example : 

15 B+ Tree Deletion Example Leaf page underflow, so merge with sibling and remove 9 3, 4, 6 13 16, 18 14 16, 17 18, 20 28/10/2010

B+ Tree Deletion Example : 

16 B+ Tree Deletion Example Index page underflow, so merge with sibling and demote 13 13, 16, 18 3, 4, 6 14 16, 17 18, 20 28/10/2010

Threaded Trees : 

17 Threaded Trees Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers We can use these pointers to help us in inorder traversals We have the pointers reference the next node in an inorder traversal; called threads We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer 28/10/2010

Threaded Tree Code : 

18 Threaded Tree Code Example code: class Node { Node left, right; boolean leftThread, rightThread; } 28/10/2010

Threaded Tree Example : 

19 Threaded Tree Example 8 7 5 3 11 13 1 6 9 28/10/2010

Threaded Tree Traversal : 

20 Threaded Tree Traversal We start at the leftmost node in the tree, print it, and follow its right thread If we follow a thread to the right, we output the node and continue to its right If we follow a link to the right, we go to the leftmost node, print it, and continue 28/10/2010

Threaded Tree Traversal : 

21 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Start at leftmost node, print it Output 1 28/10/2010

Threaded Tree Traversal : 

22 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Output 1 3 28/10/2010

Threaded Tree Traversal : 

23 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow link to right, go to leftmost node and print Output 1 3 5 28/10/2010

Threaded Tree Traversal : 

24 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Output 1 3 5 6 28/10/2010

Threaded Tree Traversal : 

25 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow link to right, go to leftmost node and print Output 1 3 5 6 7 28/10/2010

Threaded Tree Traversal : 

26 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Output 1 3 5 6 7 8 28/10/2010

Threaded Tree Traversal : 

27 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow link to right, go to leftmost node and print Output 1 3 5 6 7 8 9 28/10/2010

Threaded Tree Traversal : 

28 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow thread to right, print node Output 1 3 5 6 7 8 9 11 28/10/2010

Threaded Tree Traversal : 

29 Threaded Tree Traversal 8 7 5 3 11 13 1 6 9 Follow link to right, go to leftmost node and print Output 1 3 5 6 7 8 9 11 13 28/10/2010

Threaded Tree Traversal Code : 

30 Threaded Tree Traversal Code Node leftMost(Node n) { Node ans = n; if (ans == null) { return null; } while (ans.left != null) { ans = ans.left; } return ans; } void inOrder(Node n) { Node cur = leftmost(n); while (cur != null) { print(cur); if (cur.rightThread) { cur = cur.right; } else { cur = leftmost(cur.right); } } } 28/10/2010

Threaded Tree Modification : 

31 Threaded Tree Modification We’re still wasting pointers, since half of our leafs’ pointers are still null We can add threads to the previous node in an inorder traversal as well, which we can use to traverse the tree backwards or even to do postorder traversals 28/10/2010

Threaded Tree Modification : 

32 Threaded Tree Modification 8 7 5 3 11 13 1 6 9 28/10/2010