平衡二叉树
基本介绍

平衡二叉树:也叫平衡二叉搜索树(Self-balancing binary search tree),又被称为AVL树, 可以保证查询效率较高。
特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
一棵AVL树有如下必要条件:
- 条件一:它必须是二叉排序树。
- 条件二:每个节点的左子树和右子树的高度差至多为1。


AVL树的平衡调整
左旋转:

问题:当插入8 时,rightHeight() - leftHeight() > 1 成立,此时,不再是一颗avl树了.
怎么处理–进行左旋转:
- 创建一个新的节点 newNode ,值等于当前根节点的值
- 把新节点的左子树设置了当前节点的左子树
newNode.left = left
- 把新节点的右子树设置为当前节点的右子树的左子树
newNode.right = right.left;
- 把当前节点的值换为右子节点的值
value = right.value;
- 把当前节点的右子树设置成右子树的右子树
right = right.right;
- 把当前节点的左子树设置为新节点
left = newNode;
右旋转:

问题:当插入6 时,leftHeight() - rightHeight() > 1 成立,此时,不再是一颗avl树了.
怎么处理–进行右旋转
- 创建一个新的节点 newNode ,值等于当前根节点的值
- 把新节点的右子树设置了当前节点的右子树
newNode.right = right
- 把新节点的左子树设置为当前节点的左子树的右子树
newNode.left = left.right;
- 把当前节点的值换为左子节点的值
value = left.value;
- 把当前节点的左子树设置成左子树的左子树
left = left.left;
- 把当前节点的右子树设置为新节点
right = newNode;
双旋转:

问题: 当插入9 时,leftHeight() - rightHeight() > 1 ,此时右旋转进行平衡,发现右旋转后还不是一颗avl树
在满足右旋转条件时,要判断:
- 如果左子树的右子树高度大于左子树的左子树高度时
- 就对当前根节点的左子树,先进行左旋转
- 然后再对当前根节点进行右旋转即可
- 否则,直接对当前节点(根节点)进行右旋转即可.

同理,在满足左旋转条件时,要判断:
- 如果右子树的左子树高度大于右子树的右子树高度时
- 就对当前根节点的右子树,先进行右旋转
- 然后再对当前根节点进行左旋转即可
- 否则,直接对当前节点(根节点)进行左旋转即可.
判断树的高度的代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public int leftHeight() { if (left == null) { return 0; } return left.height(); }
public int rightHeight() { if (right == null) { return 0; } return right.height(); }
public int height() { return Math.max(this.left == null ? 0 : left.height(), this.right == null ? 0 : right.height()) + 1; }
|
左旋转和右旋转的代码实现
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
| private void leftRotate() { Node newNode = new Node(value); newNode.left = left; newNode.right = right.left; value = right.value; right = right.right; left = newNode; }
private void rightRotate() { Node newNode = new Node(value); newNode.right = right; newNode.left = left.right; value = left.value; left = left.left; right = newNode; }
|
添加节点时的平衡代码实现
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
| public void add(Node node) { if (node == null) { return; } if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else { if (this.right == null) { this.right = node; } else { this.right.add(node); } }
if (rightHeight() - leftHeight() > 1) { if (right != null && right.leftHeight() > right.rightHeight()) { right.rightRotate(); leftRotate(); } else { leftRotate(); } return; }
if (leftHeight() - rightHeight() > 1) { if (left != null && left.rightHeight() > left.leftHeight()) { left.leftRotate(); rightRotate(); } else { rightRotate(); } } }
|