延迟删除二进制搜索树

这是第一个发布的学习笔记. 我不保证所编写的代码必须正确. 如果您输入有误，请纠正我. 谢谢.

直接开始. 首先让我们谈谈数据结构. 与一般的二分搜索树相比，二分搜索树懒惰地删除了更多的字段二叉排序树 删除，还有更多的字段: theSize（剩余节点数），deletedSize（延迟删除的节点数），BinaryNode min max（用于保留标志的最有价值点！=在findMin和findMax方法中递归找到1）；在内部节点类中，还有一个附加的字节类型标志变量（= 1表示已删除），在这里，您还可以使用一个count字段，当有重复项时很常见. 初始计数为1，然后插入+1，然后删除-1且count>0. 我直接使用标志变量.

 1 class myLazyBinarySearchTree<AnyType extends Comparable<? super AnyType>> {
 2 　　 private BinaryNode<AnyType> root;
 3     private int theSize;// 总节点数
 4     private int deletedSize;// 懒惰删除的节点数
 5     private BinaryNode<AnyType> min = null;
 6     private BinaryNode<AnyType> max = null;
 7 
 8 　　public myLazyBinarySearchTree() {
 9         root = null;
10         this.deletedSize = 0;
11         this.theSize = 0;
12     }
13 
14 　　public boolean isEmpty() {
15         return theSize - deletedSize == 0;
16     }
17 }

包含（）比较简单. 在递归搜索中找到节点的标志变量后，对其进行检查. 插入例程也是如此. 如果存在元素，请检查标志变量是否为1.

以下是麻烦的remove（）方法. 实现方法与以前的LinkedList相同. 首先，将其递归删除. 找不到直接退货. 首先找到节点标志= 1，更改Size和DeletedSize，然后比较Size和DeletedSize. 值（延迟删除数> =剩余节点数），执行标准删除. 标准删除从根开始.

在标准删除中，如果不需要删除节点，则直接检查其左右子树. 如果检测到需要删除的节点，则检查①如果只有左子树或右子树二叉排序树 删除，则将这些子树拼接起来以重新检测该位置的节点. ②如果是叶节点，则直接设置Null即可删除. ③如果有左子树和右子树，则首先发现右子树是最小的子树，其标志= 0，分为两种情况. 然后直接将右子树设置为null，然后重新检测该节点（如果找到），调整标志等. 删除操作如下:

 1 public void remove(AnyType x) {
 2     remove(x, root);// 这里递归删除只能使用void在下面的remove的else中，t随着变化，而懒惰删除中，只有theSize<=deletedSize才变化，所以t时钟指向的root.造成错误。
 3     
 4 }
 5 
 6 private void remove(AnyType x, BinaryNode<AnyType> t) {
 7         if (t == null) {
 8             // 未找到
 9             return;
10         }
11 
12         int compareResult = x.compareTo(t.element);
13         if (compareResult < 0) {
14             remove(x, t.left);
15         } else if (compareResult > 0) {
16             remove(x, t.right);
17         } else {
18             // 找到了这个节点,标记删除
19             t.flag = 1;
20             this.theSize--;
21             this.deletedSize++;
22             checkDeletion();// 检测是否进行标准删除
23             System.out.println("root1:" + this.root.right);
24         }
25 }
26 
27 private void checkDeletion() {
28         if (this.theSize <= this.deletedSize) {
29             this.root = doRemove(root);
30             // 更新节点
31             this.deletedSize = 0;
32         }
33 }
34 
35 private BinaryNode<AnyType> doRemove(BinaryNode<AnyType> t) {// 删除树中所有flag=1的节点。使用递归
36 
37         if (t == null) {
38             return null;
39         }
40 
41         if (t.flag == 0) {// 不需要删除的节点,直接进入左右子树
42             //System.out.println("000");
43             t.left = doRemove(t.left);
44             t.right = doRemove(t.right);
45         } else {
46             if (t.left == null || t.right == null) {// 叶子节点或者只有一个子树
47                 t = (t.left != null) ? t.left : t.right;
48                 t = doRemove(t);// 检查拼接上来的子树
49             } else {// ②左右子树都存在
50                 min = null;
51                 findMin(t.right);
52                 if (min == null) {// 右子树上所有节点都被懒惰删除,直接将t的右子树删除，并继续监测t
53                     t.right = null;
54                     t = doRemove(t);
55                 } else {
56                     t.element = min.element;
57                     t.flag = 0;
58                     min.flag = 1;
59                     t = doRemove(t);
60                 }
61 
62             }
63         }
64         return t;
65 }

删除时，需要在右侧子树中找到最小值节点，并且其标志= 0，这是尚未删除的最小节点. 在这里，您可以参考二叉树中顺序遍历的实现，并且可以利用堆栈的后进先出功能. 为了简单明了，我使用了递归搜索并使用了前面定义的全局变量来存储最小的元素.

 1 private void findMin(BinaryNode<AnyType> t) {
 2         if (t != null) {
 3             findMin(t.left);
 4             if (t.flag == 0 && min == null) {
 5                 min = t;
 6                 return;
 7             }
 8             findMin(t.right);
 9         }
10 }

查找最大值的方法类似. 在删除的过程中，每次选择右子树的最小元素来替换删除的元素，很容易造成树的不平衡（请参阅P91），因此可以考虑随机删除，即最小的元素随机计算右子树的最大元素，以消除树的偏差.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-224959-1.html