CMPSC 24 Lecture Notes - Lecture 8: Binary Search Algorithm, Binary Search Tree, Binary Tree
Document Summary
A tree has the following general properties: One node is distinguished as a root (node pointer) Every node (exclude a root) is connected by a directed edge from exactly one other node. Leaf node: node that has no children (2, 5, 11, 4) Key: the data that is stored inside a node. Ex: 2 (parent) has a link to 7 and 5 (children) Each node can only be reached through 1 node. Bi-directional access (parent can access children, children can access parent) A: d) a & b; single node tree. Binary tree: a tree where every node can have at most 2 children (designed for fast search) Same operations as a linkedlist or an array. Has a pointer to the left child, right child and parent (optional) For any node, the keys in the node"s left subtree <= node"s key and the keys in a node"s right subtree > node"s key. Has to be true relative to the parent.
