CSC148H1 Lecture Notes - Branching Factor, Longest Path Problem, Self-Balancing Binary Search Tree
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
A tree has a set of nodes and a set of edges that connect the nodes. Properties: each node has exactly one parent. Except the root, which has none: there is a path from the root to every node, there are no cycles: no paths that form loops. If m1 is the parent of m2, m2 is the parent of m3, , and mk-1 is the parent of mk, then the sequence of nodes m1, m2, , mk is a path in the tree. Binary search tree (bst: a binary tree where the nodes are labeled, each node"s label is: Greater than the labels of all the nodes in its left subtree. 14 becomes left child of 17, 17 becomes new root: height. Max height of a binary tree with n nodes is n (all in 1 line) The minimum height of a binary tree is ) ) Shape of minium height tree with n nodes models a balanced tree.
