1、概要

这里主要讲解二叉搜索树的设计及实现。
代码地址: github地址
https://github.com/fofcn/operation-system/blob/main/%E5%AE%9E%E8%B7%B5/os/src/main/java/lang/tree/BinarySearchTree.java

2、概念

二叉搜索树是用一颗二叉树来组织的，这棵树可以使用一个链表来表示，每个节点都是一个对象。

2.1、节点

每个节点都有一个父节点、左孩子和右孩子。

2.2、性质

假设x是二叉搜索树的一个节点。
如果y是x的左子树的一个节点，那么y.key<=x.key。
如果y是x的右子树的一个节点，那么y.key>=x.key。

3、操作

搜索树支持很多动态集合操作，包括SEARCH、MINIMUM、MAXIMUM、FLOOL、CELL、INSERT和DELETE等。我们主要讲解查找、插入和删除三类主要的操作。

3.1、插入

二叉搜索树的插入相对比较简单，需要在二叉搜索树上查找插入的位置，然后新建接节点插入，然后修改该节点的父级节点属性。
例如：将 10 16 4 1 12 2 0 11 18 6 分别插入到二叉搜索树中，会得到如下图所示的二叉搜索树

Java实现代码如下：

private void putInternal(Key key, Value value) {
        // 初始化二叉搜索树
        if (root == null) {
            root = new Node(key, value);
            size.incrementAndGet();
        } else {
            // 从根节点开始查找插入位置
            Node tmp = root;
            while (tmp != null) {
                int cmp = key.compareTo(tmp.key);
                // 如果待插入节点比当前节点小，那么查看该节点的左孩子是否为空，如果为空，则将待插入节点插入到左孩子
                if (cmp < 0) {
                    if (tmp.left == null) {
                        tmp.left = new Node(key, value);
                        tmp.left.parent = tmp;
                        size.incrementAndGet();
                        break;
                    }
                    tmp = tmp.left;
                    // 如果待插入节点比当前节点小，那么查看该节点的右孩子是否为空，如果为空，则将待插入节点插入到右孩子
                } else if (cmp > 0) {
                    if (tmp.right == null) {
                        tmp.right = new Node(key, value);
                        tmp.right.parent = tmp;
                        size.incrementAndGet();
                        break;
                    }
                    tmp = tmp.right;
                } else {
                    tmp.value = value;
                    break;
                }
            }
        }
    }

3.2、查找

在一颗二叉搜索树中查找一个指定关键字。
在二叉搜索树中查找一个指定关键字从树根开始查找，并沿着这棵树的一条路径向下进行查找。
例如：如果在上图中的二叉搜索树中查找节点为6的节点，那么搜索路径为10->4-6

Java实现代码如下：

/**
     * 根据key查找Key对应的节点
     * @param key 关键字
     * @return key对应的关键字，null没有找到关键字对应的节点
     */
    private Node getInternal(Key key) {
        Node tmp = root;
        int cmp;
        // 遍历树查找节点
        while (tmp != null && (cmp = key.compareTo(tmp.key)) != 0) {
            if (cmp < 0 ) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }

        return tmp;
    }

3.3、删除

二叉搜索树的删除稍微有点复杂，根据二叉搜索树的特性，删除基本分为三种情况：
假设待删除节点为x：

1. 如果x没有孩子节点，那么修改该孩子的父节点为null

如下图所示：将6节点删除时直接删除并更新节点4的右孩子为null

1. 如果x只有一个孩子节点，那么将这个孩子提升到x位置，并修改x的父节点对应的左右孩子为这个孩子节点

如下图：将12节点的值删除时，需要将16节点的左孩子更新为11,11节点的父节点更新为16

删除后如下图所示

1. 如果x有两个孩子节点，那么就需要在x的右子树中查找x的后继节点y，并将y提升到节点x的位置，并将x的左子树成为y的左子树，将替换y的右子树为x的右子树

如下图所示：如果删除4节点，则需要从4节点的右孩子中查找右孩子中最小的节点为5，将5提升到节点4的位置，更新5的父节点为10，更新5的左孩子为1，更新6的左孩子为null

删除后如下图所示：

Java代码实现如下：

public void delete(Key key) {
        if (key == null) {
            throw new IllegalArgumentException();
        }

        Node tmp = root;
        while (tmp != null) {
            int cmp = key.compareTo(tmp.key);
            if (cmp < 0) {
                tmp = tmp.left;
            } else if (cmp > 0) {
                tmp = tmp.right;
            } else {
                // 找到了待删除的节点
                // 情况1：如果该节点既没有左孩子也没有右孩子，那么就直接删除
                // 情况2：如果该节点只有一个孩子那么直接将该孩子提升到该孩子的位置上
                // 情况3：如果该节点既有左孩子又有右孩子,则查找待删除节点的右孩子中最小的孩子，并将最小的孩子提升到待删除节点的位置

                // 左孩子为空，那么用右孩子替换为tmp
                if (tmp.left == null) {
                    transplant(tmp, tmp.right);
                } else if (tmp.right == null) {
                    // 右孩子为空，那么用左孩子替换掉tmp
                    transplant(tmp, tmp.left);
                } else {
                    // 左右孩子都不为空
                    // 查找右孩子中最小的节点
                    Node min = min(tmp.right);
                    // 右孩子中最小节点的父级节点不是tmp表示最小节点不是tmp的直接孩子
                    // 那么这种情况下，需要将最小节点的右孩子替换最小节点的位置
                    // 将最小节点的右孩子设置为tmp右孩子
                    // 将最小节点的右孩子的父设置为最小节点
                    if (min.parent != tmp) {
                        transplant(min, min.right);
                        min.right = tmp.right;
                        min.right.parent = min;
                    }

                    // 用tmp右子树最小节点替换掉tmp
                    // 最小节点的左孩子更新为tmp的左孩子
                    // 最小节点的左孩子的父节点更新为最小节点
                    transplant(tmp, min);
                    min.left = tmp.left;
                    min.left.parent = min;
                }
                tmp = null;
                break;
            }
        }
    }

private void transplant(Node del, Node child) {
        // 更新待删除节点的父节点
        if (del.parent == null) {
            root = child;
        } else if (del == del.parent.left) {
            del.parent.left = child;
        } else {
            del.parent.right = child;
        }

        // 更新孩子节点的父节点为待删除节点的父节点
        if (child != null) {
            child.parent = del.parent;
        }
    }

4 算法运行时间

假设一颗二叉搜索树的高度为h

最好情况分析

最好情况就是二叉搜索树完全平衡，即二叉搜索树中的每个节点都有左右两个孩子，此时树的高度O(logn),如下图所示：

最坏情况分析

最坏情况是所有节点都是按照正序插入，那么此时树的高度是n,插入、查找和删除的时间是O(n)，如下图所示

平均情况分析

5、总结

1. 二叉搜索树保证在O(n)的时间内完成插入、查找和删除
2. 二叉搜索树平均插入和查找的时间为1.39logn
3. 二叉搜索树平均情况运行时间依然是很快

6、参考

1. 算法导论 二叉搜索树