CSC263H1 Lecture 6: CSC263-Notes-01-21-2015
Document Summary
Search,delete,insert (1), but space is an issue! space o(n) where n is the size of the keyspace. 9 search(s,k): return treesearch(s. root,k) treesearch(root, k): if root == null: # return null pass else if k < root. item. key: root = treesearch(root. left, k) else if k > root. item. key: root = treesearch(root. right, k) else: 9 insert(s,x): treeinsert(s. root, x) treeinsert(root, x): if root == null: root = treenode(x) else if x. key < root. item. key: root. left = treeinsert(root. left, x) else if x. key > root. item. key: root. right = treeinsert(root. right, x) else. If x is not found do nothing. If x is found in a leaf remove the leaf. If x has only one sub-tree, remove x and shift the subtree up to replace x (splice around x) # remove root. item if root. left == null or root. right == null: # root missing one child, replace with other child if root. left == null: root = root. right # null if both children are missing else: root = root. left else:
