CPSC 319 Lecture Notes - Lecture 7: Parent Pointer Tree, Binary Search Algorithm, Linked List

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 319
• Professor: Leonard Manzara

Document Summary

A tree is a hierarchical data structure. Is a collection of vertices (nodes) and edges (arcs: a vertex contains data and pointer information, an edge connects 2 vertices. Is drawn to grow downwards: the root node is at the top of the structure. Each node, except the root, has only one node above it, called the parent node. A node may have zero or more children drawn below it. Nodes with the same parent are called twins or siblings. Nodes with no children are called leaf nodes: or terminal or external nodes. Any node is the root of a subtree: consists of it and the nodes below it. A set of trees is called a forest. A tree consists of levels with the root node at level 0: note: textbook numbers from 1, not 0. The height (depth) of a tree is the distance from the root to the node(s) furthest away: root node is at height 0.