CLRS chpt 12 Binary tree

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 \Theta(n). 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 O(N) time to in order walk through the tree.

Exercise

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

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.

Exercise:

recursive find max and find min

find_max_recurse(x):
    if x.right == null:
        return x
    x = x.right
    find_max_recurse(x)

Tree predecessor

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).

Exercise

recursive insert

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 \Theta(n^2)

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax