平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，查找时间上稳定了很多。
二叉树不平衡的情景，及其解决方案
这里为了避免一直看概念比较”干“，会结合代码进行说明
节点的定义
public class AvlTree<T extends Comparable<T>> {
/**
* 树的根节点
*/
private AvlNode root;
/**
* 树的高度
*/
private int height;
private class AvlNode {
/**
* 节点值
*/
private T data;
/**
* 当前节点所在树的高度
*/
int height;
/**
* 左右子树
*/
private AvlNode left, right;
AvlNode(T data) {
left = right = null;
this.data = data;
this.height = 0;
}
}
}
1. 左左
左旋
节点6的左子树高度为3，右子树高度为1，而且6节点的任意子树的左子树的高度都大于等于右子树的高度，这种形态的二叉树直接进行左旋即可。
编码实现
/**
* 左旋
* 4 2
* / \ / \
* 2 5 ---> 1 4
* / \ / / \
* 1 3 0 3 5
* /
* 0
*
* @param avlNode 当前根节点
* @return 左旋后的当前根节点
*/
private AvlNode ll(AvlNode avlNode) {
if (avlNode==null) {
return null;
}
// 获取当前传入二叉树根节点的左儿子
AvlNode leftNode = avlNode.left;
// 左旋
avlNode.left = leftNode.right;
leftNode.right = avlNode;
// 重新计算高度
leftNode.height = Integer.max(this.height(leftNode.left), this.height(leftNode.right))+1;
avlNode.height = Integer.max(this.height(avlNode), this.height(avlNode))+1;
// 此时当前二叉树的根节点为刚刚的左儿子
return leftNode;
}
2. 右右
右旋
节点2的右子树的高度为3，左子树的高度为1，而且2节点的任意右子树的高度都大于等于左子树，这种形态的二叉树直接进行右旋即可。
编码实现
/**
* 右旋
* 2 4
* / \ / \
* 1 4 2 5
* / \ ---> / \ \
* 3 5 1 3 6
* \
* 6
*
* @param avlNode 当前根节点
* @return 右旋后的当前根节点
*/
private AvlNode rr(AvlNode avlNode) {
if (avlNode==null) {
return null;
}
// 获取当前传入二叉树根节点的右儿子
AvlNode rightNode = avlNode.right;
// 右旋
avlNode.right = rightNode.left;
rightNode.left = avlNode;
// 重新计算高度
rightNode.height = Integer.max(this.height(rightNode.left), this.height(rightNode.right))+1;
avlNode.height = Integer.max(this.height(avlNode.left), this.height(avlNode.right))+1;
// 此时当前二叉树的根节点为刚刚的右儿子
return rightNode;
}
2. 左右
左右
节点6的左子树的高度为2，右子树的高度为1，但是不具备任意左子树的高度都大于等于右子树，即，节点2的左子树的高度为1，但是右子树的高度为2，这种情况首先需要将节点2进行右旋，转换成”左左“形式，然后在对节点6进行左旋，最终达到平衡。
编码实现
/**
* 左右模式，先右旋，然后左旋
* 6 6 4
* / \ / \ / \
* 2 7 4 7 2 6
* / \ ---> / \ ---> / \ / \
* 1 4 2 5 1 3 5 7
* / \ / \
* 3 5 1 3
* @param avlNode 当前根节点
* @return 旋转后的当前根节点
*/
private AvlNode lr(AvlNode avlNode){
if(avlNode==null){
return null;
}
avlNode.left = rr(avlNode.left);
return rr(avlNode);
}
3. 右左
右左
节点2的左子树的高度为1，右子树的高度为3，但是不具备任意右子树的高度都大于等于左子树的高度情况，即，节点6的左子树高度为2，右子树的高度为1，这种情况首先要将节点6进行左旋，转换成”右右“形式，然后对节点2进行右旋，最终达到平衡。
编码实现
/**
* 右左模式，先左旋，然后右旋
* 2 2 4
* / \ / \ / \
* 1 6 1 4 2 6
* / \ ---> / \ ---> / \ / \
* 4 7 3 6 1 3 5 7
* / \ / \
* 3 5 5 7
*
* @param avlNode 当前根节点
* @return 旋转后的根节点
*/
private AvlNode rl(AvlNode avlNode){
if(avlNode==null){
return null;
}
avlNode.right = ll(avlNode.right);
return rr(avlNode);
}
整体创建二叉树的过程就是这样的
- 插入新的节点
- 调整数的平衡
- 重新计算节点高度
/**
* 插入节点
*
* @param data 节点值
*/
public void insert(T data) {
root = insertCore(data, root);
height = root.height;
}
/**
* 插入节点核心逻辑
*
* @param data 数据
* @param root 当前节点根节点
* @return 根节点
*/
private AvlNode insertCore(T data, AvlNode root) {
if (root == null) {
return new AvlNode(data);
}
if (root.data.compareTo(data) > 0) {
root.left = insertCore(data, root.left);
// 是否需要平衡
if ((height(root.left) - height(root.right) > 1)) {
if (height(root.left.left)>height(root.left.right)) {
// LL情况
root = ll(root);
} else {
// LR情况
root = lr(root);
}
}
} else if (root.data.compareTo(data) < 0) {
root.right = insertCore(data, root.right);
// 是否需要平衡
if ((height(root.right) - height(root.left) > 1)) {
if (height(root.right.right)>height(root.right.left)) {
// RR情况
root = rr(root);
} else {
// RL情况
root = rl(root);
}
}
}
// 重新计算节点高度
if(root != null){
root.height = Integer.max(height(root.left), height(root.right)) + 1;
}
// 节点和当前root节点相等，直接返回
return root;
}
删除节点
删除节点的方式有很多种，这里只是其中的一种
同插入操作一样，删除结点时也有可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整。
删除分为以下几种情况：
- 首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：
- 要删除的节点是当前根节点T。
- 如果左右子树都非空。在高度较大的子树中实施删除操作。
分两种情况：- 左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。
- 左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。
- 如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。
- 如果左右子树都非空。在高度较大的子树中实施删除操作。
- 要删除的节点元素值小于当前根节点T值，在左子树中进行删除。递归调用，在左子树中实施删除。否则在右子树中递归调用实施删除。
- 删除节点后，需要判断当前根节点是否仍然满足平衡条件，如果满足平衡条件，只需要更新当前根节点T的高度信息。否则，需要进行旋转调整。
编码实现
/**
* 找到树中最小的值
*
* @param root 树的根节点
* @return min avlNode
*/
private AvlNode findMin(AvlNode root) {
return (root == null || root.left == null) ? root : findMin(root.left);
}
/**
* 找到树中最大的值
*
* @param root 树的根节点
* @return max avlNode
*/
private AvlNode finMax(AvlNode root) {
return (root == null || root.right == null) ? root : finMax(root.right);
}
/**
* 删除节点
*
* @param data 节点值
*/
public void delete(T data) {
root = deleteCore(data, root);
height = root!=null?root.height:0;
}
/**
* 删除节点核心逻辑
*
* @param data 数据
* @param root 当前节点根节点
* @return 根节点
*/
private AvlNode deleteCore(T data, AvlNode root) {
if (root == null) {
return null;
}
if (root.data.compareTo(data) > 0) {
// 根节点比删除的节点大，删除的节点在左子树
root.left = deleteCore(data, root.left);
// 平衡树
if (height(root.right) - height(root.left) > 1) {
// 判断平衡模式
if (height(root.right.left) > height(root.right.right)) {
// RL模式
root = rl(root);
} else {
// RR模式
root = rr(root);
}
}
} else if (root.data.compareTo(data) < 0) {
// 根节点比删除的节点小，删除的单节点在右子树
root.right = deleteCore(data, root.right);
// 平衡树
if (height(root.left) - height(root.right) > 1) {
// 判断平衡模式
if (height(root.left.right) > height(root.left.left)) {
// LR模式
root = lr(root);
} else {
// LL模式
root = ll(root);
}
}
} else {
// 当前的根节点即为需要删除的节点
if (root.left != null && root.right != null) {
// 左右子树都非空，判断左右子树的高度，选择高度较高的一个
if (root.left.height > root.right.height) {
// 左子树较高，那么从左子树中找到值最大的节点，跟要删除的节点的值(当前的根节点)进行替换，然后删除该节点
AvlNode maxNode = finMax(root.left);
root.data = maxNode.data;
// 删除左子树中值最大的节点
root.left = deleteCore(maxNode.data, root.left);
} else {
// 右子树较高，那么从右子树中找到值最小的节点，跟要删除的节点的值(当前的根节点)进行替换，然后删除该节点
AvlNode minNode = findMin(root.right);
root.data = minNode.data;
// 删除右子树中值最小的节点
root.right = deleteCore(minNode.data, root.right);
}
} else {
// 选择任意一个非空节点作为根节点返回
root = root.left != null ? root.left : root.right;
}
}
// 重新计算节点的高度
if(root!=null){
root.height = Integer.max(height(root.left), height(root.right)) + 1;
}
return root;
}
查找
查找跟普通的二叉树查找相同，就不墨迹概念了，直接上代码
/**
* 判断节点是否在二叉树中
*
* @param data data
* @return bool
*/
public boolean contains(T data){
AvlNode p = root;
while (p!=null&&p.data!=data){
if(p.data.compareTo(data)>0){
p=p.left;
}else {
p=p.right;
}
}
return p!=null&&p.data.compareTo(data)==0;
}
网友评论