复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 06 Binary search trees

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

Trees(max heap PARENT(O 16 return i/2 LEFT( 14 10 return 2 5 6 8 9 3 RIGHTO return 2i+1 2 4 161410879324

T h) rees (max heap ) 1 PARENT ( i ) 16 PARENT ( i ) return ⎢⎣ i / 2⎥⎦ 1 2 3 14 10 LEFT ( i ) return 2 i 2 3 8 7 9 3 RIGHT ( i ) return 2 i + 1 4 56 7 return 2 i + 1 8 9 10 2 4 1 16 14 10 8 7 9 3 2 4 1

Binary trees 7o0 Not array!

Binary trees root[T] / / / / / / / / / / / / / Not array!

Binary search tree Each node x has keyI] Pointers 12 left 6 right plx] 7 8

Binary S hT earc ree y Each node x has: 9 5 12 – key[x] – Pointers: 1 6 y left[x] y right[x] 7 y right[x] y p[x] 8

Binary search tree Property: for any node x For all nodes v in the left subtree ofx 12 keyy]≤key{x For all nodes y in the right subtree of x 6 keyy]≥key{x 7 Given a set of keys, iS bst for those keys unique? 8

Binary S hT earc ree 9 y Property: for any node x: – For all nodes y in the left 5 12 For all nodes y in the left subtree of x: key[y] ≤ key[x] 1 6 key[y] ≤ key[x] – For all nodes y in the right subtree of x: 7 subtree of x: key[y] ≥ key[x] 8 y Given a set of keys, is BST for those keys unique? 8

No uniqueness 7 5 9 12 6 8 12 6 7 8

No uniqueness 7 9 5 12 5 9 1 6 8 12 1 6 7 8

What can we do given bst Sort INORDER-TREE-WALK(x) 1.ifx≠NII 2. then INORDER-TREE-WaLK(left[xD print keylxI INORDER-TREE-WALK(rightXD A preorder tree walk prints the root before the values in either subtree, and a postorder tree walk prints the root after the values in its subtrees

Wh d ST ? at can we do given BST ? Sort ! INORDER -TREE -WALK (x ) 1. if x ≠ NIL 2. then INORDER INORDER -TREE -WALK (l ft e [ x]) 3. print key [ x ] 4 INORDER 4. INORDER -TREE -WALK ( ri ht g [ ]) x A preord t lk er tree walk p ri t th t b f th i n ts the roo t b e fore the values in either subtree, and a postorder tree walk p ri t th t ft th l i it bt i n ts the roo t after the va lues in its subtrees

Sort

S ? ort 9 5 12 1 6 7 8

Sort

S ? ort 9 5 12 1 6 7 8

Sort

S ? ort 9 5 12 1 6 7 8