Class Notes (807,339)
CPSC 319 (12)
Lecture 7

# CPSC 319 Lecture 7: 07 Trees

5 Pages
64 Views

School
University of Calgary
Department
Computer Science
Course
CPSC 319
Professor
Leonard Manzara
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.