Textbook Notes (362,879)
United States (204,279)
COSC 2320 (8)
Chapter 35 - 37

# COSC 2320 Chapter 35 - 37: Chapter 35 - 37 Premium

2 Pages
25 Views

School
University of Houston
Department
Computer Science
Course
COSC 2320
Professor
Hilford Victoria
Semester
Spring

Description
Chapter 35-37 Ch.35: Binary trees • Binary tree – each node has up to two children o Leaf – tree node with no children o Internal node – node with at least one child o Parent – node with a child o Ancestors – include the node’s parent, the parent’s parent, etc., up to the tree’s root o Root – the one tree node with no parent (top node) o Edge – the link from a node to a child o Depth – number of edges on the path from the root to the node o Level – all nodes with the same depth o Height – the largest depth of any node • Binary search tree – has an ordering property that any node’s left subtree key <= the node’s key, and the right subtree’s key >= the node’s key. o Search – find a node with a desired key, if node exists ▪ Starts by searching root node o Worse case requires height + 1 comparisons ▪ O(height) o “all-but-last-level-full” binary tree’s height is h = floor_log(n) ▪ Ex: n = 15, h = 3 o Successor – node that comes after in the BST ordering o Predecessor – node that comes before in the BST ordering • BST search algorithm o Search – returns first ode found matching that key ▪ Returns 0 if no match o Starts at root ▪ If key is less • Assign current node to the left • repeat ▪ If key is more • Assign current node to the right • Repeat Chapter 37: Binary Search Tree • BST insert algorithm o Insert – inserts the new node in a proper location obeying the BST ordering property ▪ Insert as left child • If new node’s key is less than current node and current node’s left child is 0 o Assigns that node’s left child with the new node ▪ Insert as right child • If new node’s key is greater than t
More Less

Related notes for COSC 2320

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
Just a few more details

So we can recommend you notes for your school.