Notes - Imperative Programming HT23, Binary search trees
Flashcards
What is the binary-search tree property?
For any node $x$ in a binary search tree, with left and right subtrees $l$ and $r$ respectively,
\[l\text{.key} \le x\text{.key} \le r\text{.key}\]Can you give the pseudocode for deleting data from a binary search tree, assuming we have
private class Tree(var data: Int, var left: Tree, var right: Tree)
and we’re within an object with the root stored at root?
data from a binary search tree, assuming we haveprivate class Tree(var data: Int, var left: Tree, var right: Tree)
root?def delete(data: Int) : Unit = {
root = deleteHelper(data, root)
}
def deleteHelper(data: Int, t: Tree) = {
if (t == null) {
return null
} else if (data < t.data) {
t.left = deleteHelper(data, t.left);
return t
} else if (data > t.word) {
t.right = deleteHelper(data, t.right)
return t
} else if (t.left == null) { // From now on t.data == data
// Delete this node by shifting right subtree up
return t.right
} else if (t.right == null) {
// Delete this node by shifting left subtree up
return t.left
} else {
// Both left and right nodes are full, oh no
// We need to replace this node with the smallest
// thing bigger than it
val (d, newR) = delMin(t.right)
t.data = d
t.right = newR
return t
}
}
def delMin(t: Tree) : (Int, Tree) = {
if (t.left == null) { t.data, t.right }
else {
val (d, newL) = delMin(t.left)
t.left = newL
(d, t)
}
}
Programs
Implement a binary search tree for storing a bag of words that supports:
- search
- minimum
- maximum
- predecessor
- successor
- insert
- delete
.
Todo.