二叉查找树(1)-二叉树-数据结构和算法(Java)

1 前言

树是一种数据结构，树的相关基础知识的和体系介绍可以查看百度百科关于树的介绍或者文章最后的文献索引，这里不再详述。

我们会陆续讲解二叉查找树，2-3查找树，红黑树，B树，B+树和B*树。

1.1 二叉查找树定义

二叉查找树(Binary Search Tree)，简称BST（又称二叉搜索树），是二叉树的一种，其中每个节点的值大于左子树的值（如果左子树存在）而小于右子树的值（如果右子树存在)。

1.2 二叉查找树的性质

若左子树不为空，则左子树节点的值小于其根节点的值。
若右子树不为空，则右子树节点的值大于其根节点的值。
左右子树均为二叉查找树。
所有节点的键值不重复。

2 基本实现

相对更简单的理解和实现使用递归方式，但是如果数据量大的话递归方式就不适用了，所有呢这里实现不采用递归方式。如果想要了解递归实现的话，可以查看文章末尾算法第4版或者视频。

2.1 API

API同之前有序符号表的API一致，可以查看之前的文章基础-符号表(一)-数据结构和算法(Java)

2.2 实现代码

2.2.1 数据表示

树节点代码如下：

/**
     * 内部节点类
     * @param 
     * @param 
     */
    static class Node<K, V> {
        /**
         * 键
         */
        K key;

        /**
         * 值
         */
        V value;

        /**
         * 左子树
         */
        Node<K, V> left;

        /**
         * 右子树
         */
        Node<K, V> right;

        /**
         * 该节点为根的树中节点总数
         */
        int size;

        Node(K key, V value, Node<K, V> left, Node<K, V> right, int size) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.size = 1;
        }

        Node(K key, V value) {
            this(key, value, null, null, 1);
        }
    }
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

2.2.2 查找

查找一个键有两种结果，如果包含键的节点存在与表中，我们的查找就命中，返回相应的值。否则未命中，返回null。

如果表为空，直接返回null
根节点root赋值给当前节点变量cur,只要当前节点不为null，循环执行一下操作
- 比较当前节点的键和目标键key的大小
- 如果目标键小于当前节点的键，说明目标节点在当前节点的左子树中，把当前节点的左子节点cur.left赋值给cur,即当前节点的左子节点变为了下次循环的当前节点
- 如果目标键大于当前节点的键，说明目标节点在当前节点的右子树中，把当前节点的右子节点cur.right赋值给cur,即当前节点的右子节点变为了下次循环的当前节点
- 如果目标键等于当前节点的键，说明命中目标节点，直接返回当前节点的值。
如果循环结束即查找到某个空节点，仍然为命中目标，说明该键不在表中，返回null。

代码2.2.2-1如下：

/**
 * 获取key对应的值
 * @param key   键
 * @return  指定键对应的值
 */
@Override
public V get(K key) {
    return get(root ,key);
}

/**
 * 从根结点开始查找键对应的值
 * @param root  根结点
 * @param key   指定的键
 * @return      键对应的值
 */
private V get(Node<K,V> root, K key) {
    if (size == 0) {
        return null;
    }
    Node<K, V>  cur = root;
    while (cur != null) {
        if (key.compareTo(cur.key) < 0) {
            cur = cur.left;
        } else if (key.compareTo(cur.key) > 0) {
            cur = cur.right;
        } else {
            return cur.value;
        }
    }
    return null;
}
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

2.2.3 插入

实现代码2.2.3-1如下：

/**
     * 插入键值对，如果key存在则替换旧值；如果不存在，在合适位置插入新的键值对
     * @param key       键
     * @param value     值
     */
@Override
public void put(K key, V value) {

    // 判断表是否为空
    if (root == null) {
        root = new Node<>(key, value);
        return;
    }
    // 父节点
    Node<K, V> f = null;
    // 当前节点
    Node<K, V> cur = root;
    // 新插入节点是否为左节点：true-左节点，false-右节点
    boolean left = true;
    // 查找key是否在表中
    while (cur != null) {
        cur.size++;
        if (key.compareTo(cur.key) < 0) {
            // 给定的键小于当前节点的键，继续在左子树查找
            f = cur;
            cur = cur.left;
            left = true;
        } else if (key.compareTo(cur.key) > 0) {
            // 给定的键大于当前节点的键,继续在右子树查找
            f = cur;
            cur = cur.right;
            left = false;
        } else {
            // 给定的键等于当前节点的键,新值替换旧值
            cur.value = value;
            return;
        }
    }
    // key不在表中，插入新节点
    Node<K, V> newNode = new Node<>(key, value);
    if (left) {
        f.left = newNode;
    } else {
        f.right = newNode;
    }
}

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

算法分析：代码给的注释如果明了可跳过以下解释

判断表是否为空
- 为空，新建节点，且指定为根节点，return。
- 不为空，先查找给的键是否在表中
  - 设置3个变量
    - f：当前节点的父节点，初始值null
    - cur：当前节点，初始值root根节点
    - left：当前节点是否是父节点的左子节点，初始值true
  - 循环以下操作：循环条件当前节点不为空，表示键有可能在表中
    - 路径上每个节点的计数+1
    - 判断key小于当前节点的键，则继续在当前节点的左子树中查找
      - 当前节点变为下次循环的父节点
      - 当前节点的左节点变为下次循环的当前节点
      - left设置为true表示当前节点是父节点的左子节点
    - 判断key大于当前节点的键，则继续在当前节点的右子树中查找
      - 当前节点变为下次循环的父节点
      - 当前节点的右节点变为下次循环的当前节点
      - left设置为false表示当前节点是父节点的右子节点
    - 否则key等于当前节点的键，命中目标，直接新值替换旧值，return。
  - 循环结束未命中目标,说明key不在表中，需要插入新的节点，插入位置就是cur，父节点就是f
  - 新建节点
  - 判断left
    - true，把新节点设置为父节点的左子节点
    - false，把新节点设置为父节点的右子节点。

执行流程图2.2.3-1如下所示：在这里插入图片描述

命中节点，未命中，插入为左子树，未命中，插入为右子树如下2.2.3-2所示：

在这里插入图片描述

3 分析

使用二叉查找树的算法的运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。在最好的情况下，一棵含义N个节点的树是完全平衡的，叶子结点和根节点的距离都为 $\sim\lg N$ 。在最坏情况下，搜索路径上可能有N个节点。

我们假设键的分布是（均匀）随机的，或者说它们的插入顺序是随机的。二叉查找树和快速排序几乎一样，树的根节点就是快速排序中的第一个切分元素（左侧的键都比它小，右侧的键都比它大），而这对于所有的子树同样适用。

命题C：在由N个随机键构造的二者查找树中，查找命中平均所需的比较次数为 $\sim\ln N(约为1.39\lg N)$

证明：暂时不证明，因为本人没研究明白呢😢

4 有序性相关方法与删除操作

二叉查找树得以广泛应用的一个重要的原因就是它能够保持键的有序性，因此它可以做为实现有序符号表API中的众多方法的基础。这使得符号表的用例不仅能够通过键还能同键的相对顺序来访问键值对。

4.1 最大键和最小键

查找最小键算法
- 如果根节点为空，直接返回null;
- 根节点设置为当前节点，循环判断当前节点是否为空
  - 不为空，极限查找当前节点的左子树
  - 为空那么当前节点的父节点就是最小键节点。
查找最大键算法
- 如果根节点为空，直接返回null;
- 根节点设置为当前节点，循环判断当前节点是否为空
  - 不为空，极限查找当前节点的→子树
  - 为空那么当前节点的父节点就是最大键节点。

非递归实现代码如下4.1-1所示：

/**
* 获取最小键
* @return  最小键
*/
@Override
public K min() {
    if (isEmpty()) {
        return null;
    }
    Node<K, V> f = null;
    Node<K, V> cur = root;
    while (cur != null) {
        f = cur;
        cur = cur.left;
    }
    return f.key;
}

/**
* 获取最大键
* @return  最大键
*/
@Override
public K max() {
    if (isEmpty()) {
    	return null;
    }
    Node<K, V> f = null;
    Node<K, V> cur = root;
    while (cur != null) {
        f = cur;
        cur = cur.right;
    }
    return f.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

4.2 向上取整和向下取整

如果目标键在树中，向上取整和向下取整都是目标键本身；否则，向下取整就是取小于给定值的键的最大键，即寻找目标节点的前驱节点。向上取整就是取大于给定键的最小键，即寻找目标节点的后继节点。

关于前驱和后继节点不了解的自己去搜索一下。

4.2.1 向下取整floor()

算法：

如果根节点root为空，直接返回null
否则root赋值给当前节点,prev为前驱节点默认null;
循环判断当前节点不为空
- 如果给定key小于当前节点的key，继续查找当前节点的左子树
- 如果给定key大于当前节点的key，cur赋值给prev，继续查找右子树
- 如果给定key等于当前节点的key直接返回当前节点的key
判断prev是否为空
- 为空，返回null
- 不为空，返回prev.key

逻辑就是如果目标key小于当前节点的key，那么小于等于key最大键一定（如果有）出现在当前节点的左子树；

如果目标key大于当前节点的key，那么只有当前节点右子树中有小于等于目标key的节点存在时，小于等于目标key的最大键才会出现在当前节点的右子树中，否则当前节点就是小于等于目标key的最大键。

代码4.2.1如下：

/**
 * 向下取整，获取小于给定键的最大键
 * @param key   目标键
 * @return  小于给定键的最大键
 */
@Override
public K floor(K key) {
    if (isEmpty()) {
        return null;
    }
    Node<K, V>  cur = root;
    Node<K, V> prev = null;
    while (cur != null) {
        if (key.compareTo(cur.key) < 0) {
            cur = cur.left;
        } else if (key.compareTo(cur.key) > 0) {
            prev = cur;
            cur = cur.right;
        } else {
            return cur.key;
        }
    }
    return prev == null ? null: prev.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

4.2.2 向上取整ceiling()

直接给代码，可对比向下取整，代码。4.2.2-1如下：

/**
 * 向上取整，获取大于给定键的最小值
 * @param key   目标键
 * @return  大于给定键的最小值
 */
@Override
public K ceiling(K key) {
    if (isEmpty()) {
        return null;
    }
    Node<K, V>  cur = root;
    Node<K, V> next = null;
    while (cur != null) {
        if (key.compareTo(cur.key) < 0) {
            next = cur;
            cur = cur.left;
        } else if (key.compareTo(cur.key) > 0) {
            cur = cur.right;
        } else {
            return cur.key;
        }
    }
    return next == null ? null: next.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

4.3 选择select()

代码4.3.1如下：

/**
 * 返回排序为k的键
 * @param k 排名
 * @return 排序为k的键
 */
@Override
public K select(int k) {
    if (isEmpty()) {
        return null;
    }
    int i = k;
    Node  cur = root;
    while (cur != null) {
        int l     /**
     * 返回排序为k的键
     * @param k 排名
     * @return 排序为k的键
     */
    @Override
    public K select(int k) {
        if (isEmpty()) {
            return null;
        }
        int n = k;
        Node  cur = root;
        while (cur != null) {
            int nl = cur.left == null ? 0: cur.left.size;
            if (nl  > n) {
                cur = cur.left;
            } else if (nl < n) {
                n = n - nl - 1;
                cur = cur.right;
            } else {
                return cur.key;
            }
        }
        return null;
    }= cur.left == null ? 0: cur.left.size;
        if (l  > i) {
            cur = cur.left;
        } else if (l < i) {
            i = i - l - 1;
            cur = cur.right;
        } else {
            return cur.key;
        }
    }
    return null;
}
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

排序为k，因为键有序，就是我们说的索引，返回索引为k的节点对应的键，算法如下：

如果树为空，直接返回null
根节点置为当前节点,目标索引赋值为n
循环判断当前节点不为空
- 取当前节点左子节点的size赋值为nl,nl表示当前节点的索引值
  - 每个节点左子树节点上的size就代表当前节点在以当前节点为根的树的索引
- 把当前节点索引值和目标索引比较
  - 如果当前节点索引大于目标索引n，那么继续在左子树中查找目标索引
  - 如果当前节点索引大于目标索引n，那么我们在右子树中查找索引为n=n-nl-1
    - 在右子树中查找，即相当于在以右子节点为根的新的树中查找，索引需要减去当前节点索引+1
  - 如果当前节点索引等于n，命中目标节点，返回当前节点的键
循环结束，索引超出范围，返回null

4.4 排名rank()

代码如下：

/**
 * 小于key的键的数量
 * @param key    目标key
 * @return  小于key的键的数量
 */
@Override
public int rank(K key) {
    if (isEmpty()) {
        return 0;
    }
    Node<K, V>  cur = root;
    int n = 0;
    while (cur != null) {
        if (key.compareTo(cur.key) < 0) {
            cur = cur.left;
        } else if (key.compareTo(cur.key) > 0) {
            n += 1 + (cur.left == null ?  0: cur.left.size);
            cur = cur.right;
        } else {
            break;
        }
    }
    return n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

算法如下：

如果树为空，直接返回0。
root赋值给当前节点cur,初始计数n=0。
循环判断当前节点不为空
- 如果key小于当前节点的key，继续在当前节点的左子树中查找
- 如果key大于当前节点key，计数需要加上当前节点1+当前节点左子树中节点个数
  - 如果当前节点左子树为空+0
- 如果命中目标，break结束循环
返回n

4.5 删除最大键和最小键

以删除最小键为例，算法逻辑

从根结点开始循环查找左子节点，直到左子节点为空，路径上节点size–
为空的左子节点的父节点即是要删除的目标节点
如果目标节点的父节点有右子节点，直接把父节点左连接指向该节点
没有直接情况目标节点断开连接