Page 1 Binary Search Trees (13.1/12.1) • Support Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete • In addition to key each node has – left = left child, right = right child, p = parent • Binary search tree property: – all keys in the left subtree of x = key[x] – all keys in the right subtree of x = key[x] • Resembles quicksort Page 2 Binary Search Trees (13.1/12.1) • Support Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete • In addition to key each node has – left = left child, right = right child, p = parent • Binary search tree property: – all keys in the left subtree of x = key[x] – all keys in the right subtree of x = key[x] • Resembles quicksort In-Order-Tree Walk • Procedure In-Order-Tree(x) (O(n)) – In-Order-Tree(left[x]) – print key[x] – In-Order-Tree(right[x]) 7 5 6 3 6 2 8 9 4 Page 3 Binary Search Trees (13.1/12.1) • Support Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete • In addition to key each node has – left = left child, right = right child, p = parent • Binary search tree property: – all keys in the left subtree of x = key[x] – all keys in the right subtree of x = key[x] • Resembles quicksort In-Order-Tree Walk • Procedure In-Order-Tree(x) (O(n)) – In-Order-Tree(left[x]) – print key[x] – In-Order-Tree(right[x]) 7 5 6 3 6 2 8 9 4 Searching (13.2/12.2) Searching (O(h)): Given pointer to the root and key Find pointer to a nod with key or nil Procedure Tree-Search(x,k) if k = key[x], then return x if k < key[x] then return Tree-Search(left[x]) else return Tree-Search(right[x]) Iterative Tree-Search(x,k) while k ? key[x] do if k < key[x] then x ? left[x] else x ? right[x] return x 7 5 6 3 6 2 8 9 4 Page 4 Binary Search Trees (13.1/12.1) • Support Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete • In addition to key each node has – left = left child, right = right child, p = parent • Binary search tree property: – all keys in the left subtree of x = key[x] – all keys in the right subtree of x = key[x] • Resembles quicksort In-Order-Tree Walk • Procedure In-Order-Tree(x) (O(n)) – In-Order-Tree(left[x]) – print key[x] – In-Order-Tree(right[x]) 7 5 6 3 6 2 8 9 4 Searching (13.2/12.2) Searching (O(h)): Given pointer to the root and key Find pointer to a nod with key or nil Procedure Tree-Search(x,k) if k = key[x], then return x if k < key[x] then return Tree-Search(left[x]) else return Tree-Search(right[x]) Iterative Tree-Search(x,k) while k ? key[x] do if k < key[x] then x ? left[x] else x ? right[x] return x 7 5 6 3 6 2 8 9 4 Min-Max, Successor-Predecessor • MIN: go to the left x ? left[x] • MAX: go to the right x ? right[x] • Procedure Tree-Successor(x) – if right[x] ? nil then return MIN(right[x]) – y = p[x] – while y ? nil and x = right[y] • x ? y • y ? p[y] – return y 7 5 6 3 6 2 8 9 4 Page 5 Binary Search Trees (13.1/12.1) • Support Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete • In addition to key each node has – left = left child, right = right child, p = parent • Binary search tree property: – all keys in the left subtree of x = key[x] – all keys in the right subtree of x = key[x] • Resembles quicksort In-Order-Tree Walk • Procedure In-Order-Tree(x) (O(n)) – In-Order-Tree(left[x]) – print key[x] – In-Order-Tree(right[x]) 7 5 6 3 6 2 8 9 4 Searching (13.2/12.2) Searching (O(h)): Given pointer to the root and key Find pointer to a nod with key or nil Procedure Tree-Search(x,k) if k = key[x], then return x if k < key[x] then return Tree-Search(left[x]) else return Tree-Search(right[x]) Iterative Tree-Search(x,k) while k ? key[x] do if k < key[x] then x ? left[x] else x ? right[x] return x 7 5 6 3 6 2 8 9 4 Min-Max, Successor-Predecessor • MIN: go to the left x ? left[x] • MAX: go to the right x ? right[x] • Procedure Tree-Successor(x) – if right[x] ? nil then return MIN(right[x]) – y = p[x] – while y ? nil and x = right[y] • x ? y • y ? p[y] – return y 7 5 6 3 6 2 8 9 4 Insertion (13.3/12.3) 7 5 6 3 6 2 8 9 4 O(h) operationRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!