Textbook Notes
(362,879)

United States
(204,279)

University of Houston
(754)

Computer Science
(8)

COSC 2320
(8)

Hilford Victoria
(8)

Chapter 35 - 37

Unlock Document

University of Houston

Computer Science

COSC 2320

Hilford Victoria

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