COMP 352 Lecture 21: Binary Search Tree

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

Binary search (o(log n): get(k): o(log n, put(k, v): o(n, remove(k): o(n) A bst is a binary tree storing (key, value) pairs at its internal node satisfying the following properties: Let u, v, and w be three internal nodes such that u is in the left subtree of v and w is in the right subtree of v. then, key(u) <= key(v) <= key(w). Algorithm treesearch(k, v) if t. isexternal (v) return v if k < key(v) return treesearch(k, left(v)) else if k = key(v) return v else { k > key(v) } return treesearch(k, right(v)) Insertion: put(k, v: call treesearch(k, root, if k is not found then it will return an external node, insert(k, v) in the external node, make its two children as external nodes. Removal remove(k: call treesearch(k, root, suppose v is the node storing k. Once child of v is an external node, we call it u. See last slide of binary search tree for performance.