CMSC 132 Object Oriented Programming II Advanced Tree Structures Department of Computer Science University of Maryland College Park 1 Overview Binary trees Balance Rotation Multi way trees Search Insert Indexed tries 2 Tree Balance Degenerate Worst case Search in O n time Degenerate binary tree Balanced Average case Search in O log n time Balanced binary tree 3 Tree Balance Question Can we keep tree mostly balanced Self balancing binary search trees AVL trees Red black trees Approach Select invariant that keeps tree balanced Fix tree after each insertion deletion Maintain invariant using rotations Provides operations with O log n worst case 4 AVL Trees Properties Binary search tree Heights of children for node differ by at most 1 Example 4 44 2 3 17 78 1 2 32 Heights of children shown in red 88 50 1 48 62 1 1 5 AVL Trees History Discovered in 1962 by two Russian mathematicians Adelson Velskii Landis Algorithm 1 Find insert delete as a binary search tree 2 After each insertion deletion a If height of children differ by more than 1 b Rotate children until subtrees are balanced c Repeat check for parent until root reached 6 Red black Trees Properties Binary search tree Every node is red or black The root is black Every leaf is black All children of red nodes are black For each leaf same of black nodes on path to root Characteristics Properties ensures no leaf is twice as far from root as another leaf 7 Red black Trees Example 8 Red black Trees History Discovered in 1972 by Rudolf Bayer Algorithm Insert delete may require complicated bookkeeping rotations Java collections TreeMap TreeSet use red black trees 9 Tree Rotations Changes shape of tree Move nodes Change edges Types Single rotation Left Right Double rotation Left right Right left 10 Tree Rotation Example Single right rotation 2 3 2 1 3 1 11 Tree Rotation Example Single right rotation 3 5 3 2 1 2 6 4 1 5 4 6 Node 4 attached to new parent 12 Example Single Rotations 1 2 1 single left rotation 3 2 3 T0 T3 T1 T3 T2 3 1 T3 T2 T1 T2 2 single right rotation 2 T0 T0 1 3 T0 T1 T2 T3 T1 13 Example Double Rotations right left 3 double rotation 1 2 1 3 2 T0 T3 T2 T1 3 T0 T1 T3 2 left right double rotation 1 1 T2 3 2 T3 T0 T1 T0 T1 T2 T3 T2 14 Multi way Search Trees Properties Generalization of binary search tree Node contains 1 k keys in sorted order Node contains 2 k 1 children Keys in jth child jth key keys in j 1 th child Examples 5 2 12 8 5 8 15 33 17 1 3 7 9 19 21 44 15 Types of Multi way Search Trees 5 2 3 tree Internal nodes have 2 or 3 children 2 8 Index search trie 17 c Internal nodes have up to 26 children for strings a B tree T minimum degree Non root internal nodes have T 1 to 2T 1 children All leaves have same depth 12 o s T 1 2T 1 1 2 2T 16 Multi way Search Trees Search algorithm 1 Compare key x to 1 k keys in node 2 If x some key then return node 3 Else if x key j search child j 4 Else if x all keys search child k 1 Example 25 Search 17 5 1 2 12 8 30 40 17 27 36 44 17 Multi way Search Trees Insert algorithm 1 Search key x to find node n 2 If n not full insert x in n 3 Else if n is full a Split n into two nodes b Move middle key from n to n s parent c Insert x in n d Recursively split n s parent s if necessary 18 Multi way Search Trees Insert Example for 2 3 tree Insert 4 5 2 12 8 5 17 2 4 12 8 17 19 Multi way Search Trees Insert Example for 2 3 tree 5 Insert 1 5 124 2 12 8 1 17 Split node 4 8 4 8 17 Split parent 2 5 12 1 12 17 20 B Trees Characteristics Height of tree is O logT n Reduces number of nodes accessed Wasted space for non full nodes Popular for large databases 1 node 1 disk block Reduces number of disk blocks read 21 Indexed Search Tree Trie Special case of tree Applicable when Key C can be decomposed into a sequence of subkeys C1 C2 Cn Redundancy exists between subkeys Approach C1 Store subkey at each node Path through trie yields full key C2 Example C3 Huffman tree C3 C4 22 Tries Useful for searching strings String decomposes into sequence of letters Example ART A R T A Can be very fast Less overhead than hashing R S May reduce memory Exploiting redundancy May require more memory Explicitly storing substrings E T ART 23 Types of Tries Standard Single character per node Compressed Eliminating chains of nodes Compact Stores indices into original string s Suffix Stores all suffixes of string 24 Standard Tries Approach Each node except root is labeled with a character Children of node are ordered alphabetically Paths from root to leaves yield all input strings Trie for Morse Code 25 Standard Trie Example For strings a an and any at 26 Standard Trie Example For strings bear bell bid bull buy sell stock stop b e s i a l r l d u l l y e t l o l c p k 27 Standard Tries Node structure Value between 1 m Reference to m children Array or linked list Example Class Node Letter value Node child m Letter V V1 V2 Vm 28 Standard Tries Efficiency Uses O n space Supports search insert delete in O d m time For n total size of strings indexed by trie d length of the parameter string m size of the alphabet 29 Word Matching Trie Insert words into trie Each leaf stores occurrences of word in the text s e e a b e a r s e l l s t o c k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 s e e a b u l l b u y s t o c k 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 b i d s t o c k b i d s t o c k 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 h e a r t h e b e l l s t o p 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 b e h i a l r l 6 78 d …
View Full Document
Unlocking...