CSI 2110 Lecture Notes - Lecture 6: Binary Tree
7 Nov 2017
School
Department
Course
Professor
Document Summary
A graph g=(v,e) consists of a set v of vertices and a set e of edges with e={(u,v): u,v in v, u!=v} A tree is a connected graph with no cycles. Internal node: a node with at least one child. Ancestors of a node: nodes directly above a node. Descendants of a node: nodes directly below a node. Subtree: a tree consisting of a node and its descendants. Distance between two nodes: the number of edges between them. Height of a tree: maximum depth of any node. Each node has a maximum of two children. A full binary tree each node has either 0 or 2 children. A perfect binary tree is a full binary tree with all leaves at the same depth. Summary of important properties (n=nodes, e=leaves, i=internal nodes, h=height) 2h+1 <= n <= 2h+1-1 h+1 <= e <=2h h <= i <= 2h-1 log(n+1) -1 <= h <= (n-1)/2.
