文章出處

　　　第四章習題：二叉查找樹類實現懶惰刪除，注意findMin()和findMax()（遞歸）

　　算是發布的第一篇學習筆記。也不敢保證寫的代碼一定正確，錯了的地方請大家指正，謝謝。

　　直接開始吧。先談談數據結構，二叉查找樹懶惰刪除較于一般的二叉查找樹，多了一些域：theSize(剩下的節點數)、deletedSize(懶惰刪除的節點數)、BinaryNode<AnyType> min，max(用于保留在findMin和findMax方法中遞歸查詢到的flag!=1的最值點)；在內部節點類中，多了一個byte型的flag變量（=1則表示被刪除）。在這里，也可以使用一個count域，這在有重復項時很常用，初始的count都是1，以后有插入就+1，有刪除且count>0就-1.我使用的直接是flag標志變量。

 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 }

　　其中contains()比較簡單，在遞歸查找中找到后再查看一下節點的flag變量即可；insert例程也一樣，如果有是已存在元素，查看其flag變量是否=1。

　　下面是比較麻煩的remove()方法，實現方法和之前的LinkedList一樣，先是遞歸刪除，未找到直接return，找到了先將節點flag=1，改變theSize和deletedSize，然后比較theSize和deletedSize的值（懶惰刪除的數目>=剩下的節點數目），進行標準刪除。標準刪除從root開始。

　　在標準刪除中，如果節點不需要刪除，直接檢查其左右子樹。如果檢測到需要刪除的節點，再檢測①若只存在左子樹或者右子樹，則將子樹拼接上來，重新檢測該位置節點。②若是葉子節點，直接置Null刪除。③若有左子樹也右子樹，則同理先將右子樹找到一個最小的且flag=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 }

　　在刪除需要查找右子樹中最小數值節點且其flag=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 }