定义
一棵二叉树时高度平衡的。如果 T 是一棵非空二叉树，TL 和 TR 分别是 T 的左子树和右子树，HL 和 HR 是 TL 和 TR 的高度。那么当T是高度平衡的当且仅当:
- TL和 TR 是高度平衡的。
- Abs(HL - HR) <= 1
高度平衡的二叉树的定义要求其所有子树也是高度平衡的。由定义引入平衡因子 （BalanceFactor），取值 -1、0、1代表着 HL - HR。
旋转
由插入和删除操作导致二叉树失去平衡，也就是平衡因子 大于 1 或者 小于 -1。通过当前结点 parent 和 子节点 child 以及子孙结点 grandchild 的指向关系，有 LL、RR、LR、RR关系。如下图
平衡子树
左子树平衡
左子树高度减去右子树高度大于等于 2，左子树失去平衡，进行旋转后再次平衡， 这里分为两种情况（令当前结点为 parent 左孩子为 child ）：
LL 型
- 左子树的左子树的高度增加
- 左子树的右子树高度减少
如果 child 的平衡因子为 1 则仅需进行右旋转即可，旋转后， parent 和 child 的平衡因子设置为 0，图中 (1.1) 所示。
LR 型
- 左子树的右子树的高度增加
- 左子树的左子树高度减少
如果 child 的平衡因子为 -1 ，则需要进行两次旋转，先对 child 进行左旋，然后对 parent 进行右旋，取 child 的右孩子 grandchild：
- 如果 grandchild 的平衡因子 等于 1 则 child 的平衡因子设置为 0 ，parent 的平衡因子设置为 -1，grandchild 的平衡因子设置为0，图中（1.2）所示
- 如果 grandchild 的平衡因子 等于 -1 则 child 的平衡因子设置为 1， parent 的平衡因子设置为 0， grandchild 的平衡因子设置为0，图中（1.3）所示。
1 private void leftBalance(AvlNode<T> node) {
2 AvlNode<T> child = node.getLeft();
3 if (child.getBf() == LH) {
4 /* 左子树 的 左子树增高 LL */
5 right_Rotation(node);
6 node.setBf(EH);
7 child.setBf(EH);
8 } else {
9 /* 左子树 的 右子树增高 LR */
10 AvlNode<T> grandChild = child.getRight();
11 switch (grandChild.getBf()) {
12 case RH: {
13 node.setBf(EH);
14 child.setBf(LH);
15 break;
16 }
17 case EH : {
18 node.setBf(EH);
19 child.setBf(EH);
20 break;
21 }
22 case LH : {
23 node.setBf(RH);
24 child.setBf(EH);
25 break;
26 }
27 }
28 grandChild.setBf(EH);
29
30 left_Rotation(child);
31 right_Rotation(node);
32 }
33 }
右子树平衡
左子树高度减去右子树高度大于等于 -2，右子树失去平衡，进行旋转后再次平衡， 这里分为两种情况（令当前结点为 parent 右孩子为 child ）：
RL 型
- 右子树的左子树高度增加
- 右子树的右子树高度减少
如果 child 的平衡因子为 1 则 需要进行两次旋转，先对 child 进行右旋 然后 对 parent 进行左旋，取 child 的左孩子 grandchild ：
- 如果 grandchild 的平衡因子为 1 则 旋转后设置 parent 的平衡因子为 0， child 的平衡因子为 -1， grandchild 平衡因子为0，图中（2.3）所示。
- 如果 grandchild 的平衡因子为 -1 则 旋转后设置 parent 的平衡因子为 1，child 的平衡因子为 0， grandchild 平衡因子为0，图中（2.2）所示。
RR 型
- 右子树的右子树高度增加
- 右子树的左子树高度减少
如果 child 的平衡因子为 -1 则 进行一次左旋即可，旋转后设置 parent 的平衡因子为 0，child 的平衡因子为 0，图中（2.1）所示。
1 private void rightBalance(AvlNode<T> node) {
2 AvlNode<T> child = node.getRight();
3 if (child.getBf() == RH) {
4 /* RR */
5 node.setBf(EH);
6 child.setBf(EH);
7 left_Rotation(node);
8 } else {
9 /* RL */
10 AvlNode<T> grand = child.getLeft();
11 switch (grand.getBf()) {
12 case RH : {
13 node.setBf(LH);
14 child.setBf(EH);
15 break;
16 }
17 case EH : {
18 node.setBf(EH);
19 child.setBf(EH);
20 break;
21 }
22 case LH : {
23 node.setBf(EH);
24 child.setBf(RH);
25 break;
26 }
27 }
28 grand.setBf(EH);
29 right_Rotation(child);
30 left_Rotation(node);
31 }
32 }
旋转
左旋转函数
当前结点为n， nr 为 n 的右孩子，nrl 为 nr 的左孩子， 旋转设置为：将 nr 的左孩子设置为 n， 将 n 的右孩子设置 nrl。
1 private void left_Rotation(AvlNode<T> n) {
2 /*
3 * n nr
4 * / \ / \
5 * nl nr => n nrr
6 * / \ / \
7 * nrl nrr nl nrl
8 */
9 AvlNode<T> p = n.getParent();
10 AvlNode<T> nr = n.getRight();
11 AvlNode<T> nrl = nr.getLeft();
12 int pointer = p != null ? (p.getLeft() == n ? LEFT : RIGHT) : NONE;
13 n.setRight(nrl);
14 nr.setLeft(n);
15 if (p == null) {
16 head = nr;
17 nr.setParent(null);
18 } else if (pointer == LEFT)
19 p.setLeft(nr);
20 else
21 p.setRight(nr);
22 }
右旋转函数
当前结点 n， nl 为 n 的左孩子，nlr 为 nl 的右孩子，旋转设置：nl 的右孩子设置为 n， n 的左孩子设置为 nlr。
1 private void right_Rotation(AvlNode<T> n) {
2 /*
3 * n nl
4 * / \ / \
5 * nl nr => nll n
6 * / \ / \
7 * nll nlr nlr nr
8 */
9 AvlNode<T> p = n.getParent();
10 AvlNode<T> nl = n.getLeft();
11 AvlNode<T> nlr = nl.getRight();
12 int pointer = p != null ? (p.getLeft() == n ? LEFT : RIGHT) : NONE;
13 n.setLeft(nlr);
14 nl.setRight(n);
15
16 if (p == null) {
17 head = nl;
18 nl.setParent(null);
19 } else if (pointer == LEFT)
20 p.setLeft(nl);
21 else
22 p.setRight(nl);
23 }
结点定义
1 public class AvlNode <T extends Comparable<T>> {
2 /** 数据域 */
3 private T data;
4 /** 父节点 */
5 private AvlNode parent;
6 /** 左子树根节点 */
7 private AvlNode left;
8 /** 右子树根节点 */
9 private AvlNode right;
10 /** 平衡因子 */
11 private int bf;
12
13 public AvlNode(T data) {
14 this.data = data;
15 bf = 0;
16 }
17 // 省略 getter setter
18 }
树定义
定义根节点、常量定义以及基本方法。
1 public class AvlTree<T extends Comparable<T>> implements Tree<AvlNode<T>, T> {
2
3 /** 左子树高于右子树 */
4 private static final int LH = 1;
5 /** 左子树和右子树相同 */
6 private static final int EH = 0;
7 /** 左子树低于右子树 */
8 private static final int RH = -1;
9 /** 左指针 */
10 private static final int LEFT = 1;
11 /** 右指针 */
12 private static final int RIGHT = 2;
13 /** 未知 */
14 private static final int NONE = 0;
15
16 /* 比较结果 */
17 static final int QUEUE_INITIALIZE = 0x00000000;
18 static final int GRATER = 0x00000001;
19 static final int LESS = 0x00000000;
20 static final int VALID_BIT = 0x00000001;
21
22 private AvlNode<T> head;
23
24 }
查找元素
1 @Override
2 public AvlNode<T> search(T data) {
3 if (data == null) return null;
4 AvlNode<T> n = head;
5 while (n != null) {
6 int r = data.compareTo(n.getData());
7 if (r == 0) return n;
8 if (r < 0) n = n.getLeft();
9 if (r > 0) n = n.getRight();
10 }
11 return null;
12 }
插入元素
插入肯定在某个叶子结点上，树的高度增加，平衡因子也要改变。需要自底向上改变平衡因子，当遇到平衡因子为 -2 和 2 时需要做相应的子树平衡，平衡后的子树高度不变，因此会终止向上回溯。
- 如果是空树 则构建一个根节点的树。
- 遍历树，查找给定的元素，如果找到则插入失败 否则 在叶子结点上插入新结点。
- 从插入新结点的叶子结点向上更改平衡因子：
- 如平衡因子改变后为 -2 或者 2 则需要进行平衡，平衡后终止回溯。
- 如平衡因子改变后变后为 0 则意味着树的高度未变，终止回溯。
- 如平衡因子改变后变为 -1 或者 1，意味着树的高度改变，继续向上回溯。
1 public boolean insert(T data) {
2 if (data == null) {
3 return false;
4 }
5 AvlNode<T> n = head;
6 if (n == null) {
7 // 空树 构建头节点
8 head = new AvlNode<>(data);
9 return true;
10 }
11 AvlNode<T> next = null;
12 //查找比较结果 0 为小于 , 1 为 大于
13 int cq = QUEUE_INITIALIZE;
14 while (n != null) {
15 int r = data.compareTo(n.getData());
16 if (r == 0) return false;
17 // 之前比较结果队列左移一位，将当前结果放置在后低位
18 cq = (cq << 1) | ((r < 0 ? LESS : GRATER) & VALID_BIT);
19 if (r < 0) {
20 if ((next = n.getLeft()) == null) {
21 n.setLeft(new AvlNode(data));
22 break;
23 }
24 } else {
25 if ((next = n.getRight()) == null) {
26 n.setRight(new AvlNode(data));
27 break;
28 }
29 }
30 n = next;
31 }
32 // 逆序设置平衡因子
33 BACK_TRACE:
34 while (n != null) {
35 int r = cq & VALID_BIT;
36 if (r == LESS) {
37 switch (n.getBf()) {
38 case RH: n.setBf(EH); break BACK_TRACE;
39 case EH: n.setBf(LH); break;
40 case LH: leftBalance(n); break BACK_TRACE;
41 }
42 } else if (r == GRATER) {
43 switch (n.getBf()) {
44 case RH: rightBalance(n); break BACK_TRACE;
45 case EH: n.setBf(RH); break;
46 case LH: n.setBf(EH); break BACK_TRACE;
47 }
48 }
49 n = n.getParent();
50 cq = cq >> 1;
51 }
52 return true;
53 }
删除元素
任何删除非叶子结点都可转为对叶子结点的删除，因为非叶子结点，可以用该结点的直接前驱（左子树的最右结点）或者直接后继（右子树的最左结点）来替换，因此只考虑对叶子结点的删除即可。删除后，会出现树的高度变化，这时候需要进行平衡因子的重置以及树的再次平衡。
1 public void remove(T data) {
2 AvlNode<T> node = head;
3 if (node == null) return;
4 int cq = QUEUE_INITIALIZE;
5 AvlNode<T> d = null;
6 /* 查找到要删除的结点 */
7 while (node != null) {
8 int r = data.compareTo(node.getData());
9 if (r == 0) {
10 d = node;
11 break;
12 }
13 //指向结果入队
14 cq = (cq << 1) | ((r < 0 ? LESS : GRATER) & VALID_BIT);
15 if (r < 0)
16 node = node.getLeft();
17 else
18 node = node.getRight();
19 }
20 if (d == null) return; /* NOT FOUND */
21 /* 将待删除结点赋值给 node 变量，寻找右子树最小值结点或者左子树最大值结点，即 d 的直接前驱或者直接后继*/
22 node = d;
23 int pointer = NONE;
24 AvlNode<T> next = null;
25 if ((next = node.getRight()) == null) {
26 if ((next = node.getLeft()) != null) {
27 pointer = LEFT;
28 cq = (cq << 1) | (LESS & VALID_BIT);
29 }
30 } else {
31 cq = (cq << 1) | (GRATER & VALID_BIT);
32 pointer = RIGHT;
33 }
34 //next == null 说明 d 就是叶子结点
35 if (next != null) {
36 node = next;
37 while (true) {
38 if (pointer == RIGHT) {
39 if ((next = node.getLeft()) != null)
40 cq = (cq << 1) | (LESS & VALID_BIT);
41 } else {
42 if ((next = node.getRight()) != null)
43 cq = (cq << 1) | (GRATER & VALID_BIT);
44 }
45 if (next == null) break;
46 node = next;
47 }
48 }
49 if (d != node) d.setData(node.getData());
50 AvlNode<T> p = node.getParent();
51 if (p == null) {
52 /* 根结点直接置空树 */
53 head = null;
54 return;
55 }
56
57 //逆序设置平衡因子 并再次平衡子树,
58 node = p;
59 int dr = cq & VALID_BIT;
60 BACK_TRACE:
61 while (node != null) {
62 int r = cq & VALID_BIT;
63 int bf = node.getBf();
64 next = node.getParent();
65 if (r == LESS) {
66 /* 左子树高度减少 */
67 switch (bf) {
68 /** 高度减少 继续回溯 */
69 case LH: node.setBf(EH); break;
70 /** 高度无变化,结束回溯 */
71 case EH: node.setBf(RH); break BACK_TRACE;
72 /** 左子树高度减少,右子树变高，进行右子树平衡,平衡后高度会减少，继续向上回溯 */
73 case RH: rightBalance(node); break;
74 }
75 } else {
76 /* 右子树高度减少 */
77 switch (bf) {
78 /** 右子树高度减少,左子树变高, 进行左子树平衡，平衡后高度减少继续向上回溯 */
79 case LH: leftBalance(node); break;
80 /** 子树高度无变化，终止回溯 */
81 case EH: node.setBf(LH); break BACK_TRACE;
82 /** 右子树高度减少, 继续向上回溯 */
83 case RH: node.setBf(EH); break;
84 }
85 }
86 cq = cq >> 1;
87 node = next;
88 }
89
90 /* 切断删除的叶子结点 */
91 if (dr == LESS)
92 p.setLeft(null);
93 else
94 p.setRight(null);
95
96 }
标签：node,左子,AvlNode,AVL,child,平衡,null From： https://www.cnblogs.com/chengsh/p/17278375.html