文章首发于：clawhub.club

定义

SBT(Binary Sort Tree或者Binary Search Tree),二叉查找树，二叉排序树，是有一定性质的二叉树。
在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。
当它的高度为logN+1时，我们就说二叉查找树是平衡的。
BST.png

性质：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  • 左、右子树也分别为二叉查找树。

注意：

  • 从特性中可以看出是支持重复值的。如果有重复的值，会影响到查询效率，所以一般在插入的时候，如果碰到重复的值，直接过滤处理。
  • 当二叉查找树以中序遍历时，遍历的结果是一个从小到大排列的顺序。

节点定义

Java代码实现：

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
/**
 * 节点
 */
private class Node<V> {
    /**
     * 值
     */
    private V value;
    /**
     * 频率,如果value相同，则此值+1，去掉了重复的项
     */
    private int freq;
    /**
     * 父节点
     */
    private Node<V> parent;
    /**
     * 左节点
     */
    private Node<V> left;
    /**
     * 右节点
     */
    private Node<V> right;

}

查找

当BST查找的时候，先与当前节点进行比较：

  • 如果相等的话就返回当前节点；
  • 如果少于当前节点则继续查找当前节点的左节点；
  • 如果大于当前节点则继续查找当前节点的右节点。

直到当前节点指针为空或者查找到对应的节点
Java代码实现：

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
/**
 * Search .
 *
 * @param value the value
 * @return node
 */
public Node<V> search(V value) {
    //死循环
    while (true) {
        //如果根节点为null,返回null
        if (root == null) {
            return null;
        }
        //如果根节点的value与待查找value相同，返回根节点的值
        if (root.value.equals(value)) {
            return root;
        } else if (root.value.compareTo(value) < 0) {
            //如果待查找的value大于根节点的value,则继续查找根节点右边的节点
            root = root.right;
        } else {
            //如果待查找的value小于根节点的value，则查找根节点左边的节点
            root = root.left;
        }
    }

}

插入

  • 通过循环查找到待插入的节点的父节点，比大小，小的往左，大的往右。
  • 如果父节点为空，就此节点作为根节点。
  • 如果父节点不为空，对比父节点，小的就插入到父节点的左节点，大就插入到父节点的右节点上。
  • 重复节点的插入用值域中的freq标记

Java代码实现：

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
/**
 * Insert.
 *
 * @param current the current
 */
public void insert(Node<V> current) {
    //父节点
    Node<V> parent = null;

    //循环查找到待插入的节点的父节点
    while (true) {
        //如果根节点为null,跳出寻循环
        if (root == null) {
            break;
        }
        //指定父节点
        parent = root;

        //如果待插入的值 等于 根节点节点的值
        if (root.value.equals(current.value)) {
            //频率加1
            current.freq++;
            //程序结束
            return;

        } else if (root.value.compareTo(current.value) < 0) {
            //如果待插入的值 大于 根节点的值,则查找当前节点右边的节点
            root = root.right;
        } else {
            //如果待插入的值 小于 根节点的值,则查找当前节点左边的节点
            root = root.left;
        }
    }
    //找到待插入值的父节点
    if (null != parent) {
        //如果待插入的值 大于 父节点的值，则插入到父节点的右边
        if (parent.value.compareTo(current.value) < 0) {
            current.parent = parent;
            parent.right = current;
        } else {
            //如果待插入的值 小于 父节点的值，则插入到父节点的左边
            current.parent = parent;
            parent.left = current;
        }
    } else {
        //如果根节点为空，就此节点作为根节点
        root = current;
    }

}

删除

  • 查找到要删除的节点。
  • 没有左右子节点，可以直接删除
  • 存在左节点或者右节点，删除后需要对子节点移动
  • 同时存在左右子节点，不能简单的删除，但是可以通过和后继节点交换后转换为前两种情况
    Java代码实现：
    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
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    /**
         * Delete.
         *
         * @param value the value
         */
        public void delete(V value) {
            //找到要删除的节点
            Node<V> current = search(value);
            //如果未找到
            if (current == null) {
                return;
            }
            Node<V> parent = current.parent;
            //如果删除节点为根节点，直接删除
            if (parent == null) {
                //被删节点如果为根节点
                root = null;
            }

            //3-如果同时存在左右子节点
            if (current.left != null && current.right != null) {
                //获取中序遍历后的后继结点，以其右孩子为根的子树的最小结点
                Node<V> successor = minimum(current.right);
                //将后继结点值转移到到当前节点上
                current.value = successor.value;
                //把要删除的当前节点设置为后继结点
                current = successor;
            }

            //1-被删节点为叶子节点，直接删除
            if (current.left == null && current.right == null) {
                if (parent.left == current) {
                    //当前节点为父节点的左节点
                    parent.left = null;
                } else {
                    //当前节点为父节点的右节点
                    parent.right = null;
                }

                //2-被删除的节点只有一个子节点
            } else if (current.left == null || current.right == null) {
                Node<V> child;
                if (current.left != null) {
                    child = current.left;
                } else {
                    child = current.right;
                }

                if (parent.left == current) {
                    //当前节点的父节点的左节点指向当前节点的子节点
                    parent.left = child;
                } else {
                    //当前节点的父节点的右节点指向当前节点的子节点
                    parent.right = child;
                }
                //当前节点的子节点指向当前节点的父节点
                child.parent = parent;
            }

        }


        /**
         * 查找最小结点：返回node为根结点的二叉树的最小结点。
         *
         * @param node the node
         * @return the node
         */
        private Node<V> minimum(Node<V> node) {
            if (node == null) {
                return null;
            }
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

参考资料：
https://blog.csdn.net/isea533/article/details/80345507