forked from dairongpeng/algorithm-note
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path23.md
More file actions
2362 lines (1927 loc) · 68.2 KB
/
23.md
File metadata and controls
2362 lines (1927 loc) · 68.2 KB
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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
- [1 有序表原理及扩展](#1)
* [1.1 搜索二叉树](#11)
* [1.2 搜索二叉树的增删改查](#12)
+ [1.2.1 搜索二叉树的查找和添加](#121)
* [1.3 传统搜索二叉树存在的问题](#13)
+ [1.3.1 平衡搜索二叉树](#131)
+ [1.3.2 左旋和右旋](#132)
* [1.4 有序表](#14)
* [1.5 有序表的实现（AVL树，SB树，红黑树）](#15)
+ [1.5.1 AVL树](#151)
- [1.5.1.1 AVL树针对某个节点的平衡性处理](#1511)
+ [1.5.2 SB树](#152)
- [1.5.2.1 SB树针对某个节点的平衡性处理](#1521)
+ [1.5.3 红黑树](#153)
- [1.5.3.1 红黑树针对某个节点的平衡性处理](#1531)
* [1.5.3.1.1 Redis为什么选择跳表的结构？](#15311)
* [1.6 跳表SkipList（也可实现有序表功能）](#16)
* [1.7 有序表例题实战](#17)
+ [1.7.1 哪些情况下需要改写系统的有序表？](#171)
<h1 id='1'>1 有序表原理及扩展</h1>
<h2 id='11'>1.1 搜索二叉树</h2>
经典的搜索二叉树，是没有重复值的，任何节点为头的数，左孩子都比自己小，右孩子都比自己大
允许重复值的改进的搜索二叉树，可以在每个节点上增加一个统计词频的数据项。表示出现了几次；但是不可相等的放到左右孩子上，搜索二叉树变平衡时，会影响后续的旋转
1、搜索二叉树一定要说明以什么标准来排序
2、经典的搜索二叉树，树上没有重复的用来排序的key值
3、如果有重复节点的需求，可以在一个节点内部增加数据项
<h2 id='12'>1.2 搜索二叉树的增删改查</h2>
<h2 id='121'>1.2.1 搜索二叉树的查找和添加</h2>
- 查找
搜索二叉树查询key（查询某个key存在还是不存在），当前节点比自己小，到右子树上去找，当前节点比自己大，到其左孩子上去找，越界，说明不存在
1、如果当前节点的value==key，返回true
2、如果当前节点的value<key，当前节点向左移动
3、如果当前节点的value>key，当前节点向右移动
4、如果当前节点变成null，返回false
- 添加
和查询过程一样，但当前节点滑到空的时候，就插入在这里
- 删除
1、先找到key所在的节点
2、如果该节点没有左孩子、没有右孩子，直接删除即可（好理解）
3、如果该节点有左孩子、没有右孩子，直接用左孩子顶替该节点（好理解）
4、如果该节点没有左孩子、有右孩子，直接用右孩子顶替该节点（好理解）
5、如果该节点有左孩子、有右孩子，用该节点后继节点顶替该节点（需要旋转调整，没法有左右孩子去替换，原因是左右孩子也有左右孩子）
==一个节点的后继节点，就是该节点右孩子的最左的那个节点。==
```
graph TD
2-->1
2-->5
5-->3
5-->10
10-->8
10-->13
8-->6
6-->7
```
比如我要删除5节点，那么5节点的后继节点就是其右子树的最左的孩子，也就是6。把6替换掉5，6的右孩子给它父亲作为左孩子，得到
```
graph TD
2-->1
2-->6
6-->3
6-->10
10-->8
10-->13
8-->7
```
```Java
package class05;
/**
* Not implemented by zuochengyun
*
* Abstract binary search tree implementation. Its basically fully implemented
* binary search tree, just template method is provided for creating Node (other
* trees can have slightly different nodes with more info). This way some code
* from standart binary search tree can be reused for other kinds of binary
* trees.
*
* @author Ignas Lelys
* @created Jun 29, 2011
*
*/
public class AbstractBinarySearchTree {
/** Root node where whole tree starts. */
public Node root;
/** Tree size. */
protected int size;
/**
* Because this is abstract class and various trees have different
* additional information on different nodes subclasses uses this abstract
* method to create nodes (maybe of class {@link Node} or maybe some
* different node sub class).
*
* @param value
* Value that node will have.
* @param parent
* Node's parent.
* @param left
* Node's left child.
* @param right
* Node's right child.
* @return Created node instance.
*/
protected Node createNode(int value, Node parent, Node left, Node right) {
return new Node(value, parent, left, right);
}
/**
* Finds a node with concrete value. If it is not found then null is
* returned.
* 查找节点
*
* @param element
* Element value.
* @return Node with value provided, or null if not found.
*/
public Node search(int element) {
Node node = root;
while (node != null && node.value != null && node.value != element) {
// 小于当前节点，找左孩子对比
if (element < node.value) {
node = node.left;
} else {
// 大于当前节点，找右孩子对比
node = node.right;
}
}
return node;
}
/**
* Insert new element to tree.
* 插入一个节点
*
* @param element
* Element to insert.
*/
public Node insert(int element) {
// 首先如果这个树是空的，把该节点当成头节点
if (root == null) {
root = createNode(element, null, null, null);
size++;
return root;
}
// 需要插入在该节点下面
Node insertParentNode = null;
Node searchTempNode = root;
while (searchTempNode != null && searchTempNode.value != null) {
insertParentNode = searchTempNode;
if (element < searchTempNode.value) {
searchTempNode = searchTempNode.left;
} else {
searchTempNode = searchTempNode.right;
}
}
Node newNode = createNode(element, insertParentNode, null, null);
if (insertParentNode.value > newNode.value) {
insertParentNode.left = newNode;
} else {
insertParentNode.right = newNode;
}
size++;
return newNode;
}
/**
* Removes element if node with such value exists.
* 删除节点，每个节点由于加入向上的指针，那么旋转的时候会方便些
*
* @param element
* Element value to remove.
*
* @return New node that is in place of deleted node. Or null if element for
* delete was not found.
*/
public Node delete(int element) {
Node deleteNode = search(element);
if (deleteNode != null) {
return delete(deleteNode);
} else {
return null;
}
}
/**
* Delete logic when node is already found.
*
* @param deleteNode
* Node that needs to be deleted.
*
* @return New node that is in place of deleted node. Or null if element for
* delete was not found.
* 注意，删除方法返回的是删除后接管删除节点的位置的节点，返回
*/
protected Node delete(Node deleteNode) {
if (deleteNode != null) {
Node nodeToReturn = null;
if (deleteNode != null) {
if (deleteNode.left == null) {
// 左孩子为空，右孩子直接替换该节点，达到删除的效果
// transplant(a,b) b去替换a的环境，a断连掉，把b返回
nodeToReturn = transplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == null) {
// 右孩子为空，左孩子直接替换，达到删除的目的
nodeToReturn = transplant(deleteNode, deleteNode.left);
} else {
// 否则，要删除的节点既有左孩子，又有右孩子，找右子树的最左的孩子
Node successorNode = getMinimum(deleteNode.right);
// 要删除的节点的右孩子，有左孩子。最左孩子的右孩子要它父亲来接管
if (successorNode.parent != deleteNode) {
transplant(successorNode, successorNode.right);
successorNode.right = deleteNode.right;
successorNode.right.parent = successorNode;
}
// 如果要删除的节点的右孩子，没有左孩子。直接用要删除的节点的右孩子进行替换即可
transplant(deleteNode, successorNode);
successorNode.left = deleteNode.left;
successorNode.left.parent = successorNode;
nodeToReturn = successorNode;
}
size--;
}
return nodeToReturn;
}
return null;
}
/**
* Put one node from tree (newNode) to the place of another (nodeToReplace).
*
* @param nodeToReplace
* Node which is replaced by newNode and removed from tree.
* @param newNode
* New node.
*
* @return New replaced node.
*/
private Node transplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == null) {
this.root = newNode;
} else if (nodeToReplace == nodeToReplace.parent.left) {
nodeToReplace.parent.left = newNode;
} else {
nodeToReplace.parent.right = newNode;
}
if (newNode != null) {
newNode.parent = nodeToReplace.parent;
}
return newNode;
}
/**
* @param element
* @return true if tree contains element.
*/
public boolean contains(int element) {
return search(element) != null;
}
/**
* @return Minimum element in tree.
*/
public int getMinimum() {
return getMinimum(root).value;
}
/**
* @return Maximum element in tree.
*/
public int getMaximum() {
return getMaximum(root).value;
}
/**
* Get next element element who is bigger than provided element.
*
* @param element
* Element for whom descendand element is searched
* @return Successor value.
*/
// TODO Predecessor
public int getSuccessor(int element) {
return getSuccessor(search(element)).value;
}
/**
* @return Number of elements in the tree.
*/
public int getSize() {
return size;
}
/**
* Tree traversal with printing element values. In order method.
*/
public void printTreeInOrder() {
printTreeInOrder(root);
}
/**
* Tree traversal with printing element values. Pre order method.
*/
public void printTreePreOrder() {
printTreePreOrder(root);
}
/**
* Tree traversal with printing element values. Post order method.
*/
public void printTreePostOrder() {
printTreePostOrder(root);
}
/*-------------------PRIVATE HELPER METHODS-------------------*/
private void printTreeInOrder(Node entry) {
if (entry != null) {
printTreeInOrder(entry.left);
if (entry.value != null) {
System.out.println(entry.value);
}
printTreeInOrder(entry.right);
}
}
private void printTreePreOrder(Node entry) {
if (entry != null) {
if (entry.value != null) {
System.out.println(entry.value);
}
printTreeInOrder(entry.left);
printTreeInOrder(entry.right);
}
}
private void printTreePostOrder(Node entry) {
if (entry != null) {
printTreeInOrder(entry.left);
printTreeInOrder(entry.right);
if (entry.value != null) {
System.out.println(entry.value);
}
}
}
protected Node getMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
protected Node getMaximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}
protected Node getSuccessor(Node node) {
// if there is right branch, then successor is leftmost node of that
// subtree
if (node.right != null) {
return getMinimum(node.right);
} else { // otherwise it is a lowest ancestor whose left child is also
// ancestor of node
Node currentNode = node;
Node parentNode = node.parent;
while (parentNode != null && currentNode == parentNode.right) {
// go up until we find parent that currentNode is not in right
// subtree.
currentNode = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
// -------------------------------- TREE PRINTING
// ------------------------------------
public void printTree() {
printSubtree(root);
}
public void printSubtree(Node node) {
if (node.right != null) {
printTree(node.right, true, "");
}
printNodeValue(node);
if (node.left != null) {
printTree(node.left, false, "");
}
}
private void printNodeValue(Node node) {
if (node.value == null) {
System.out.print("<null>");
} else {
System.out.print(node.value.toString());
}
System.out.println();
}
private void printTree(Node node, boolean isRight, String indent) {
if (node.right != null) {
printTree(node.right, true, indent + (isRight ? " " : " | "));
}
System.out.print(indent);
if (isRight) {
System.out.print(" /");
} else {
System.out.print(" \\");
}
System.out.print("----- ");
printNodeValue(node);
if (node.left != null) {
printTree(node.left, false, indent + (isRight ? " | " : " "));
}
}
public static class Node {
public Node(Integer value, Node parent, Node left, Node right) {
super();
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
public Integer value;
public Node parent;
public Node left;
public Node right;
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((value == null) ? 0 : value.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
}
}
```
<h2 id='13'>1.3 传统搜索二叉树存在的问题</h2>
1）基础的搜索二叉树，添加、删除时候不照顾平衡性
2）数据状况很差时，性能就很差
==给搜索二叉树引入两个动作：左旋、右旋==
输入状况，决定性能。比如输入状况构建出来的树，严重不平衡。极端情况是只有一条通往底部的路径，高度为n;
平衡二叉树的定义，任何子树，左子树的高度和右子树的高度差，不大于1。所以对于n个节点，平衡二叉树的高度，就是logN
<h3 id='131'>1.3.1 平衡搜索二叉树</h3>
平衡搜索二叉树，就是在插入和删除的过程中，动态的保持平衡性。保持平衡的代价保持在logN。平衡搜索二叉树的实现由很多，红黑树只是其中一种
<h3 id='132'>1.3.2 左旋和右旋</h3>
左旋和右旋针对头结点而言的，即对哪个头结点进行左旋还是右旋；顾名思义如果对头结点为a的子树右旋，那么a倒到右边，a的左孩子顶上来，到a原来的位置上去。a原来左孩子的右孩子，现在当做a的左孩子，如下图
```
graph TD
a-->b
a-->c
c-->d
c-->e
b-->f
b-->g
```
a右旋，得到：
```
graph TD
b-->f
b-->a
a-->g
a-->c
c-->d
c-->e
```
同理，a左旋，得到：
```
graph TD
c-->a
c-->e
a-->b
a-->d
b-->f
b-->g
```
带左旋和右旋的搜索二叉树，在经典搜索二叉树上做的扩展，继承经典搜索二叉树。
```Java
package class05;
/**
* Not implemented by zuochengyun
*
* Abstract class for self balancing binary search trees. Contains some methods
* that is used for self balancing trees.
*
* @author Ignas Lelys
* @created Jul 24, 2011
*
*/
public abstract class AbstractSelfBalancingBinarySearchTree
extends AbstractBinarySearchTree {
/**
* Rotate to the left.
*
* @param node Node on which to rotate.
* @return Node that is in place of provided node after rotation.
*/
protected Node rotateLeft(Node node) {
Node temp = node.right;
temp.parent = node.parent;
node.right = temp.left;
if (node.right != null) {
node.right.parent = node;
}
temp.left = node;
node.parent = temp;
// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
/**
* Rotate to the right.
*
* @param node Node on which to rotate.
* @return Node that is in place of provided node after rotation.
*/
protected Node rotateRight(Node node) {
Node temp = node.left;
temp.parent = node.parent;
node.left = temp.right;
if (node.left != null) {
node.left.parent = node;
}
temp.right = node;
node.parent = temp;
// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
}
```
<h2 id='14'>1.4 有序表</h2>
在Java中，就是TreeMap，有序表和Hash表（HashMap）的操作类似，但是有序表中自动把我们的key排好了顺序，我们也可以传入比较器，自定义对比和排序的规则；我们可以通过TreeMap直接得到最大节点和最小节点，也可以获取大于某个值的第一个Key是什么等等
为什么TreeMap可以做到有序，原因是TreeMap的底层是一个平衡搜索二叉树
- Hash表和有序表对比
1、HashMap的所有操作是O(1)的，TreeMap的所有操作是O(logN)
2、使用有序表的Key必须是可以比较的，没法自然比较的需要传入自定义比较器
<h2 id='15'>1.5 有序表的实现（AVL树，SB树，红黑树）</h2>
在有序表中，有序表是一种规范，类似于接口名。规范为key要按序组织，所有操作要是O(logN)等。各种树结构可以实现有序表的功能。其中红黑树只是有序表的一个实现
==AVL树，SB树，红黑树，都是有序表的一种实现。都是平衡搜索二叉树，这三种树在功能和时间复杂度上几乎无差别，在实现细节上也就是在常数时间上，会有差别。三种树调整检查哪些节点的平衡性相同，下文进行说明。每种树针对每个节点的平衡性调整不同，但是都是使用左旋和右旋两个动作==
- AVL树，SB树，红黑树的共性
1）都是搜索二叉树
2）插入、删除、查询（一切查询）搜索二叉树怎么做，这些结构都这么做
3）使用调整的基本动作都只有左旋、右旋
4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查
5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)
- AVL树，SB树，红黑树不同之处
1）平衡性的约束不同
AVL树最严格、SB树稍宽松、红黑树最宽松
2）插入、删除和搜索二叉树一样，但是额外，做各自的平衡性调整。各自的平衡性调整所使用的动作都是左旋或者右旋
<h3 id='151'>1.5.1 AVL树</h3>
是这三个平衡搜索二叉树中，平衡性最严格的，左树高度和右树高度的绝对值，严格小于2
AVL树在插入节点的时候，只会向上检查节点的平衡性有没有被破坏。删除节点也一样，只会检查删除的那个节点向上的那条链上的节点有没被破坏。删除的时候，如果被删除的节点没有左右孩子那么直接检查，如果有右孩子，是去检查后继节点原来所在的位置的向上节点的平衡性
==实质上三种树删除和插入节点，检查哪些节点需要调整平衡都是这样的查找规则，对于删除来说，只有左树和只有右树没影响，如果左右树都存在，是去检查后继节点原来所在的位置向上的平衡性。只是具体到某个节点平衡性的处理上，三种树不一样==
<h4 id='1511'>1.5.1.1 AVL树针对某个节点的平衡性处理</h4>
1、该节点左树高度和右树高度差的绝对值|L-R|，小于2。不违规，无须调整
2、|L-R|大于1，说明要不然左树高度大了，要不然右树高度大了。而且之前的每一步都进行了调整，所以高度差不会超过2。高度不平衡对应四种情况，被称为RR形违规，RL形违规，LL形违规，LR形违规。首字母表示左树变高了还是右树变高了，比如RR和RL都表示经过插入或者删除，右树的高度变大了
RR表示，右子节点的右树过长，RL表示右子节点的左树过长。同理LL表示左子节点的左子树高度过长导致，LR表示左子节点的右树高度过长导致的不平衡
- LL形违规，对该节点进行一次右旋即可
```
graph TD
x-->y
x-->p
y-->z
y-->t
z-->k
```
右旋后得到：
```
graph TD
y-->z
y-->x
z-->k
x-->t
x-->p
```
- 同理RR形违规，对该节点进行一次左旋即可
- LR形,让底部的孙子节点，来到顶部来。
下面例子，想办法让x的孙子节点t节点来到顶部，先对y节点进行一次左旋,再对x节点做一次右旋
```
graph TD
x-->y
x-->p
y-->z
y-->t
t-->k
```
先对y节点进行一次左旋
```
graph TD
x-->t
x-->p
y-->z
t-->y
t-->k
```
再对x节点做一次右旋
```
graph TD
t-->y
t-->x
x-->k
x-->p
y-->z
```
原x的孙子节点t此时，调整到的顶部
- 同理RL形,也是让超过长度的那一侧底部的孙子节点，来到顶部来。
==LL形和RR形旋转一次O(1)，LR和RL形旋转两次，也是O(1)。那么即使删除或者添加的节点影响的整个向上的链路，整体复杂度也是O(logN)==
AVL树继承自带左右旋的平衡搜索二叉树，在此基础上做的扩展，code如下：
```Java
package class05;
/**
* Not implemented by zuochengyun
*
* AVL tree implementation.
*
* In computer science, an AVL tree is a self-balancing binary search tree, and
* it was the first such data structure to be invented.[1] In an AVL tree, the
* heights of the two child subtrees of any node differ by at most one. Lookup,
* insertion, and deletion all take O(log n) time in both the average and worst
* cases, where n is the number of nodes in the tree prior to the operation.
* Insertions and deletions may require the tree to be rebalanced by one or more
* tree rotations.
*
* @author Ignas Lelys
* @created Jun 28, 2011
*
*/
public class AVLTree extends AbstractSelfBalancingBinarySearchTree {
/**
* @see trees.AbstractBinarySearchTree#insert(int)
*
* AVL tree insert method also balances tree if needed. Additional height
* parameter on node is used to track if one subtree is higher than other
* by more than one, if so AVL tree rotations is performed to regain
* balance of the tree.
*/
@Override
public Node insert(int element) {
Node newNode = super.insert(element);
// 对有影响的节点，顺着parent指针向上做平衡性检查调整
rebalance((AVLNode) newNode);
return newNode;
}
/**
* @see trees.AbstractBinarySearchTree#delete(int)
*/
@Override
public Node delete(int element) {
// 先查出来需要删的值，存在的话进行删除
Node deleteNode = super.search(element);
if (deleteNode != null) {
// 先调用父类，也就是带左右旋的平衡搜索二叉树的删除，把删除的节点后哪个节点接管了被删除的位置，该节点返回
Node successorNode = super.delete(deleteNode);
// 接管的节点不为空，检查是哪一种替换的方式，左孩子接管or右孩子接管，or后继节点接管，or既没有左孩子有没有右孩子直接删除
if (successorNode != null) {
// if replaced from getMinimum(deleteNode.right) then come back there and update
// heights
AVLNode minimum = successorNode.right != null ? (AVLNode) getMinimum(successorNode.right)
: (AVLNode) successorNode;
// 重新计算高度（重要）
recomputeHeight(minimum);
// 重新进行平衡（重要）
rebalance((AVLNode) minimum);
} else { // 并没有任何节点替代被删除节点的位置，被删除节点是孤零零被删除的
recomputeHeight((AVLNode) deleteNode.parent);
rebalance((AVLNode) deleteNode.parent);
}
return successorNode;
}
return null;
}
/**
* @see trees.AbstractBinarySearchTree#createNode(int,
* trees.AbstractBinarySearchTree.Node,
* trees.AbstractBinarySearchTree.Node,
* trees.AbstractBinarySearchTree.Node)
*/
@Override
protected Node createNode(int value, Node parent, Node left, Node right) {
return new AVLNode(value, parent, left, right);
}
/**
* Go up from inserted node, and update height and balance informations if
* needed. If some node balance reaches 2 or -2 that means that subtree must be
* rebalanced.
*
* @param node Inserted Node.
*/
private void rebalance(AVLNode node) {
while (node != null) {
// 先记录一下父环境
Node parent = node.parent;
// 左右树的高度拿出来
int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
int nodeBalance = rightHeight - leftHeight;
// rebalance (-2 means left subtree outgrow, 2 means right subtree)
// 右树过高
if (nodeBalance == 2) {
// 判断是RR形还是RL形，确定进行一次还是两次旋转
if (node.right.right != null) {
// 旋转，旋转的过程中，一定维护好高度信息
node = (AVLNode) avlRotateLeft(node);
break;
} else {
node = (AVLNode) doubleRotateRightLeft(node);
break;
}
// 左树过高
} else if (nodeBalance == -2) {
// 同理，判断是LL还是LR
if (node.left.left != null) {
node = (AVLNode) avlRotateRight(node);
break;
} else {
node = (AVLNode) doubleRotateLeftRight(node);
break;
}
} else {
updateHeight(node);
}
// 把当前node向上变为父节点，向上窜，继续调整平衡
node = (AVLNode) parent;
}
}
/**
* Rotates to left side.
*/
private Node avlRotateLeft(Node node) {
Node temp = super.rotateLeft(node);
updateHeight((AVLNode) temp.left);
updateHeight((AVLNode) temp);
return temp;
}
/**
* Rotates to right side.
*/
private Node avlRotateRight(Node node) {
Node temp = super.rotateRight(node);
updateHeight((AVLNode) temp.right);
updateHeight((AVLNode) temp);
return temp;
}
/**
* Take right child and rotate it to the right side first and then rotate node
* to the left side.
*/
protected Node doubleRotateRightLeft(Node node) {
node.right = avlRotateRight(node.right);
return avlRotateLeft(node);
}
/**
* Take right child and rotate it to the right side first and then rotate node
* to the left side.
*/
protected Node doubleRotateLeftRight(Node node) {
node.left = avlRotateLeft(node.left);
return avlRotateRight(node);
}
/**
* Recomputes height information from the node and up for all of parents. It
* needs to be done after delete.
*/
private void recomputeHeight(AVLNode node) {
while (node != null) {
node.height = maxHeight((AVLNode) node.left, (AVLNode) node.right) + 1;
node = (AVLNode) node.parent;
}
}
/**
* Returns higher height of 2 nodes.
*/
private int maxHeight(AVLNode node1, AVLNode node2) {
if (node1 != null && node2 != null) {
return node1.height > node2.height ? node1.height : node2.height;
} else if (node1 == null) {
return node2 != null ? node2.height : -1;
} else if (node2 == null) {
return node1 != null ? node1.height : -1;
}
return -1;
}
/**
* Updates height and balance of the node.
*
* @param node Node for which height and balance must be updated.
*/
private static final void updateHeight(AVLNode node) {
int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
node.height = 1 + Math.max(leftHeight, rightHeight);
}
/**