数据结构与算法-AVL树
AVL树(Adelson-Velsky和Landis树)是一种自平衡的二叉搜索树(BST)。在AVL树中,任何节点的两个子树的高度最大差别为1,因此它也被称为高度平衡二叉搜索树。
我们先研究下二叉搜索树的构建
二叉搜索树
树的节点
构建二叉搜索树
创建根(root)节点
创建根节点,即第一个添加的节点。第一个节点的左、右子节点为空(null)。
TreeNode root = new TreeNode(35);
添加节点方法insert()
方法描述
实现添加节点的insert方法。
方法原型: public TreeNode insert(TreeNode root, int data);
参数描述
- TreeNode root : 树的根节点,通过传入根节点将整颗树连接起来。
- int data: 要插入的新节点的数据。
返回类型:
返回类型为节点类型,即返回root节点。
新节点特性
如果根节点不存在,新节点即为根节点。
if(root== null){ return new Node(data); }
新节点创建出来,其左、右子节点为空。
Node newNode = new Node(data);//默认left、right都为空
递归方式插入
假设已经有一个根节点,使用递归的方式添加节点。
public TreeNode insert(TreeNode curr, int data) {
/*
1. 递归终止条件, 当前节点为空,产生新节点直接为当前节点
*/
if (curr == null) return new TreeNode(data);
/*
2. 一般规律:
1)当前节点的左节点不为空,检查左节点
2)当前节点的右节点不为空,检查右节点
*/
if (data < curr.data) {
curr.left = insert(curr.left, data);
}
if (data > curr.data) {
curr.right = insert(curr.right, data);
}
return curr;
}
测试
AVL
AVL节点
AVL树的节点比普通的BST(二叉搜索树)多了一个高度属性,用来记录节点的高度(默认值为1)。
AVL树的高度
AVL树高度从叶节点向上计算,如下图所示,根借点(curr)有两颗子树,左子树的高度-右子树高度 =2
curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));
AVL树的调整方案
获取平衡因子
平衡因子:是根据节点的左右子树的高度来定义的一个参数,实际上是左右子树高度差。
对于一个平衡二叉树其平衡因子只能有三个值: -1, 0, 1
- -1 : 右子树比左子树高 1
- 0: :左子树和右子树一样高
- 1 : 左子树比右子树高 1
/**
* 获取平衡因子,计算左子树和右子树的高度差是否小于或等于1
*
* @param curr
* @return
*/
public int balanceFactor(AVLNode curr) {
if (curr == null) return 0;
return getHeight(curr.left) - getHeight(curr.right);
}
插入节点的四个位置
如果左子树-右子树> 1, 即 左子树太高致使BST树不平衡。在左子树的左侧添加新节点后需要调整。
如果左子树-右子树 <-1, 即右子树太高导致BST不平衡。 在右子树右侧添加新节点后需要调整。
如果在左子树-右子树 > 1, 即左子树太高导致BST树不平衡。在左子树的右侧添加新节点需要调整。
- 如果左子树-右子树 <-1, 即右子树太高导致BST不平衡。在右子树的左侧添加新节点需要调整。
左子树的最左侧添加节点(右旋)
当左子树的的高度- 右子树的高度 >1,且节点添加在最左侧(先完成二叉树的添加节点,当要添加的节点值小于父节点时,左侧添加,同事父节点的.left.height = 1)
右旋: 以当前节点的左子节点为轴进行右旋
- 将当前节点挂在其左子节点(X节点)。
- 将x节点的右子节点挂在当前节点(curr)的左子位置。
- x的左子树不动。
public AVLNode rightRoate(AVLNode curr) {
AVLNode x = curr.left;
AVLNode tmp = x.right;
x.right = curr;
curr.left = tmp;
curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
return x;
}
int bf = balanceFactor(curr);
/*
1. 判断左子树的左侧节点,右旋调整
*/
if (bf > 1 && balanceFactor(curr.left) >= 0) {
return rightRoate(curr);
}
右子树的最右侧节点
左旋: 以当前节点的右子节点为轴进行右旋
- 将当前节点挂在其左子节点(X节点)。
- 将x节点的左子节点挂在当前节点(curr)的右子位置。
- X的右子树不动。
public AVLNode leftRoate(AVLNode curr) {
AVLNode x = curr.right;
AVLNode tmp = x.left;
x.left = curr;
curr.right = tmp;
//更新当前节点高度(调整后当前节点高度改变了)
curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));
//跟新x节点高度
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
return x;
}
if (bf < -1 && balanceFactor(curr.right) <= 0) {
return leftRoate(curr);
}
左子树的右节点
LR型: 先进行左旋调整,然后在进行右旋调整。
/*
* 3. 左子树的最右节点,左旋
*/
if(bf >1 && balanceFactor(curr.left) < 0){
curr.left = leftRoate(curr.left);
return rightRoate(curr);
}
右子树的左侧
RL型: 先进行右旋调整,再进行左旋调整。
/*
* 4. 右子树的最左节点,先右旋再左旋
*/
if (bf < -1 && balanceFactor(curr.right) > 0) {
curr.right = rightRoate(curr.right);
return leftRoate(curr);
}
构建AVL树
定义平衡因子
/**
* 获取平衡因子,计算左子树和右子树的高度差是否小于或等于1
* @param curr
* @return
*/
public int balanceFactor(AVLNode curr) {
if (curr == null) return 0;
return getHeight(curr.left) - getHeight(curr.right);
}
添加节点
添加节点时判断平衡因子,即左子树高度减去右子树高度。以下模拟以(35)为根,逐个添加节点(55),(32),(12),(33),(11)的过程。
高度差的绝对值为1
/*
更新节点的height
*/
curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));
/*
计算平衡因子
*/
int bf = balanceFactor(curr);
高度差为0
插入数据32后,高度差为0(平衡因子),不用调整。
添加数据12
添加数据33
添加10
平衡因子大于1为左侧大,右边小
平衡因子小于-1 为右侧大,左侧小
判断左侧位置的左侧
要添加的节点在左侧的左节点
- 判断平衡因子是否大于1 : 大于1 表示左子树的高度大于右子树高度1
- 判断是添加左子节点还是右子节点: 检查左子节点的高度如果大于0则是在左子节点(在添加节点过程中使用BST与父节点判断大小,如果小于父节点则挂在左子节点位置,那么左子节点的高度就会>0)
- 此处要使用右旋(找到合适的点向右旋转)
/*
计算平衡因子
*/
int bf = balanceFactor(curr);
int leftForLeftChild = getHeight(curr.left);
/*
1. 判断左子树的左侧节点,右旋调整
*/
if (bf > 1 && leftForLeftChild > 0) {
return rightRoate(curr);
}
public AVLNode rightRoate(AVLNode curr) {
AVLNode x = curr.left;
AVLNode y = x.right;
x.right = curr;
curr.left = y;
curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
return x;
}