二叉搜索树及 Java 实现

定义

由一棵二叉树构成，满足：
$$
left.key<key<=right.key
$$
进一步有：
$$
key<=right.key<parent.key
$$
大部分二叉搜索树的最坏运行时间与树的高度成正比

1
2
3
4
5
// 成员变量(一般情况下)
Tree parent;
Tree left;
Tree right;
var key;

遍历方法

​ 1.中序遍历：

​ 通过递归方法，先找出左节点，再找出当前节点，最后是右节点。
​ 定理：若树节点为n，则调用该遍历方法需要O(n)的时间。

​ 2.先序遍历

​ 先当前节点，后左节点，最后右节点。

​ 3.后序遍历

​ 先左节点，后右节点，最后当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//中序遍历
public void inorder() {
    inorder(this);
}
private void inorder(Tree node) {
    if (node.left != null) inorder(node.left);
    System.out.println(node.key);
    if (node.right != null) inorder(node.right);
}

//先序遍历
public void preorder() {
    preorder(this);
}
private void preorder(Tree node) {
    System.out.println(node.key);
    if (node.left != null) preorder(node.left);
    if (node.right != null) preorder(node.right);
}

//后序遍历
public void postorder() {
    postorder(this);
}
private void postorder(Tree node) {
    System.out.println(node.key);
    if (node.left != null) postorder(node.left);
    if (node.right != null) postorder(node.right);
}

查找

给定一关键字key，返回第一个找到的含该关键字的树节点，没有则返回null。

运行时间为O(h)，h为树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//查找具体值对应的树（递归调用法）
public Tree search(int key) {
    if (key == this.key) return this;
    if (key < this.key) return left != null ? left.search(key) : null;
    return right != null ? right.search(key) : null;
}

//查找具体值对应的树（循环法）注意容易因混淆而产生幂等循环体，应设临时变量
public Tree iterativeSearch(int key) {
    Tree root = new Tree();
    root = this;
    while (root != null && root.key != key) {
        if (key < this.key) root = root.left != null ? root.left : null;
        else root = root.right != null ? root.right : null;
    }
    return root;
}

最大值和最小值：仅需查找左/右节点到头即可，运行时间为O(h)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//查找以node为根节点的最小值（递归调用法）
public Tree minimum(Tree node) {
    if (node.left == null) return node;
    else return minimum(node.left);
}

//查找以node为根节点的最小值（循环法）
public Tree iterativeMinimum(Tree node) {
    while (node.left != null) node = node.left;
    return node;
}

//查找以node为根节点的最大值（递归调用法）
public Tree maximum(Tree node) {
    if (node.right == null) return node;
    else return maximum(node.right);
}

//查找以node为根节点的最大值（循环法）
public Tree iterativeMaximum(Tree node) {
    while (node.right != null) node = node.right;
    return node;
}

后继和前驱：关键字key的最小大于值和最大小于值（key均不相等的情况下），运行时间为O(h)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//前驱
public Tree predecessor(Tree node) {
    if (node.left != null) return maximum(node.left);
    Tree node_p = node.parent;
    while (node_p != null && node == node_p.left) {
        node = node_p;
        node_p = node_p.parent;
    }
    return node_p;
}

//后继
public Tree successor(Tree node) {
    if (node.right != null) return maximum(node.right);
    Tree node_p = node.parent;
    while (node_p != null && node == node_p.right) {
        node = node_p;
        node_p = node_p.parent;
    }
    return node_p;
}

插入和删除

插入和删除会引发树结构的动态集合的变化。插入相对简单，但删除较为复杂。

插入：从根节点向下遍历到指定位置，实际上为新叶子节点的添加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//添加（插入）递归调用法
public void insert(int key) {
    if (key < this.key) {
        if (left == null) {
            left = new Tree();
            left.key = key;
            left.parent = this;
        } else left.insert(key);
    } else {
        if (right == null) {
            right = new Tree();
            right.key = key;
            right.parent = this;
        } else right.insert(key);
    }
}

//添加（插入）循环法
public void iterativeInsert(int key) {
    Tree parent = null;
    Tree x = this;
    while (x != null) {
        parent = x;
        if (key < x.key) x = x.left;
        else x = x.right;
    }
    if (key < parent.key) {
        parent.left = new Tree();
        parent.left.key = key;
        parent.left.parent = parent;
    } else {
        parent.right = new Tree();
        parent.right.key = key;
        parent.right.parent = parent;
    }
}

删除：有三种情况，有一种较为棘手，设该节点为z。

  1. z节点没有子节点，则仅将对应父节点连接的子节点位置修改为null；
  2. z节点有一个子节点，则将该子节点与父节点相连;
  3. z节点有两个子节点，则应寻找其后继y,将y代替z，z的子节点和父节点改接到y上，并将原y的父节点连接的子节点位置修改为null。该情况较为棘手，还涉及y是否为z右子节点的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//删除
public void delete(Tree node) {
    //如果左孩子为null，则提升右孩子，包含了二者皆为null的情况
    if (node.left == null) transPlant(node, node.right, false);
        //如果左孩子非null，右孩子为null，则提升左孩子
    else if (node.right == null) transPlant(node, node.left, true);
        //如果二者非空,则寻找node的后继
    else {
        Tree next = successor(node);
        //若next不是node的右孩子，则先将next的右孩子提升，再替换node
        if (next != node.right) {
            transPlant(next, next.right, false);
            next.right = node.right;
        }
        //若是，则直接替换
        transPlant(node, next, false);
    }
}

private void transPlant(Tree node, Tree next, boolean isLeft) {
    if (isLeft) next.right = node.right;
    else next.left = node.left;
    if (node == node.parent.left) node.parent.left = next;
    else node.parent.right = next;
}