数据结构-平衡二叉树（ALV树）
2019-07-18 本文已影响14人
小怪兽大作战
一、平衡二叉树的定义
首先，平衡二叉树是一棵二叉查找树。此外，他的每一个结点的左子树和右子树的高度之差都小于等于1l
因为平衡二叉树的平衡特性（每一个结点的左子树和右子树的高度之差都小于等于1），它的搜索效率很高log(n)。一颗n个结点的平衡二叉树的高度最大是log(n) + 1。
平衡因子：我们将平衡二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。平衡二叉树上所有结点的平衡因子都只可能是0， 1， -1。
最小不平衡子树：当往平衡二叉树中插入一个结点，造成这棵二叉树不再平衡时，我们称以距离插入结点最近的并且平衡因子绝对值大于1的结点为根的子树叫做最小不平衡子树。
请找出下图中的最小不平衡子树。
图一 - 找出最小不平衡子树
二、平衡二叉树的实现原理
2.1 基本旋转操作
平衡二叉树是在二叉查找树原理的基础上，每次增加或者删除结点后，都应该重新维持树的平衡。
维持树的平衡的基本操作就是旋转。
首先我们看一下最基础的右旋（左旋和右旋道理一样）。
图二 - 简单右旋
我们假设cur为需要右旋的结点，parent = cur.parent，left = cur.left。
那么右旋的伪代码就是
public void rightRotate(BiTNode cur) {
BiTNode parent = cur.parent;
BiTNode left = cur.left;
left.parent = parent; //连接左子结点和父节点
if (parent.left == cur) {
parent.left = left;
} else {
parent.right = left;
}
cur.left = left.right; //使left的右子结点称为cur的左子结点
if (left.right != null) {
left.right.parent = cur;
}
left.right = cur; //使cur称为left的右子结点
cur.parent = left;
}
2.2 两次旋转操作
有些情况下，不能用一次旋转就完成树的平衡。比如如下这种情况。
图三 - 结点和左子结点的平衡因子的正负值不一样
上图中结点中黑色数字表示结点存储的值，红色数字表示结点的平衡因子。结点5的平衡因子是2，因此结点5需要右旋。但是结点5的左子结点结点2的平衡因子是-1，直接右旋依然是不平衡的，如下图所示。
图四 - 结点和左子结点的平衡因子的正负值不一样的情况下一次旋转不能平衡
这时候，我们应该先将结点2左旋，使得他和结点5的平衡因子正负值一样，然后再对结点5右旋。
图五 - 两次旋转达到平衡
2.3 插入一个结点
首先我们这样定义平衡二叉树的结点。他相比二叉查找树结点多了一个平衡因子，用于存储当前结点的平衡状态；还多了一个父节点，因为java不能传指针，因此需要一个父节点引用来进行删除操作。
//平衡二叉树结点
public static class BiTNode {
int val = 0; //结点的值
int bf = 0; //平衡因子
BiTNode left = null; //左子树
BiTNode right = null; //右子树
BiTNode parent = null; //父结点
}
平衡二叉树的插入可以分为两个步骤：1.插入一个结点，2.进行平衡操作。
2.3.1 插入结点
首先我们按照二叉查找树的操作插入一个结点（递归）。
伪代码如下
if (cur == null) { //插入结点
cur = new BiTNode();
cur.val = key;
cur.bf = 0;
cur.parent = parent;
taller = true;
if (parent != null) {
if (parent.val < cur.val) {
parent.right = cur;
} else {
parent.left = cur;
}
} else {
root = cur;
cur.parent = null;
}
else if (cur.val == key) { //已有结点，不需要插入
taller = false;
return false;
} else if (cur.val > key) { //插入到左子树中
insert(cur.left, cur, key)
} else { //插入右子树中
insert(cur.right, cur, key)
}
2.3.2 平衡操作
进行回溯，不断计算插入路径中父节点的平衡因，出现不平衡状况，进行旋转使之重新平衡。
三、代码
package AVLTree;
public class AVLTree {
private BiTNode root = null;
private boolean taller = false;
public void setRoot(int data) {
if (root == null) {
root = new BiTNode();
root.val = data;
} else {
root.val = data;
}
}
/**
* 插入前是平衡状态，插入后可能会是不平衡状态，旋转后是平衡状态
* @param key
* @return
*/
public boolean insert(int key) {
return insert(root, null, key);
}
private boolean insert(BiTNode cur, BiTNode parent, int key) {
if (cur == null) { //插入结点
cur = new BiTNode();
cur.val = key;
cur.bf = 0;
cur.parent = parent;
taller = true;
if (parent != null) {
if (parent.val < cur.val) {
parent.right = cur;
} else {
parent.left = cur;
}
} else {
root = cur;
cur.parent = null;
}
} else { //搜索，插入并平衡
if (cur.val == key) { //已有结点，不需要插入
taller = false;
return false;
} else if (cur.val > key) { //插入到左子树中
if (!insert(cur.left, cur, key)) { //插入，如果已存在，不需要平衡
return false;
}
if (taller) { //如果有增长，需要平衡
if (cur.bf == 0) {
taller = true;
cur.bf = 1;
} else if (cur.bf == 1) {
leftBalance(cur);
taller = false;
} else {
cur.bf = 0;
taller = false;
}
}
} else { //插入右子树中
if (!insert(cur.right, cur, key)) { //插入，如果已存在，不需要平衡
return false;
}
if (taller) { //如果有增长，需要平衡
if (cur.bf == 0) {
taller = true;
cur.bf = -1;
} else if (cur.bf == 1) {
cur.bf = 0;
taller = false;
} else {
rightBalance(cur);
taller = false;
}
}
}
}
return true;
}
/**
* 5 5
* * * * *
* 2 6 3 6
* * * * *
* 1 3 2 4
* * *
* 4 1
* @param node
*/
public void leftBalance(BiTNode node) {
BiTNode leftSon = node.left;
BiTNode leftSonRight = leftSon.right;
switch (leftSon.bf) {
case 1:
node.bf = 0;
rightBalance(node);
break;
case -1:
switch(leftSonRight.bf) {
case 1:
node.bf = -1;
leftSon.bf = 0;
break;
case -1:
node.bf = 0;
leftSon.bf = 1;
break;
case 0:
node.bf = 0;
leftSon.bf = 0;
break;
}
leftSonRight.bf = 0;
leftRotate(leftSon);
rightRotate(node);
break;
}
}
/**
* 4 4 4 4
* * * * * * * * *
* 2 6 2 6 2 7 2 7
* * * * * * * * *
* 5 7 5 8 6 8 5 8
* * * * *
* 8 7 5 6
* @param node
*/
public void rightBalance(BiTNode node) {
BiTNode rightSon = node.left;
BiTNode rightSonLeft = null;
switch (rightSon.bf) {
case -1:
rightSon.bf = 0;
leftRotate(node);
break;
case 1:
switch (rightSonLeft.bf) {
case 0: //不可能存在这种情况
node.bf = 0;
rightSon.bf = 0;
break;
case 1:
node.bf = 0;
rightSon.bf = -1;
break;
case -1:
node.bf = 1;
rightSon.bf = 0;
break;
}
rightSonLeft.bf = 0;
rightRotate(rightSon);
leftRotate(node);
break;
}
}
/**
* 简单右旋
* @param node
*/
public void rightRotate(BiTNode node) {
BiTNode parent = node.parent;
BiTNode leftSon = node.left;
leftSon.parent = parent;
if (parent != null) {
if (parent.left == node) {
parent.left = leftSon;
} else {
parent.right = leftSon;
}
} else {
root = leftSon;
leftSon.parent = null;
}
node.left = leftSon.right;
if (leftSon.right != null) {
leftSon.right.parent = node;
}
leftSon.right = node;
node.parent = leftSon;
}
/**
* 简单左旋
* @param node
*/
public void leftRotate(BiTNode node) {
BiTNode parent = node.parent;
BiTNode rightSon = node.right;
rightSon.parent = parent;
if (parent != null) {
if (parent.left == node) {
parent.left = rightSon;
} else {
parent.right = rightSon;
}
} else {
root = rightSon;
rightSon.parent = null;
}
node.right = rightSon.left;
if (rightSon.left != null) {
rightSon.left.parent = node;
}
rightSon.left = node;
node.parent = rightSon;
}
//平衡二叉树结点
public static class BiTNode {
int val = 0; //结点的值
int bf = 0; //平衡因子
BiTNode left = null; //左子树
BiTNode right = null; //右子树
BiTNode parent = null; //父结点
}
}
