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