目录

1.概念

2AVL树

树的旋转

1.左旋

2.右旋

3.左双旋转

4.右双旋转

树的平衡

---

1.概念

在介绍自平衡二叉查找树之前，先说一下二叉树，这里就简单列一下概念来自《数据结构和算法分析》

二叉树：是一棵树，每个节点不能多于两个儿子

二叉查找树：树中所有项都可以被排序，即树中每个节点x，它的左子树所有项都小于x，它的右子树所有项都大于x。

自平衡的二叉查找树：根据某些平衡条件保证树的深度（avl和红黑树）

2AVL树

AVL树严格保障树的高度达到某种条件：左子树和右子树高度相差不能大于1。但是每次插入或者删除的时候都有可能破坏平衡条件，解决的方法是树的旋转。

树的旋转

1.左旋

如图，对k1进行左旋，即将k1变成左节点，k2为根，k2的左节点变成k1的右节点

代码示例：

private AvlNode leftRate(AvlNode k1) { AvlNode k2 = k1.right; k1.right = k2.left; k2.left = k1; k2.height = Math.max(k1.height, height(k2.right))+1; k1.height = Math.max(height(k1.left), height(k1.right)) + 1; return k2; }

2.右旋

如图：对k2进行右旋，即将k2变为右节点，k1为根，k1的右节点变为k2的左节点。

代码示例：

private AvlNode rightRate(AvlNode k2) { AvlNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k1.height = Math.max(k2.height, height(k1.left))+1; k2.height = Math.max(height(k2.left), height(k2.right)) + 1; return k2; }

3.左双旋转

先对k3进行右旋，在对k1进行左旋。

代码示例

private AvlNode leftDoubleRate(AvlNode k1) { k1.right = rightRate(k1.right); return leftRate(k1); }

4.右双旋转

对k1进行左旋，然后对k3进行右旋。

代码示例：

private AvlNode rightDoubleRate(AvlNode k3) { k3.left = rightRate(k3.left); return leftRate(k3); }

树的平衡

了解了树的旋转，我们讨论什么情况下，如何进行平衡

插入

在插入之后，破坏了AVL平衡条件，我们要平衡这棵树，我们将不满足平衡条件的节点叫x，呢么有四种情况会破坏：

1.向x的左儿子的左子树进行插入.

对x进行右旋

2.向x的左儿子的右子树进行插入.

对x右双旋转

3.向x的右儿子的左子树进行插入.

对x左双旋转

4.向x的右儿子的右子树进行插入.

对x左旋

代码示例：

//向t插入x private AvlNode insert(int x, AvlNode t) { //如果t为空 if (t == null) { return new AvlNode(x, null, null); } //如果x小于节点，将x插入至左节点 if (x < t.element) { t.left = insert(x, t.left); } else {//否则插入至右节点 t.right = insert(x, t.right); } //开始平衡 return balance(t); } //左右节点高度相差的最大值，大于此值则表示不平衡 private final static int ALLOWED_IMBALANCE = 1; private AvlNode balance(AvlNode t) { if (t == null) { return t; } if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE) {//左侧高失去平衡 if (height(t.left.left) > height(t.right)) {//左左 右旋 t = rightRate(t); }else{//左右 右双旋 t = rightDoubleRate(t); } }else{//右侧高 if (height(t.left.left) > height(t.right)) {//右左 左双旋 t = leftDoubleRate(t); }else{//右右 左旋 t = leftRate(t); } } t.height = Math.max(height(t.left), height(t.right)) + 1; return t; }

删除

private AvlNode remove(int x, AvlNode t) { //如果t为空 什么都不做 if (t == null) { return t; } //如果x小于节点，将x插入至左节点 if (x < t.element) { t.left = remove(x, t.left); } else if (x > t.element) {//否则插入至右节点 t.right = remove(x, t.right); } else if (t.left != null && t.right != null) {//如果有两个孩子 将右子树最小值代替x删除右子树最小值 t.element = findMin(t.right); t.right = remove(x, t.right); } else { t = (t.left == null) ? t.left : t.right; } return balance(t); }