COMPSCI 61B Lecture Notes - Lecture 21: Binary Tree, Binary Search Tree, Linked List

• School: Berkeley
• Department: Computer Science
• Course: COMPSCI 61B
• Professor: Joshua Hug

Document Summary

Fundamental problem with ordered linked list: slow get, containskey, and put. Change entry point, ip links: move pointer to middle build a bst. A set of edges that connects those nodes. There is only one path between any two nodes. In a rooted tree, we call one node the root. Every node n except the root has one parent ( rst node on the path from n to the root) A node with no child is a leaf. In a rooted binary tree, every node has 0, 1, or 2 children (subtrees) A binary search tree is a rooted binary tree with the bst property: for every node x in the tree, Every key in the left subtree is less than x"s key. Every key in the right subtree is greater than x"s key. Exactly one of p < q and q < p is true p < q and q < r imply p < r.