6.1 Binary Search Trees Flashcards
For search,Insert/delete,Min/Max and Predecessor/Successor operations what is the runtime complexity when implementing via a Binary Search Tree
theta(h)
h = height of tree (logn)
Definition of height of tree
Number of edges on longest root-to-leaf path
What is recursive definition for the height of a tree
Starting from the root:
1 + max{h(TL), h(TR)}
TL = subtree to the left
TR = subtree to the right
Properties of a binary search tree
All nodes in the left subtree are less than its root
All nodes in the right subtree are greater than or equal than its root
Max 2 children
Describe how an In order Traversal outputs the nodes in value order
Recursively traverse the left subtree of the root.
Output the value of the root.
Recursively traverse the right subtree of the root.
Running time complexity for In order traversal
O(n)
What is the output of the in order traversal for this tree
dbehafch
How would a search for a node be implemented recursively?
NodeSearch(key k, Node x = root)
if x = nil or x.key then return x
else if k < x.key then return NodeSearch(k, x.left)
else
return NodeSearch(k, x.right)
How would a search for a node be implemented iteratively?
while not nil and x.key not k
if k < x.key then x = x.left
else x = x.right
return x
What is a successor to a node x
Give its mathematical definition as well
node with smallest key that is also greater than x.key
arg min y {y.key|y.key > x.key}
what does y = x. p mean
x. p means x’s parent so y = x’s parent
How do you delete the root (or any node that isnt a leaf)? (has 2 children)
Find the roots successor, set that as the new root.
Recurse this operation, deleting the successor that just got placed at the root.
How do you delete a leaf node z
Determine if z is the left or right child of z. p
Set that left/right pointer to nil
How to delete a node z that has one child x
Set pointer from z. p to z to point to x
What is best case and worst case runtime complexity for a BST?
The heigh which
Best case: O(log(n))
Worst case: theta(n) when each node has one child so the height is n
