二叉排序树的原理与实现

1 二叉排序树简介

二叉排序树 (Binary Sort Tree),又称为二叉搜索树 (Binary Search Tree),它具有以下几个性质:

  1. 每个节点都有一个关键字 (key),可以用来比较节点之间的大小,并且各节点的关键字互不相同。
  2. 对于每个节点,如果它的左子树不为空,那么左子树上所有节点的关键字都小于它的根节点;如果它的右子树不为空,那么右子树上所有节点的关键字都大于它的根节点。
  3. 每个节点的左、右子树也都是二叉排序树。

二叉排序树可以通过二分法加速查询,平均时间复杂度为 $O(\log n)$ ~ $O(n)$。

2 二叉排序树的数据类型

首先,我们声明一个表示二叉排序树的数据类型 BinarySortTree<K extends Comparable<K>, V>,其中的泛型 KV 分别表示节点的键和值。

然后,我们在这个数据类型的内部声明一个数据节点类型 Node,该节点类型包含四个属性:key 表示节点的键,value 表示节点的值,leftright 分别表示节点的左子树和右子树。通过这个节点类型,我们可以表示二叉排序树中的节点。

 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
/**
 * 二叉排序树数据结构
 * @param <K> 节点 Key
 * @param <V> 节点 Value
 */
public class BinarySortTree<K extends Comparable<K>, V> {
    /**
     * 数据节点内部类
     */
    private class Node {
        private K key;
        private V value;
        private Node left, right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 根节点
     */
    private Node root;

    /**
     * 节点总数
     */
    private int count;
}
  • 为了声明关键字 K 的可比较性,我们让关键字 K 继承了 Comparable<T> 接口。

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
public void insert(K key, V value) {
    // 接收递归最外层返回的 root 节点
    root = insertNode(root, key, value);
}

private Node insertNode(Node node, K key, V value) {
    // 找到颗空位,创建新节点,并返回
    if (node == null) {
        ++count;
        return new Node(key, value);
    }
    int compare = key.compareTo(node.key);
    if (compare < 0) {
        // 如果新节点的 key 值小于当前节点,递归左子树
        node.left = insertNode(node.left, key, value);
    } else if (compare > 0) {
        // 如果新节点的 key 值大于当前节点,递归右子树
        node.right = insertNode(node.right, key, value);
    } else {
        // 如果新节点的 key 值与当前节点相等,更新节点的值
        node.value = value;
    }
    // 如果当前位置不为空,则返回本身
    return node;
}

4 二叉排序树查找操作

二叉排序树的查找操作包括 searchcontain 两个方法,这两个方法的查找过程相同,只是返回的数据类型不同。

我们先来看 search 方法,该方法递归地查找二叉排序树中是否存在指定的关键字 key。在每个节点中,比较当前节点的关键字与要查找的关键字 key 的大小,根据大小关系向左或向右递归查找,直到找到对应的节点或查找到了一个空节点:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public Node search(K key) {
    return searchNode(root, key);
}

private Node searchNode(Node node, K key) {
    if (node == null) {
        return null;
    }
    int compare = key.compareTo(node.key);
    if (compare == 0) {
        return node;
    } else if (compare < 0) {
        return searchNode(node.left, key);
    } else {
        return searchNode(node.right, key);
    }
}

contain 方法的实现与 search 方法基本相同,只是 contain 方法返回一个布尔值,用于表示二叉排序树中是否存在给定的关键字:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public boolean contain(K key) {
    return containNode(root, key);
}

private boolean containNode(Node node, K key) {
    if (node == null) {
        return false;
    }
    int compare = key.compareTo(node.key);
    if (compare == 0) {
        return true;
    } else if (compare < 0) {
        return containNode(node.left, key);
    } else {
        return containNode(node.right, key);
    }
}

5 二叉排序树删除操作

二叉排序树的删除过程是通过递归地比较节点的 key 大小,直到找到目标节点,然后将其删除。

  • 如果目标节点的 key 小于当前节点的 key,则递归删除当前节点的左子树中的节点;
  • 如果目标节点的 key 大于当前节点的 key,则递归删除当前节点右子树中的节点;
  • 如果目标节点的 key 等于当前节点的 key,则根据被删除的节点的子节点情况,进行不同的处理:
    • 如果要删除的节点没有左右子树,则可以直接删除该节点;
    • 如果要删除的节点只有左子树或右子树,则可以用它的左子树或右子树的根节点代替该节点。
    • 如果要删除的节点既有左子树又有右子树,则可以用其右子树中最小的节点代替该节点,然后删除其右子树中最小的节点。

实现如下:

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public void remove(K key) {
    root = deleteNode(root, key);
}

/**
 * 递归删除目标节点
 */
private Node deleteNode(Node node, K key) {
    if (node == null) {
        return null;
    }
    int compare = key.compareTo(node.key);
    if (compare < 0) {
        // key 小于当前节点,递归左子树
        node.left = deleteNode(node.left, key);
        return node;
    } else if (compare > 0) {
        // key 大于当前节点,递归右子树
        node.right = deleteNode(node.right, key);
        return node;
    } else {
        // 找到了目标节点,开始删除
        if (node.left == null && node.right == null) {
            // 如果左右子树都为空,直接删除节点即可
            --count;
            return null;
        } else if (node.left != null && node.right == null) {
            // 如果只有左子树,把左子树整个移交给前驱节点即可
            Node leftSubTreeRoot = node.left;
            node.left = null;
            --count;
            return leftSubTreeRoot;
        } else if (node.left == null) {
            // 如果只有右子树,把右子树整个移交给前驱节点即可
            Node rightSubTreeRoot = node.right;
            node.right = null;
            --count;
            return rightSubTreeRoot;
        } else {
            // 如果 node 左右子树都存在,那么需要合并两个子树
            // 根据性质,node 左子树所有节点,都小于其右子树中最小的节点,
            // 因此我们可以将右子树中最小的节点提升到删除节点的位置
            Node newNode = getMinNode(node.right);
            // 摘下右子树中最小节点,然后作为新节点的右子树
            newNode.right = removeMinNode(node.right);
            // 左子树不动,直接作为新节点的左子树
            newNode.left = node.left;
            node.left = node.right = null;
            return newNode;
        }
    }
}
  • getMinNode(Node node) 方法用于获取以 node 为根的子树中最小的节点,其实现是在左子树中递归查找最小节点。实现如下:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    
    /**
     * 获取以 node 为根的子树中,最小的节点
     */
    private Node getMinNode(Node node) {
        if (node.left == null) {
            return node;
        } else {
            return getMinNode(node.left);
        }
    }
  • removeMinNode(Node node) 方法用于删除以 node 为根的树中 key 最小的节点,其实现是在左子树中递归查找最小节点,并把它的右子树提升到该节点的位置。实现如下:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    
    /**
     * 删除以 node 为根的树中 key 最小的节点
     * @param node 树的根节点
     * @return 删除节点后的树的根节点
     */
    private Node removeMinNode(Node node) {
        if (node.left == null) {
            Node subRight = node.right;
            node.right = null;
            --count;
            return subRight;
        }
        node.left = removeMinNode(node.left);
        return node;
    }

当被删除节点的左右子树都存在时,我们可以还选择用其右子树中最小的节点或者其左子树中最大的节点来代替该节点。

6 二叉排序树遍历操作

二叉排序树的遍历操作也分为深度优先和广度优先两类,遍历方法与普通的二叉树完全一样,这里不再赘述。

7 二叉排序树的局限性

二叉排序树的主要局限性在于插入顺序会影响它的高度。例如,如果将有序序列插入到二叉排序树中,会得到一棵非常高的树,其高度接近于节点数量 $n$。这种情况会导致树的搜索效率变得非常低,甚至退化成链表,从而使时间复杂度退化为 $O(n)$,失去了二叉排序树的优势。

为了解决这个问题,人们发明了许多基于二叉排序树的改进算法,如 AVL 树红黑树 等。这些改进算法的目的是使树的高度始终保持在一个可控的范围内,从而保证二叉排序树的高效性。