CMPSC 24 Lecture Notes - Lecture 16: Binary Search Tree, Binary Tree
Document Summary
Binary search tree of nodes --> its height is. Insert operation in binary search tree always adds a leaf to bst. Minimum element/key in bst is always a leaf (left-most) Is always a leaf or an interior node with at most one child, and that child has to be a right child. Node to be deleted has two children bool find(treenode* tree, string word) { if (tree == null) return false; else if (tree->data == word) return true; else if (tree->data < word) return find(tree->right, word); else . All values in the middle values: pointers. For d-ary tree: key < v1 --> find(left) key == v1 --> found key > v1 && key < v2 --> find(mid) key == v2 --> found key > v2 --> find(right) Need to maintain the two boundaries for the values. Unbalanced behavior minheap = an adt that implements prioirityq. Order property: for every node in the heap, its value is parent"s value.
