二叉查找树

二叉查找树定义

二叉查找树(Binary Search Tree), 也称为二叉搜索树, 有序二叉树(ordered binary tree), 排序二叉树(sorted binary tree), 是指一颗空树或具有以下性质的二叉树:
1. 任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值
2. 任意节点的右子树不空, 则右子树上所有节点均大于它的根节点的值
3. 任意节点的左,右子树也分别为二叉查找树
4. 没有键值相等的节点

二叉查找树通常采用二叉链表作为二叉查找树的存储结构, 相比于其他数据结构的优势在于查找,插入时间复杂度较低, 为O(log n). 它是基础的数据结构, 用于构建 红黑数, B-Tree, B+Tree, B*Tree等.

二叉查找树的Java实现

1. 二叉查找树节点定义

public class BSTNode<T extends Comparable<T>> {
    T key;                // 关键字(键值)
    BSTNode<T> left;    // 左孩子
    BSTNode<T> right;    // 右孩子
    BSTNode<T> parent;    // 父结点

    public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
        this.key = key;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    public T getKey() {
        return key;
    }

    public String toString() {
        return "key:"+key;
    }
}

BSTNode是二叉查找树的内部节点, 它包含以下信息:

1. key 对二叉树进行排序的依据
2. left 左边子节点
3. right 右边子节点
4. parent 当前节点的父节点

2. 二叉查找树的查找

/*
 * (递归实现)查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> search(BSTNode<T> x, T key) {
    if (x==null)
        return x;

    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        return search(x.left, key);
    else if (cmp > 0)
        return search(x.right, key);
    else
        return x;
}

public BSTNode<T> search(T key) {
    return search(mRoot, key);
}

search 的过程比较简单, 从根节点开始, 根据给定的key与节点的key值进行比较, 直到 "cmp" = 0 或节点x = 0.

3. 查找最大值, 最小值

最大值

/*
 * 查找最大结点：返回tree为根结点的二叉树的最大结点。
 */
private BSTNode<T> maximum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.right != null)
        tree = tree.right;
    return tree;
}

public T maximum() {
    BSTNode<T> p = maximum(mRoot);
    if (p != null)
        return p.key;

    return null;
}

最小值

/*
 * 查找最小结点：返回tree为根结点的二叉树的最小结点。
 */
private BSTNode<T> minimum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.left != null)
        tree = tree.left;
    return tree;
}

public T minimum() {
    BSTNode<T> p = minimum(mRoot);
    if (p != null)
        return p.key;

    return null;
}

4. 查找前继节点(predecessor) 后继节点(successor)

查找前继节点

/*
 * 找结点(x)的前继结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
 */
public BSTNode<T> predecessor(BSTNode<T> x) {
    // 如果x存在左孩子，则"x的前继结点"为 "以其左孩子为根的子树的最大结点"。
    if (x.left != null)
        return maximum(x.left);

    // 如果x没有左孩子。则x由分以下两种情况讨论：
    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且x在该父结点右子树上孩子或是其又子节点"，找到的这个"最低的父结点"就是"x的前继结点"。
    BSTNode<T> y = x.parent;
    while ((y!=null) && (x==y.left)) {
        x = y;
        y = y.parent;
    }

    return y;
}

查找后继节点

/*
 * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
 */
public BSTNode<T> successor(BSTNode<T> x) {
    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
    if (x.right != null)
        return minimum(x.right);

    // 如果x没有右孩子。则x分以下两种情况进行讨论：
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且x是该父结点左子树上的孩子节点或直接是左子节点"，找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode<T> y = x.parent;
    while ((y!=null) && (x==y.right)) {
        x = y;
        y = y.parent;
    }

    return y;
}

5. 插入节点

/*
 * 将结点插入到二叉树中
 *
 * 参数说明：
 *     tree 二叉树的
 *     z 插入的结点
 */
private void insert(BSTree<T> bst, BSTNode<T> z) {
    int cmp;
    BSTNode<T> y = null;
    BSTNode<T> x = bst.mRoot;

    // 1. 查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp < 0)
            x = x.left;
        else
            x = x.right;
    }

    //2. 根据位置决定放在root节点, y的左/右边
    z.parent = y;
    if (y==null) // y是null
        bst.mRoot = z;
    else {
        cmp = z.key.compareTo(y.key);
        if (cmp < 0)
            y.left = z;
        else
            y.right = z;
    }
}

/*
 * 新建结点(key)，并将其插入到二叉树中
 *
 * 参数说明：
 *     tree 二叉树的根结点
 *     key 插入结点的键值
 */
public void insert(T key) {
    BSTNode<T> z=new BSTNode<T>(key,null,null,null);

    // 如果新建结点失败，则返回。
    if (z != null)
        insert(this, z);
}

5. 删除节点

/*
 * 删除结点(z)，并返回被删除的结点
 *
 * 参数说明：
 *     bst 二叉树
 *     z 删除的结点
 */
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
    BSTNode<T> x=null;
    BSTNode<T> y=null;
    /** 1. 待删除节点情况
     * 1) 节点z最多一个子节点, 则删除z后将对应子节点代替原来的位置
     * 2) 节点有两个子节点, 调用 successor方法获取其后继节点, 后继节点代替原来的那个节点
     */
    if ((z.left == null) || (z.right == null) )
        y = z; // 节点z最多有一个子节点
    else{
        // 这里有个知识点, 既然y是后继节点, 则 y 必定没有两个子节点
        y = successor(z); // 节点z有两个子节点, 则调用 successor 查询z对应的子节点
    }

    // 2. 将待删除节点的子节点赋值给x
    if (y.left != null)
        x = y.left;
    else
        x = y.right;
    /**
     * x 情况
     * 1. x是被删除节点的子节点
     * 2. x是被删除节点的后继节点的子节点
     */
    if (x != null) {
        x.parent = y.parent;
    }

    // y.parent == null, 则说明y是mRoot节点
    if (y.parent == null)
        bst.mRoot = x;
    else if (y == y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;

    // 若y是z的后继节点
    if (y != z) {
        z.key = y.key;
    }

    return y;
}

6. 二叉查找树完整实现代码

二叉查找树Java实现 BSTree.java

总结

二叉查找树总体实现比较简单, 但这是学习 RBTree, B-Tree, B+Tree 等数据结构的基础