一、概念
平衡二叉树是一种 二叉排序树 ，其中每个结点的左子树和右子树的高度差至多等于1
平衡因子：平衡二叉树是在二叉查查找树的基础上进行构建了，为了维持平衡二叉树的平衡，那么就需要一种机制来判断平衡二叉树是否是平衡的。这种机制就叫做平衡因子。平衡二叉树上某个结点的左子树深度减去右子树深度的值，就称为此结点的平衡因子。
最小不平衡树：距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡树。
特点:
- 平衡二叉树是一种二叉查找树
- 每个结点的左子树的高度减去右子树的高度的绝对值不超过1
- 空树和左右子树都是平衡二叉树
- 相比红黑树，平衡二叉树比较适用于没有删除的情况
平衡二叉树的每个结点都会维持一个值，这个值就是平衡因子，这个平衡因子就是这个结点的左子树的高度减去右子树的高度得到的值。如果这个平衡因子的值的绝对值大于1了，说明这个树就不平衡了，那么就需要调整树的结构了。
二、实践
1、树的表示形式：孩子表示法
public class Node<E extends Comparable<E>>{
E element;
int balance; //平衡因子
Node<E> parent;
Node<E> left;
Node<E> right;
public Node(E element, Node<E> parent){
this.element = element;
this.parent = parent;
}
}
2、左旋
坐旋转
代码：
/**
* 左旋
* @param x 把 x 结点左旋转
*/
public void leftRotate(Node<E> x){
if(x != null){
Node<E> y = x.right;
x.right = y.left;
if(y.left != null){
y.left.parent = x;
}
y.parent = x.parent;
if(x.parent == null){
root = y;
}else if(x.parent.left == x){
x.parent.left = y;
}else if(x.parent.right == y){
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
}
3、右旋
右旋转
代码：
/**
* 右旋转
* @param x 把 x 结点右旋转
*/
public void rightRotate(Node<E> x){
if(x != null){
Node<E> y = x.left;
x.left = y.right;
if(y.right != null){
y.right.parent = x;
}
y.parent = x.parent;
if(x.parent == null){
root = y;
}else if(x.parent.left == x){
x.parent.left = y;
}else if(x.parent.right == y){
x.parent.right = y;
}
y.right = x;
x.parent = y;
}
}
3、右平衡操作
image.png
代码：
/**
* 右平衡操作，即结点t的不平衡是因为右子树过深
* @param t 为最小不平衡子树的根节点
*/
public void rightBalalce(Node<E> t){
if(t != null){
Node<E> tr = t.right;
switch (tr.balance){
case RH: //如果新的结点插入到t的右孩子的右子树中，则直接进行左旋操作即可
leftRotate(t);
t.balance = EH;
tr.balance = EH;
break;
case LH: //如果新的结点插入到t的右孩子的左子树中，则需要进行分情况讨论
Node<E> trl = tr.left;
switch (trl.balance){
case LH: //当t的右孩子的左子树根节点的balance = LEFT_HIGH
t.balance = EH;
tr.balance = RH;
trl.balance = EH;
break;
case RH: //当t的右孩子的左子树根节点的balance = RIGHT_HIGH
t.balance = LH;
tr.balance = EH;
trl.balance = EH;
break;
case EH: //当t的右孩子的左子树根节点的balance = EQUAL_HIGH
t.balance = EH;
tr.balance = EH;
trl.balance = EH;
break;
}
/**
* 切记，先执行平衡因子的计算，之后再进行，旋转操作。否则旋转之后，之前的结构发生了变化。
*/
rightRotate(tr);
leftRotate(t);
break;
}
}
}
4、左平衡操作（参照右平衡）
/**
* 左平衡操作：即结点t的不平衡是因为左子树过深
* @param t 为最小不平衡子树的根节点
*/
public void leftBalance(Node<E> t){
if(t != null){
Node<E> tl = t.left;
switch (tl.balance){
case LH: //如果新的结点插入到t的左孩子的左子树中，则直接进行右旋操作即可
rightRotate(t);
t.balance = EH;
tl.balance = EH;
break;
case RH: //如果新的结点插入到t的左孩子的右子树中，则需要进行分情况讨论
Node<E> tlr = tl.right;
switch (tlr.balance){
case LH: //当t的左孩子的右子树根节点的balance = LEFT_HIGH
t.balance = RH;
tl.balance = EH;
tlr.balance = EH;
break;
case RH: //当t的左孩子的右子树根节点的balance = RIGHT_HIGH
t.balance = EH;
tl.balance = LH;
tlr.balance = EH;
break;
case EH: //当t的左孩子的右子树根节点的balance = EQUAL_HIGH 【举例： 2 0 1 三个数的时候】
t.balance = EH;
tl.balance = EH;
tlr.balance = EH;
break;
}
/**
* 切记，先执行平衡因子的计算，之后再进行，旋转操作。否则旋转之后，之前的结构发生了变化。
*/
leftRotate(tl);
rightRotate(t);
break;
}
}
}
5、插入节点
/**
* 插入节点
* @param element 元素内容
*/
public boolean insertElement(E element){
Node t = root;
if (t == null){
root = new Node<>(element, null);
size = 1;
root.balance = 0;
return true;
}else{
//开始找到要插入的位置
int cmp;
Node parent;
do {
parent = t;
cmp = element.compareTo((E) t.element);
if(cmp < 0){
t = t.left;
}else if(cmp > 0){
t = t.right;
}else{
return false;
}
}while (t != null);
//开始插入位置
Node child = new Node(element, parent);
if(cmp < 0){
parent.left = child;
}else if(cmp > 0){
parent.right = child;
}
//检查平衡，回溯查找
while (parent != null){
cmp = element.compareTo((E) parent.element);
if(cmp < 0){
parent.balance++;
}else{
parent.balance--;
}
if(parent.balance == 0){ //如果插入后还是平衡树，不用调整
break;
}
if(parent.balance == 2 || parent.balance == -2){
//出现了平衡问题，需要调整
fixAfterInsertion(parent);
break;
}else{
parent = parent.parent;
}
}
}
size++;
return true;
}
// parent 为最小不平衡子树的根节点
private void fixAfterInsertion(Node parent) {
if(parent.balance == 2){
leftBalance(parent);
}
if (parent.balance == -2){
rightRotate(parent);
}
}
三、完整代码
/**
AVLBTree 平衡二叉树
*/
public class AVLBTree<E extends Comparable<E>> {
Node<E> root;
int size;
private static final int LH = 1;
private static final int RH = -1;
private static final int EH = 0;
/**
* 左旋
* @param x 把 x 结点左旋转
*/
public void leftRotate(Node<E> x){
if(x != null){
Node<E> y = x.right;
x.right = y.left;
if(y.left != null){
y.left.parent = x;
}
y.parent = x.parent;
if(x.parent == null){
root = y;
}else if(x.parent.left == x){
x.parent.left = y;
}else if(x.parent.right == y){
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
}
/**
* 右旋转
* @param x 把 x 结点右旋转
*/
public void rightRotate(Node<E> x){
if(x != null){
Node<E> y = x.left;
x.left = y.right;
if(y.right != null){
y.right.parent = x;
}
y.parent = x.parent;
if(x.parent == null){
root = y;
}else if(x.parent.left == x){
x.parent.left = y;
}else if(x.parent.right == y){
x.parent.right = y;
}
y.right = x;
x.parent = y;
}
}
/**
* 左平衡操作：即结点t的不平衡是因为左子树过深
* @param t 为最小不平衡子树的根节点
*/
public void leftBalance(Node<E> t){
if(t != null){
Node<E> tl = t.left;
switch (tl.balance){
case LH: //如果新的结点插入到t的左孩子的左子树中，则直接进行右旋操作即可
rightRotate(t);
t.balance = EH;
tl.balance = EH;
break;
case RH: //如果新的结点插入到t的左孩子的右子树中，则需要进行分情况讨论
Node<E> tlr = tl.right;
switch (tlr.balance){
case LH: //当t的左孩子的右子树根节点的balance = LEFT_HIGH
t.balance = RH;
tl.balance = EH;
tlr.balance = EH;
break;
case RH: //当t的左孩子的右子树根节点的balance = RIGHT_HIGH
t.balance = EH;
tl.balance = LH;
tlr.balance = EH;
break;
case EH: //当t的左孩子的右子树根节点的balance = EQUAL_HIGH 【举例： 2 0 1 三个数的时候】
t.balance = EH;
tl.balance = EH;
tlr.balance = EH;
break;
}
/**
* 切记，先执行平衡因子的计算，之后再进行，旋转操作。否则旋转之后，之前的结构发生了变化。
*/
leftRotate(tl);
rightRotate(t);
break;
}
}
}
/**
* 右平衡操作，即结点t的不平衡是因为右子树过深
* @param t 为最小不平衡子树的根节点
*/
public void rightBalalce(Node<E> t){
if(t != null){
Node<E> tr = t.right;
switch (tr.balance){
case RH: //如果新的结点插入到t的右孩子的右子树中，则直接进行左旋操作即可
leftRotate(t);
t.balance = EH;
tr.balance = EH;
break;
case LH: //如果新的结点插入到t的右孩子的左子树中，则需要进行分情况讨论
Node<E> trl = tr.left;
switch (trl.balance){
case LH: //当t的右孩子的左子树根节点的balance = LEFT_HIGH
t.balance = EH;
tr.balance = RH;
trl.balance = EH;
break;
case RH: //当t的右孩子的左子树根节点的balance = RIGHT_HIGH
t.balance = LH;
tr.balance = EH;
trl.balance = EH;
break;
case EH: //当t的右孩子的左子树根节点的balance = EQUAL_HIGH
t.balance = EH;
tr.balance = EH;
trl.balance = EH;
break;
}
/**
* 切记，先执行平衡因子的计算，之后再进行，旋转操作。否则旋转之后，之前的结构发生了变化。
*/
rightRotate(tr);
leftRotate(t);
break;
}
}
}
/**
* 插入节点
* @param element 元素内容
*/
public boolean insertElement(E element){
Node t = root;
if (t == null){
root = new Node<>(element, null);
size = 1;
root.balance = 0;
return true;
}else{
//开始找到要插入的位置
int cmp;
Node parent;
do {
parent = t;
cmp = element.compareTo((E) t.element);
if(cmp < 0){
t = t.left;
}else if(cmp > 0){
t = t.right;
}else{
return false;
}
}while (t != null);
//开始插入位置
Node child = new Node(element, parent);
if(cmp < 0){
parent.left = child;
}else if(cmp > 0){
parent.right = child;
}
//检查平衡，回溯查找
while (parent != null){
cmp = element.compareTo((E) parent.element);
if(cmp < 0){
parent.balance++;
}else{
parent.balance--;
}
if(parent.balance == 0){ //如果插入后还是平衡树，不用调整
break;
}
if(parent.balance == 2 || parent.balance == -2){
//出现了平衡问题，需要调整
fixAfterInsertion(parent);
break;
}else{
parent = parent.parent;
}
}
}
size++;
return true;
}
private void fixAfterInsertion(Node parent) {
if(parent.balance == 2){
leftBalance(parent);
}
if (parent.balance == -2){
rightRotate(parent);
}
}
/**
层级遍历
*/
public void showAVL(Node root) {
LinkedList<Node> list = new LinkedList<Node>();
list.offer(root);//队列放入
while (!list.isEmpty()) {
Node node = list.pop();//队列的取出
System.out.println(node.element);
if (node.left != null) {
list.offer(node.left);
}
if (node.right != null) {
list.offer(node.right);
}
}
}
public class Node<E extends Comparable<E>>{
E element;
int balance; //平衡因子
Node<E> parent;
Node<E> left;
Node<E> right;
public Node(E element, Node<E> parent){
this.element = element;
this.parent = parent;
}
}
}
我们详细的介绍到平衡二叉查找树的算法以及代码实践，我们知道平衡二叉查找树是一个高度平衡的二叉树，也就是说树的高度差不能大于1，在删除的时候，可能需要多次调整，也就是左旋转、右旋转操作，在树的深度很大的情况下，删除效率会非常低，如何提高这种效率？红黑树由此诞生了，下一次讨论红黑树
网友评论