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

COSC 2320 Chapter 35 - 37: Chapter 35 - 37

2 Pages
Unlock Document

University of Houston
Computer Science
COSC 2320
Hilford Victoria

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

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


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.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.