Sorting Does it mean that we can sort n keys in O(n) time? No It just means that building a binary search tree takes Q2(nlgn )time (in the comparison model)
Sorting Does it mean that we can sort n keys in O(n) time? No. It just means that building a binary search tree takes search tree takes Ω(nlgn) time (in the comparison model)
bst as a data structure ° Operations Insert(x) Delete(x) 12 -Search(k) 6 7 8
BST d as aata structure y Operations: 9 – Insert(x) – Delete(x) 5 12 – Search(k) 1 6 7 8
Search TREE-SEARCH(x k 1. ifx=Nil or k=key] 2. then return x 3.ifk≤key{x] 4. then return TREE-SEARCH(left, k) 5. else return TREE-SEARCH(right[x], k)
S h earc TREE-SEARCH(x, k) 1. if x = NIL or k = key[x] 2. then return x 3. if k < key[x] 4. then return TREE-SEARCH(left[x], k) 5. else return TREE-SEARCH(right[x], k)
Search ITERATIVE-TREE-SEARCH( k 1. while x≠ NIL and k≠key{x] 2. do if k< key 345 then x←lefx] else x← rightly] return x On most computers, this version is more efficient
S h earc ITERATIVE-TREE-SEARCH(x, k) 1. while x ≠ NIL and k ≠ key[x] 2. do if k < key[x] 3. then x ← left[x] 4. else x ← right[x] 5. return x On most computers, this version is more efficient. On most computers, this version is more efficient
Minimum and maximum TREE-MINIMUM() 1. while lefi[x]≠NL 2.dox←lefx] 3. return x 12 TREE-MAXIMUM() 6 1. while right]≠NL 2.dox← rightly] 7 3. return x 8
Minimum and maximum TREE-MINIMUM(x) 1. while left[x] ≠ NIL 9 f [ ] ≠ 2. do x ← left[x] 3. return x 5 12 TREE-MAXIMUM(x) 1 6 TREE MAXIMUM(x) 1. while right[x] ≠ NIL 2. do x ← right[x] 7 2. do x ← right[x] 3. return x 8