Class Notes
(807,339)

Canada
(492,708)

University of Calgary
(6,012)

Computer Science
(115)

CPSC 319
(12)

Leonard Manzara
(12)

Lecture 7

# CPSC 319 Lecture 7: 07 Trees

Unlock Document

University of Calgary

Computer Science

CPSC 319

Leonard Manzara

Winter

Description

Trees
Introduction
- A tree is a hierarchical data structure
- Is a collection of vertices (nodes) and edges (arcs)
o A vertex contains data and pointer information
o An edge connects 2 vertices
- Is drawn to grow downwards
o 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
o Or terminal or external nodes
- Any node is the root of a subtree
o 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
o 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
o Root node is at height 0
- The path length is the sum of edges from each node to the root
- With ordered trees, the order of the children at every node is specified
o Are much more useful than unordered trees
Binary Trees
- Are trees where every node has 0, 1, or 2 children
- Each node contains:
o Data
o A left child pointer
o A right child pointer
o A parent pointer (optional)
- A root pointer is used to point to the root node
- In Java, each node is an object of a class such as the following:
public class Node {
private int data;
private Node parent, left, right;
private Node(int el, Nod e p, Node l, Node r) {
data = el;
parent = p;
left = l;
right = r;
}
// ...
} Binary Search Trees
- Also called ordered binary trees
- Are binary trees organized so that:
o Every left child is less than (or equal to) the parent node
o Every right child is greater than the parent node
- All nodes in any left subtree will be less than (or equal to) the parent node
- All nodes in any right subtree will be greater than the parent node
- Different binary search trees can represent the same data
o The shape of the tree depends on the order of insertion
- In the best case, the tree is balanced and the height is minimized
o Height is approximately lg #
- In the worst case, the tree degenerates into a linked list
o Height is # − 1
- If the tree is well balanced, searches are efficient
o < lg#
o Related to the binary search of a sorted array
Insertion in a Binary Search Tree:
- Requires a search of the existing tree, to find the parent node of the new node
- New nodes are always added as leaf nodes
- The new node is then attached to the parent
- If the tree is empty, then the new node becomes the root node
- Iterative implementation
public void insert(int el, Node root)
{
Node current = root, parent = null;
while(current != null)
{
parent = current;
if (el > current.data)
current = current.right;
else
current = current.left;
}
if (root == null)
root = new Node(el, parent, null, null);
else if (el > parent.data)
parent.right = new Node(el, parent, null, null);
else
parent.left = new Node(el, parent, null, null);
} Traversal in a Binary Search Tree:
- To traverse a tree, all nodes are visited once in some prescribed order
- Two types:
o Depth-first: recursively visit each node starting at the far left (or right)
o Breadth-first: starting at the highest level, move down level by level, visiting
nodes on each level
§ Can also start at the bottom, or traverse from right to left
- Depth-first, in-order traversal
o Visits nodes in ascending order

More
Less
Related notes for CPSC 319