Search tree data structure supports search, max, min, insert, delete, predecessor and successor. Basic operation is bounded by the height of the tree(even though the worst case can have . Binary tree has a pointer to parent and left and right child.
Binary search tree
Binary search tree satisfy the binary search tree property: Let x be a node, if y is a left child of x, x.key > y.key. If y is a right child of x, then x.key < y.key.
The binary search tree allows us to print the node in sorted order through in order traversal.
in-order(x): if x != null: in-order(x.left) print(x.key) in-order(x.right)
This algorithm will go down to the far left until it reaches the leftest element. It will attempt to find leftest element’s children, but there isn’t any so it only prints and go back up to the parent that called it. The parent is the next node to be printed, then the right node of the parent. This pattern goes on… Essentially we are squashing down the tree such that the parents fit between the two children and make a sorted list.
It takes time to in order walk through the tree.
Min heap property
the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root. It is different from binary tree property because min heap only knows the relationship between children and parent, not between children. On the contrary, we know the left child is smaller than the parent and the right child.
Non recursive in order
We can use a stack as a aux data structure to hold parent’s value. 1. we init an empty stack 2. we init current node as root 3. push the current node onto the stack and set the current = current.left 4. If current is null and the stack is not empty then we pop the stack, print it and set current = poped.right. Then we go to step 3 5.If the stack is empty, we are done.
non-recurse-inorder(x): stack s current = root While not s.isEmpty() or current == root: if current != Null: s.push(current) current = current.left else: poped = s.pop() #pop the parent print(poped) current = poped.right
Pre order traversal
In preorder, we want to print the root before the children.
pre-order(x): if x != null: print(x.key) pre-order(x.left) pre-order(x.right)
Post order traversal
In post order, we want to print the root after the children
if x! = null: pre-order(x.left) pre-order(x.right) print(x.key)
Argue that since sorting n elements takes O(nlgn) time in the worst case in
the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements takes O(nlgn) time in the worst case.
Suppose not, then we can construct a binary search tree in o(nlgn) time(not big O, it means it is strictly smaller than nlgn). Then we can just do a in-order traversal and print. In order takes O(n) so sorting is o(nlgn) instead of O(nlgn) =><= so constructing binary search tree must be O(nlgn).
Querying a binary search tree
We want to find max, min and search. All of these operations are bounded by the height of the tree.
tree-search(x,k): if x.key == k or x == null: return x if x.key < k: tree-search(x.right, k) else: tree-search(x.left, k)
This search will form a path in the BST and if we didn’t find it, it will return null. This is very helpful. One less boundary check.
An iterative version is:
tree-iter-search(x,k): while x.key != k or x!= null: if x.key < k: x = x.right else: x = x.left return x
If we found x.key == k, then we will return the node. Else we will go to the bottom of the tree and return null.
find min and find max
find_min(x): while x.left != null: x = x.left return x
the min is the left most node of the tree.
Same with find max. find max is at the right most of the tree.
find_max(x): while x.right != null: x = x.right return x ###successor and predecessor If all keys are distinct, then successor of x will be the element with the smallest value that's bigger than x.key ```python successor(x): if x.right != null: return find_min(x.right) y = x.parent while y != null and x == y.right: x = y y = y.parent return y
The code has two section, the first one is when our node has a right node, then the next biggest would be the right node’s min. The second part of the when the node is a right node and has no right node. Then traverse back the tree until the current node is a left node of the parent y. then that parent would be bigger than the node under exam.
recursive find max and find min
find_max_recurse(x): if x.right == null: return x x = x.right find_max_recurse(x)
find_predecessor(x): if x.left != null: return find_max(x.left) else: return x.parent
Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.
If a node has two children x.left and x.right, then the successor will be the min of the subtree rooted at x.right. it will be the left most child of the subtree therefore no left child. The predecessor will be the max of the subtree rooted at x.left. If predecessor has right child then it won’t be the max. (This can be proved using contradiction)
predecessor and ancestor II
Consider a binary search tree T whose keys are distinct. Show that if the right subtree of a node x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. (Recall that every node is its own ancestor.)
Insert and delete
We insert through traverse through the tree till we hit a null that can fit our inserted node.
We need to alter the tree and z
insert(T,z): y = null x = T.root while x != null: y = x if z.key > x.key: x = x.right else x = x.left #Now we have traverse till null, y points to last not-null node if y == null: #if the tree is empty: T.root = z if z.key > y.key: y.right = z elif z.key < y.key y.left = z
Delete is more intricate since we might need to move more than 1 nodes around We have 4 cases when trying to remove z
1. The deleted node z has no left child: replace z with z's right child 2. The deleted node z has no right child: replace z with z's left child 3. The deleted node z has two child and its predecessor is its right child(right child has no left child). replace z with z's right child. 4. The deleted node z has two child and its predecessor isn't its right child(right child has left child). We need to traverse down z's right child until we find the leftmost node *left_most*, which is the predecessor of z. Then replace *left_most* with it's right child(recall predecessor shouldn't have left child). Then we replace z with *left_most*. The graphs on p297 might be helpful. We will need a transplant subroutine which will point one node's parent point to another node. (It won't change what the node children though).
insert(r, x): if r == null: if x.key > r.parent.key : r.parent = x else r.parent.left = x else: if x.key > r.key: insert(r.right, x) else insert(r.left, x)
nodes examined for searching
Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.
When the node was first inserted, assume it takes n steps. It takes the same path as the path to search for this node since both these steps use the same comparison method. We need to traverse over the searched node to reach null to return. That’s where the + 1 comes from.
Another kind of insertion sort
We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worstcase and best-case running times for this sorting algorithm?
The worst case for tree insertion is to insert in increasing order. That would require us to traverse the whole list to insert. (1 + 2 + 3 + … + n- 1 + n) That would be