二叉排序树BST
1. 问题描述
- 数组（顺序存储）：
- 未排序：
- 优点：直接在数组末尾添加元素，速度较快；
- 缺点：查找速度慢；
- 已排序：
- 优点：可以使用二分查找等查找算法，查找速度较快；
- 缺点：为了保证数组是有序的，添加新数据时，找到插入位置后，后面的数据需要整体移动，速度较慢；
- 未排序：
- 链表（链式存储）：
- 无论链表上的节点是否有序，查找速度都较慢；但添加数据的速度要比顺序存储快，因为不需要数据进行整体后移；
- 解决方案：二叉排序树BST，添加数据和查找数据都较快。
2. BST介绍
二叉排序树（Binary Sort Tree，BST），对于BST的任何一个非叶子节点，要求其左子节点的值比当前节点的值小，且右子节点的值比当前节点的值大。
特别说明：若有相同的值，则可以将该节点放在左子节点或右子节点。
eg. 针对数列{7，3，10，12，5，1，9}，其对应的BST如下图所示：
3. BST创建与遍历代码实现
package com.datastructure;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author SnkrGao
* @create 2023-05-18 10:33
*/
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7,3,10,12,5,1,9};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(binarySortTree.getRoot(), new BSTNode(arr[i]));
}
System.out.println("中序遍历：");
List<Integer> resList = binarySortTree.inorderTraversal(binarySortTree.getRoot());
System.out.println(resList);
}
}
class BinarySortTree {
private BSTNode root;
public BSTNode getRoot() {
return root;
}
public void setRoot(BSTNode root) {
this.root = root;
}
/**
* 以递归的方式往BST中添加节点（创建BST）
* @param root 当前节点，从根节点root开始
* @param node 传入要添加的节点
*/
public void add(BSTNode root, BSTNode node) {
// 如果整个BST的根节点为空，则直接让root指向node
if (this.getRoot() == null) {
// 即创建树时通过setRoot使得root节点与BST建立关系，否则整个BST为空
this.setRoot(node);
return;
}
// 判断传入节点的value与当节点的value的关系
if (node.getValue() < root.getValue()) {
// 若当前节点的左子节点为空
if (root.getLeft() == null) {
root.setLeft(node);
} else {
// 递归向左子树添加
add(root.getLeft(), node);
}
} else {
if (root.getRight() == null) {
root.setRight(node);
} else {
// 递归向右子树添加
add(root.getRight(), node);
}
}
}
// 非递归方法进行中序遍历
public List<Integer> inorderTraversal(BSTNode root) {
if (root == null) {
System.out.println("二叉排序树为空，无法遍历！");
}
List<Integer> resList = new ArrayList<>();
Deque<BSTNode> stack = new ArrayDeque<>();
BSTNode curNode = root;
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
stack.push(curNode);
curNode = curNode.getLeft();
}
if (!stack.isEmpty()) {
BSTNode temp = stack.pop();
resList.add(temp.getValue());
curNode = temp.getRight();
}
}
return resList;
}
}
class BSTNode {
private int value;
private BSTNode left;
private BSTNode right;
public BSTNode(int value) {
this.value = value;
}
@Override
public String toString() {
return "BSTNode{" +
"value=" + value +
'}';
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public BSTNode getLeft() {
return left;
}
public void setLeft(BSTNode left) {
this.left = left;
}
public BSTNode getRight() {
return right;
}
public void setRight(BSTNode right) {
this.right = right;
}
}
4. BST删除节点思路
-
首先通过search方法找到要删除的节点targetNode
- 若没有找到要删除的节点，则直接return。即判断是否有targetNode == null
- 若targetNode != null且该BST只有root节点（root.getLeft == null && root.getRight == null），即说明root节点就是要删除的节点，则直接将root置空并返回（待删除的节点为root节点，且root为叶子节点的情况）
-
通过searchParent方法找到要删除节点的父节点parent
-
之后需要分三种情况分别进行处理：
-
(一). 要删除的节点为叶子节点（targetNode.getLeft == null && targetNode.getRight == null）
-
注：此时不需要判断parent是否为空，该情况下parent为空的情况在前面已经处理过（即BST只有一个root节点）
-
若targetNode为parent的左子节点：则parent.setleft = null
-
若targetNode为parent的右子节点：则parent.setRight = null
-
-
(二). 要删除的节点有两棵子树（targetNode.getLeft != null && targetNode.getRight != null）
- 注：此时也不需要判断parent是否为空，因为该情况下不需要判断targetNode与parent节点之间的关系
- 两种处理方式：（1）从targetNode的右子树中找到最小的节点（2）从targetNode的左子树中找到最大的节点
- 用临时变量temp保存上一步中找到的节点的值
- 删除上一步中找到的右子树最小节点/左子树最大节点（仍然保持BST的特性）
- 将保存的值替换给待删除的节点，即targetNode.setValue = temp
-
(三). 要删除的节点只有一棵子树，分以下两种情况讨论：
- 若targetNode有左子节点，即targetNode.getLeft != null
- 首先判断parent是否为空（即待删除节点是否为root节点）
- 若parent == null，则直接令root = targetNode.getLeft
- 若不为空，再分以下两种情况：
- （1）targetNode是parent的左子节点，则令parent.setLeft = targetNode.getLeft
- （2）targetNode是parent的右子节点，则令parent.setRight = targetNode.getLeft
- 若targetNode有右子节点，即targetNode.getRight != null
- 同样首先判断parent是否为空（即待删除节点是否为root节点）
- 若parent == null，则直接令root = targetNode.getRIght
- 若不为空，再分以下两种情况：
- （1）targetNode是parent的左子节点，则令parent.setLeft = targetNode.getRight
- （2）targetNode是parent的右子节点，则令parent.setRight = targetNode.getRight
- 若targetNode有左子节点，即targetNode.getLeft != null
-
5. 完整代码实现
package com.datastructure;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
* @author SnkrGao
* @create 2023-05-18 10:33
*/
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(binarySortTree.getRoot(), new BSTNode(arr[i]));
}
System.out.println("中序遍历：");
List<Integer> resList = binarySortTree.inorderTraversal(binarySortTree.getRoot());
System.out.println(resList);
// 测试search方法和searchParent方法
System.out.println(binarySortTree.search(binarySortTree.getRoot(), 4));
System.out.println(binarySortTree.searchParent(binarySortTree.getRoot(), 3));
binarySortTree.delNode(7);
binarySortTree.delNode(3);
binarySortTree.delNode(9);
binarySortTree.delNode(5);
binarySortTree.delNode(10);
binarySortTree.delNode(12);
binarySortTree.delNode(2);
System.out.println("删除节点后中序遍历：");
resList = binarySortTree.inorderTraversal(binarySortTree.getRoot());
System.out.println(resList);
}
}
class BinarySortTree {
private BSTNode root;
public BSTNode getRoot() {
return root;
}
public void setRoot(BSTNode root) {
this.root = root;
}
/**
* 以递归的方式往BST中添加节点
*
* @param root 当前节点，从根节点root开始
* @param node 传入要添加的节点
*/
public void add(BSTNode root, BSTNode node) {
// 如果整个BST的根节点为空，则直接让root指向node
if (this.getRoot() == null) {
// 创建BST二叉排序树，将node作为root节点放入树中，否则整个BST为空
this.setRoot(node);
return;
}
// 判断传入节点的value与当节点的value的关系
if (node.getValue() < root.getValue()) {
// 若当前节点的左子节点为空
if (root.getLeft() == null) {
root.setLeft(node);
} else {
// 递归向左子树添加
add(root.getLeft(), node);
}
} else {
if (root.getRight() == null) {
root.setRight(node);
} else {
// 递归向右子树添加
add(root.getRight(), node);
}
}
}
// 非递归方法进行中序遍历
public List<Integer> inorderTraversal(BSTNode root) {
if (root == null) {
System.out.println("二叉排序树为空，无法遍历！");
}
List<Integer> resList = new ArrayList<>();
Deque<BSTNode> stack = new ArrayDeque<>();
BSTNode curNode = root;
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
stack.push(curNode);
curNode = curNode.getLeft();
}
if (!stack.isEmpty()) {
BSTNode temp = stack.pop();
resList.add(temp.getValue());
curNode = temp.getRight();
}
}
return resList;
}
// 查找待删除结点
public BSTNode search(BSTNode root, int value) {
if (root == null) {
return null;
}
if (value == root.getValue()) {
return root;
} else if (value < root.getValue()) {
// 向左子树递归查找
return search(root.getLeft(), value);
} else {
return search(root.getRight(), value);
}
}
// 查找待删除节点的父节点
public BSTNode searchParent(BSTNode root, int value) {
if (root == null) {
return null;
}
// 若当前节点就是待删除节点的父节点
if ((root.getLeft() != null && root.getLeft().getValue() == value) || (root.getRight() != null && root.getRight().getValue() == value)) {
return root;
} else {
// 若查找值 < 当前节点的值，且当前节点有左子节点
if (value < root.getValue() && root.getLeft() != null) {
// 向左递归查找
return searchParent(root.getLeft(), value);
} else if (value >= root.getValue() && root.getRight() != null) {
return searchParent(root.getRight(), value);
} else {
// 没有找到父节点，ie. root节点为待删除节点时其父节点为null
return null;
}
}
}
/**
* 查找并删除待删除节点的右子树中的最小值
* @param node 传入待删除节点的右子树的根节点
* @return 返回该最小值
*/
public int delRightTreeMin(BSTNode node) {
// 找BST子树中的最小值，一直向左子树查找即可
while (node.getLeft() != null) {
node = node.getLeft();
}
// 调用delNode方法删除该最小值节点
delNode(node.getValue());
return node.getValue();
}
public void delNode(int value) {
if (this.root == null) {
System.out.println("二叉排序树为空，无法删除！");
return;
}
// 先找到待删除节点
BSTNode targetNode = search(this.root, value);
// 若没有找到待删除节点
if (targetNode == null) return;
// 若找到了待删除节点，但该节点是BST的root节点且树中只有该节点
if (this.root.getLeft() == null && this.root.getRight() == null) {
this.root = null;
return;
}
// 找到targetNode的父节点
BSTNode parent = searchParent(this.root, value);
// 第一种情况：targetNode是叶子节点
if (targetNode.getLeft() == null && targetNode.getRight() == null) {
// targetNode是parent的左子节点
if (parent.getLeft() == targetNode) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
// 第二种情况：targetNode有两个子节点
} else if (targetNode.getLeft() != null && targetNode.getRight() != null) {
// 临时变量保存右子树的最小值，并删除该最小值节点
int minValueOfRightTree = delRightTreeMin(targetNode.getRight());
// 替换掉targetNode的值
targetNode.setValue(minValueOfRightTree);
// 第三种情况：targetNode只有一个子节点
} else {
// 若targetNode有左子节点
if (targetNode.getLeft() != null) {
// 判断parent是否为空，即targetNode是否是root节点
if (parent == null) {
this.root = targetNode.getLeft();
} else {
// targetNode是parent的左子节点
if (parent.getLeft() == targetNode) {
parent.setLeft(targetNode.getLeft());
} else {
parent.setRight(targetNode.getLeft());
}
}
} else { // 若targetNode有右子节点
// 判断parent是否为空，
if (parent == null) {
this.root = targetNode.getRight();
} else {
if (parent.getLeft() == targetNode) {
parent.setLeft(targetNode.getRight());
} else {
parent.setRight(targetNode.getRight());
}
}
}
}
}
}
class BSTNode {
private int value;
private BSTNode left;
private BSTNode right;
public BSTNode(int value) {
this.value = value;
}
@Override
public String toString() {
return "BSTNode{" +
"value=" + value +
'}';
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public BSTNode getLeft() {
return left;
}
public void setLeft(BSTNode left) {
this.left = left;
}
public BSTNode getRight() {
return right;
}
public void setRight(BSTNode right) {
this.right = right;
}
}