二叉排序树（Binary Sort(Search) Tree）_binarysort

作者：不正经 | 2024-04-28 14:10:53

踩

binarysort

二叉排序树（Binary Sort(Search) Tree）

二叉排序树（Binary Sort Tree）又称二叉查找 / 搜索树（Binary Search Tree），也是树的一种特殊数据结构，这种树结构最大的特点就是查询效率高，很多情况下甚至比链表结构还要高。这种结构不仅查找高效，在动态插入、删除、修改等地方同样高效，因此这种结构在查找、插入算法、删除节点等地方被大量应用。

1、引子

现有一组数列[7, 3, 10, 12, 5, 1, 9]，要求能够高效的完成对数据的查询和添加。

解决方案分析：

1、使用数组实现

数组未排序时，直接在数组尾部添加，速度非常快，因为无需考虑顺序，缺点就是查找慢。
数组已排好序，对于排好序的数组我们可以使用二分法查找，查找速度可以非法快。但是也有缺点，为了保证数组有序在添加新数据时，找到插入位置后，后面的数据需要整体移动，导致效率很差。

2、使用链式存储即链表结构

不管链表是否有序，查找速度都慢，添加数据速度比数组快，因为不需要整体移动！

3、使用树存储方式

针对经常要查询和修改的数据，使用树结构存储最合适，这也是设计数据库采用树结构的原因。
树结构能提高数据存储和读取的效率，比如利用二叉排序树(Binary Sort Tree)，即可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。

关于二叉排序树(Binary Sort Tree)，是如何实现高效查找、插入、删除、修改的？？这也是本文探索与介绍的内容。

2、二叉排序树(BST)

2.1、基本介绍

二叉排序树：BST(Binary Sort(Search) Tree)，简称BST 。对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点。

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：
在这里插入图片描述

2.2、二叉排序树的创建和中序遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如：数组为 Array(7, 3, 10, 12, 5, 1, 9) ，创
建成对应的二叉排序树为：

package com.laizhenghua.tree;

/**
 * @description:
 * @author: laizhenghua
 * @date: 2021/11/9 20:11
 */
public class BinarySortTreeTest {
    public static void main(String[] args) {
        Integer[] array = new Integer[]{7, 3, 10, 12, 5, 1, 9};
        // 构建二叉排序树
        BinarySortTree binarySortTree = new BinarySortTree();
        for (Integer value : array) {
            binarySortTree.add(new Node(value));
        }
        // 中序遍历
        binarySortTree.infixOrder(); // 1 3 5 7 9 10 12
    }
}

// 创建二叉排序树
class BinarySortTree {
    private Node root; // 根节点

    // 添加节点方法
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            root.add(node);
        }
    }
    // 中序遍历
    public void infixOrder() {
        if (root.left != null) {
            root.infixOrder();
        } else {
            System.out.println("BinarySortTree is null");
        }
    }
}

// 创建Node节点
class Node {
    Integer value;
    Node left;
    Node right;

    public Node(Integer value) {
        this.value = value;
    }
    // 递归添加节点，需要满足二叉树排序树要求
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 和根节点比较value
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node); // 递归向左子树添加
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node); // 递归向右子树添加
            }
        }
    }
    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + "}";
    }
}
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
78
79
80
81
82
83
84
85
86
87

2.3、二叉排序树的删除

前面我们已经构建出了一颗二叉排序树，不难发现因为它的特殊排列规律，查找时相当于每次都是使用了二分法查找，所以查找效率比较高。那么二叉排序树的删除又是怎样的呢？

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑：
在这里插入图片描述
1、删除叶子节点 (比如：2, 5, 9, 12)

2、删除只有一颗子树的节点 (比如：1)

3、删除有两颗子树的节点. (比如：7, 3, 10)

对删除结点的各种情况的思路分析：

第一种情况：删除叶子节点 (比如：2, 5, 9, 12) 思路：

需求先去找到要删除的结点 targetNode
找到 targetNode 的父结点 parent
确定 targetNode 是 parent 的左子结点还是右子结点
根据前面的情况来对应删除 ①左子结点 parent.left = null ②右子结点 parent.right = null

第二种情况：删除只有一颗子树的节点（比如1）思路：

需求先去找到要删除的结点 targetNode
找到 targetNode 的父结点 parent
确定 targetNode 的子结点是左子结点还是右子结点
targetNode 是 parent 的左子结点还是右子结点
如果 targetNode 有左子结点
1. 如果 targetNode 是 parent 的左子结点parent.left = targetNode.left;
2. 如果 targetNode 是 parent 的右子结点parent.right = targetNode.left;
如果 targetNode 有右子结点
1. 如果 targetNode 是 parent 的左子结点parent.left = targetNode.right;
2. 如果 targetNode 是 parent 的右子结点parent.right = targetNode.right;

第三种情况：删除有两颗子树的节点(比如：7, 3, 10)思路：

需求先去找到要删除的结点 targetNode
找到 targetNode 的父结点 parent
从 targetNode 的右子树找到最小的结点
用一个临时变量，将最小结点的值保存 temp = 11
删除该最小结点
targetNode.value = temp

完整代码示例：

package com.laizhenghua.tree;

/**
 * @description:
 * @author: laizhenghua
 * @date: 2021/11/9 20:11
 */
public class BinarySortTreeTest {
    public static void main(String[] args) {
        Integer[] array = new Integer[]{7, 3, 10, 12, 5, 1, 9, 2};
        // 构建二叉排序树
        BinarySortTree binarySortTree = new BinarySortTree();
        for (Integer value : array) {
            binarySortTree.add(new Node(value));
        }
        binarySortTree.infixOrder(); // 1 2 3 5 7 9 10 12
        // 删除值为2的节点
        binarySortTree.deleteNode(2);
        System.out.println();
        // 中序遍历
        binarySortTree.infixOrder(); // 1 3 5 7 9 10 12

    }
}

// 创建二叉排序树
class BinarySortTree {
    private Node root; // 根节点

    // 添加节点方法
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            root.add(node);
        }
    }
    // 中序遍历
    public void infixOrder() {
        if (root.left != null) {
            root.infixOrder();
        } else {
            System.out.println("BinarySortTree is null");
        }
    }
    // 查找节点
    public Node searchNode(Integer value) {
        if (this.root == null) {
            System.out.println("BinarySortTree is null");
            return null;
        } else {
            return this.root.searchNode(value);
        }
    }
    // 查找父节点
    public Node searchParentNode(Integer value) {
        if (this.root == null) {
            System.out.println("BinarySortTree is null");
            return null;
        } else {
            return this.root.searchParentNode(value);
        }
    }
    // 删除节点
    public void deleteNode(Integer value) {
        if (root == null) {
            System.out.println("BinarySortTree is null");
        }
        Node targetNode = searchNode(value);
        if (targetNode == null) {
            System.out.printf("This node[value = %s] cannot be found", value);
        }
        // 如果我们发现当前这可二叉树排序树只有一个节点，并且还是要删除的节点
        if (root.left == null && root.right == null) {
            root = null;
            return;
        }
        Node parentNode = searchParentNode(value);
        // 情况1删除叶子节点
        if (targetNode.left == null && targetNode.right == null) {
            if (parentNode.left != null && parentNode.left.value == value) {
                // 删除父节点的左子节点
                parentNode.left = null;
            } else if (parentNode.right != null && parentNode.right.value == value) {
                // 删除父节点的右子节点
                parentNode.right = null;
            }
        } else if (targetNode.left != null && targetNode.right != null) {
            // 删除有两颗子树的节点
            Integer minValue = getAndDeleteRightTreeMin(targetNode.right);
            targetNode.value = minValue;
        } else {
            // 删除只有一颗子树的节点
            if (targetNode.left != null) {
                // 如果要删除的节点又左子节点
                if (parentNode.left.value == value) {
                    parentNode.left = targetNode.left;
                } else {
                    parentNode.right = targetNode.left;
                }
            } else {
                // 如果要删除的节点有右子节点
                if (parentNode.left.value == value) {
                    parentNode.left = targetNode.right;
                } else {
                    parentNode.right = targetNode.right;
                }
            }
        }
    }
    // 传入node节点（当做二叉排序树的根节点）删除并返回以node为根节点的二叉排序树的最小节点的值
    public Integer getAndDeleteRightTreeMin(Node node) {
        Node minValueNode = node;
        while (minValueNode.left != null) {
            minValueNode = minValueNode.left;
        }
        // 此时minValueNode就是以node为根节点的最小值
        deleteNode(minValueNode.value);
        return minValueNode.value;
    }
}

// 创建Node节点
class Node {
    Integer value;
    Node left;
    Node right;

    public Node(Integer value) {
        this.value = value;
    }
    // 递归添加节点，需要满足二叉树排序树要求
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 和根节点比较value
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node); // 递归向左子树添加
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node); // 递归向右子树添加
            }
        }
    }

    /**
     * 查找指定value的节点
     * @param value 查找节点的value
     * @return 如果找到则返回，找不到则返回null
     */
    public Node searchNode(Integer value) {
        if (this.value == value) {
            // 找到该节点
            return this;
        } else if (this.value > value) {
            // 向左递归查找
            if (this.left != null) {
                return this.left.searchNode(value);
            }
        } else if (this.value < value) {
            // 向右递归查找
            if (this.right != null) {
                return this.right.searchNode(value);
            }
        }
        return null;
    }

    /**
     * 查找指定值的父节点
     * @param value
     * @return 返回父节点，如果没有则返回null
     */
    public Node searchParentNode(Integer value) {
        if (this.right == null && this.left == null) {
            return null;
        }
        if (this.right != null && this.right.value == value) {
            return this;
        } else if (this.left != null && this.left.value == value) {
            return this;
        } else if (this.value > value) {
            // 向左递归查找
            if (this.left != null) {
                return this.left.searchParentNode(value);
            }
        } else if (this.value < value) {
            if (this.right != null) {
                return this.right.searchParentNode(value);
            }
        }
        return null;
    }
    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + "}";
    }
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216

3、BST删除注意点

前面我们已经完成了BST的构建、添加、查找、删除，看似已经万事大吉了。但是以上代码删除方法写的有漏洞！比如说二叉排序树长这样：
在这里插入图片描述
删除value=7的节点！此时就会报空指针异常。这是为啥？删除情况属于删除只有一颗子树的节点，不难发现当7为根节点时，已经没有父节点了。当去判断parentNode.left.value必定抛出空指针！所以我们还要对删除方法进行改造！

// 删除节点
public void deleteNode(Integer value) {
    if (root == null) {
        System.out.println("BinarySortTree is null");
    }
    Node targetNode = searchNode(value);
    if (targetNode == null) {
        System.out.printf("This node[value = %s] cannot be found", value);
    }
    // 如果我们发现当前这可二叉树排序树只有一个节点，并且还是要删除的节点
    if (root.left == null && root.right == null) {
        root = null;
        return;
    }
    Node parentNode = searchParentNode(value);
    // 情况1删除叶子节点
    if (targetNode.left == null && targetNode.right == null) {
        if (parentNode.left != null && parentNode.left.value == value) {
            // 删除父节点的左子节点
            parentNode.left = null;
        } else if (parentNode.right != null && parentNode.right.value == value) {
            // 删除父节点的右子节点
            parentNode.right = null;
        }
    } else if (targetNode.left != null && targetNode.right != null) {
        // 删除有两颗子树的节点
        Integer minValue = getAndDeleteRightTreeMin(targetNode.right);
        targetNode.value = minValue;
    } else {
        // 删除只有一颗子树的节点
        if (targetNode.left != null) {
            if (parentNode != null) {
                // 如果要删除的节点又左子节点
                if (parentNode.left.value == value) {
                    parentNode.left = targetNode.left;
                } else {
                    parentNode.right = targetNode.left;
                }
            } else {
                root = targetNode.left;
            }
        } else {
            if (parentNode != null) {
                // 如果要删除的节点有右子节点
                if (parentNode.left.value == value) {
                    parentNode.left = targetNode.right;
                } else {
                    parentNode.right = targetNode.right;
                }
            } else {
                root = targetNode.right;
            }
        }
    }
}
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

EDN

THANK YOU

END

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/502699