二叉查找树

二叉查找树中关键字的存储方式总是满足以下的二叉查找树性质：

  • 设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则Day 9 - 图1。如果y是x的右子树中的结点，则Day 9 - 图2。

根据二叉树的性质，可以用一个递归算法按排列顺序输出树中的所有关键字，即中序遍历算法。

  1. public void inOrderTreeWalk(TreeNode x){
  2.     if(x！=null){
  3.         inOrderTreeWalk(x.left);
  4.         System.out.println(x);
  5.         inOrderTreeWalk(x.right);
  6.     }
  7. }

定理 ：如果x是一棵包含n个结点的子树的根，则调用InOrderTreeWalk(x)过程的时间为Θ(n)。

查询二叉查找树

查找一个给定的关键字 

public TreeNode treeSearch(TreeNode x, int k){
    if(x==null || x.val==k){
        return x;
    }
    if(k<x.val)
        return treeSearch(x.left,k);
    else
        return treeSearch(x.right.k);
}

也可以用非递归算法（While循环）来实现，在大多数计算机上，非递归版本运行的要更快一些。

public iterativeTreeSearch(TreeNode x, int k){
    while(x!=null && k!=x.val){
        if(k<x.val)
            x = x.left;
        else
            x = x.right;
    }
    return x;
}

最大关键字元素和最小关键字元素 

public TreeNode treeMinimun(TreeNode x){
    while(x.left!=null){
        x = x.left;
    }
     return x;
}

最大关键字类似。对高度为h的树，这两个过程的运行时间都是O(h)。
前趋和后继
给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继，如果所有的关键字均不相同，则某一个结点x的后继即具有大于key[x]中的关键字中的最小值的那个结点。
若s的右子树为空，则从x向上查找，直到遇到某个是其父节点的左儿子的结点为止。

TREE-SUCCESSOR(x)
if right[x]!=null{
    then return treeMinimum(x.right);
y = p[x]
whilr y!=null and x = right[y]
    do x = y
     y = p[y]
return y

删除和插入

插入 

public void treeInsert(TreeNode x, int z){
    TreeNode pre = null;
    TreeNode cur = x;
    while(cur!=null){
        pre = cur;
        if(z<x.val)
            cur = cur.left;
        else
            cur = cur.right;
    }
    if(pre==null)
        x = new TreeNode(z);
    else if(z<pre.val)
        pre.left = new TreeNode(z);
    else
        pre.right = new TreeNode(x);
}

和其他查找树上的原始操作一样，过程TreeInsert的运行时间也为O(h).
删除
给定结点z从二叉查找树中删除的过程以指向z的指针为参数，并考虑三种情况：1）如果z没有子女，则修改其父节点p[z]，使NIL为其子女；如果结点z只有一个子女，则通过在其子节点与父节点间建立一条链来删除z。最后，如果结点z有两个子女，先删除z的后继y（没有左儿子），再用y的内容来替代z的内容。 以下代码并不完善 

public void treeDelete(TreeNode z){
    if(z.left==null && z.right==null){
        //没有孩子
        p[z].next = null; //其父节点连接null
    }else if(z.right!=null && z.left!=null){
        x = treeMinimum(z.right);
        z.val = x.val;
        treeDelete(x);
    }else if(z.right !=null){
        p[z].next = z.right;
    }else{
        p[z].next = z.left;
    }
}

定理 对高度为h的二叉查找树，动态集合操作INSERT和DELETE的运行时间为O(h)。
The Relation to QuickSort:
BST Sort & QuickSort make same comparisons but in a different order.

随机构造的二叉树

步骤 ：

  • Randomly permite A
  • BST Sort(A)

Time(BST) = Time(Randomized-QuickSort)
定理
一棵在n个关键字上随机构造的二叉查找树的期望高度为O(lgn)。