AVL树
2020-04-24 本文已影响0人
GoofyWang
介绍
AVL树是最常见的自平衡二叉搜索树了。关于二叉搜索树大致的描述如下：
- 每个节点只有左右两个子节点
- 每个节点的左子节点的值小于该节点值，每个节点的右子节点的值大于该节点的值
AVL树是一颗平衡二叉树，所谓平衡的概念如下：
二叉搜索树中任何一个节点，左子树的高度与右子树的高度差小于等于1。子树的高度定义为子树的左右子树中高度大的值。
当一个二叉搜索树为平衡二叉树的时候，查询效率是很高的，时间复杂度为O(lgn)。但如果对这个树做了多次的插入与删除操作后，这个树就很可能失去了平衡，变成了一个链表结构。
AVL树插入与删除节点后都需要重新计算当前节点是否平衡，如果不平衡，则通过旋转来使节点保持平衡。
旋转
旋转有四种情况，左旋转两种，右旋转两种，其中左旋转与右旋转是镜对称动作，我们只看左旋转就好。参考如下两张图，应该可以很清晰的说明两种左旋转的过程。注意：旋转前后，颜色相同的节点代表了值相同的节点。 右旋的操作，可以自己去画一下。
左旋一
左旋一
左旋二
左旋二
关于删除
突然发现，二叉查找树中节点的删除其实也不是一个特别简单的过程。所以单开一个小节来描述一下。
通用方法
当需要删除一个节点的时候我们需要的操作如下：
- 持有该节点的父节点与子节点
- 断开父节点到该节点的连接，以及该节点到子节点的连接
- 如果该节点没有右子节点，则将该节点的左子节点设置为父节点的左子节点，结束
- 如果该节点有右子节点，则需要从右子节点中找到最小值的节点，然后做如下操作
4.1 如果最小值节点就是当前节点的右子节点，则将最小值节点设置为父节点的左子节点，然后把原左子节点设置为最小值节点的左子节点，结束
4.2 如果最小值节点不是当前节点的右子节点，则需要在右子节点的子树中删除最小值节点，然后创建新的最小时节点，将新的最小时节点设置为父节点的左子节点，然后把原左子节点设置为新的最小值节点的左子节点，右子节点为新的最小值节点的右子节点，结束。
看图
红色的节点表示删除后需要重新计算高度并判断是否需要旋转的节点
步骤3的删除操作
步骤3的场景
步骤4.1的删除操作
步骤4.1的场景
步骤4.2的删除操作
步骤4.2的场景
这个图里，oldRight到minNode的虚线表示的意思是minNode不一定是oldRight的直接左子节点，有可能是很多层之后的一个子节点。但肯定在oldRight为根的树中，它是最左边的。
Talk is cheap
/**
* AVL树节点类
* 节点中持有的对象的类必须实现Comparable接口
* 此类中封装了计算子树高度，计算自身节点高度，判断是否需要旋转，以及旋转实现的方法 作为树节点的基础功能
*
* @author goofy.wang
*/
public class AVLNode<T extends Comparable> implements Comparable<AVLNode<T>>{
private T value;
private int leftDepth;
private int rightDepth;
private AVLNode<T> left;
private AVLNode<T> right;
public AVLNode(T value) {
this(value, null, null);
}
public AVLNode(T value, AVLNode<T> left, AVLNode<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
public AVLNode<T> getLeft() {
return this.left;
}
public void setLeft(AVLNode<T> left) {
this.left = left;
}
public AVLNode<T> getRight() {
return this.right;
}
public void setRight(AVLNode<T> right) {
this.right = right;
}
public void setValue(T value){
this.value = value;
}
public T getValue(){
return this.value;
}
public boolean hasLeft(){
return this.left != null;
}
public boolean hasRight(){
return this.right != null;
}
/**
* 获取当前节点深度的方法
* @return
*/
public int getDepth(){
int maxSubDepth = this.leftDepth > this.rightDepth ? this.leftDepth : this.rightDepth;
return maxSubDepth + 1;
}
/**
* 计算左右子树深度的方法
*/
public void calculateDepth(){
this.leftDepth = this.left == null ? 0 : this.left.getDepth();
this.rightDepth = this.right == null ? 0 : this.right.getDepth();
}
/**
* 判断是否需要旋转
* @return
*/
public boolean needRotate(){
return Math.abs(this.leftDepth - this.rightDepth) > 1;
}
/**
* 旋转方法，内部判断需要左旋还是右旋
*/
public void rotate(){
if(this.leftDepth > this.rightDepth){
this.leftRotateToRight();
}else{
this.rightRotateToLeft();
}
this.calculateDepth();
}
/**
* 左旋方法
* if 实现旋转一
* else 实现旋转二
*/
private void leftRotateToRight(){
AVLNode<T> leftRight = this.left.getRight();
T currentValue = this.getValue();
if(leftRight == null){
T leftValue = this.left.getValue();
AVLNode<T> newRight = new AVLNode<T>(currentValue, null, this.getRight());
newRight.calculateDepth();
this.setValue(leftValue);
this.setRight(newRight);
this.setLeft(this.getLeft().getLeft());
}else{
T leftRightValue = leftRight.getValue();
AVLNode<T> leftRightLeft = leftRight.getLeft();
AVLNode<T> leftRightRight = leftRight.getRight();
AVLNode<T> newRight = new AVLNode<T>(currentValue, leftRightRight, this.getRight());
newRight.calculateDepth();
this.setValue(leftRightValue);
this.setRight(newRight);
this.left.setRight(leftRightLeft);
this.left.calculateDepth();
}
}
/**
* 右旋方法，与左旋镜对称
*/
private void rightRotateToLeft(){
AVLNode<T> rightLeft = this.right.getLeft();
T currentValue = this.getValue();
if(rightLeft == null){
T rightValue = this.right.getValue();
AVLNode<T> newLeft = new AVLNode<T>(currentValue, this.left, null);
newLeft.calculateDepth();
this.setValue(rightValue);
this.setLeft(newLeft);
this.setRight(this.right.getRight());
}else{
T rightLeftValue = rightLeft.getValue();
AVLNode<T> rightLeftLeft = rightLeft.getLeft();
AVLNode<T> rightLeftRight = rightLeft.getRight();
AVLNode<T> newLeft = new AVLNode<T>(currentValue, this.left, rightLeftLeft);
newLeft.calculateDepth();
this.setValue(rightLeftValue);
this.setLeft(newLeft);
this.right.setLeft(rightLeftRight);
this.right.calculateDepth();
}
}
/**
* 比较方法
* @param o
* @return
*/
@Override
public int compareTo(AVLNode<T> o) {
return this.value.compareTo(o.getValue());
}
}
/**
* AVL树类
* 此类用于组织AVLNode节点，使得这些节点以正确的平衡二叉树方式关联在一起
* 并在添加与删除元素后，控制树节点完成高度计算，平衡性判断，以及旋转等行为
*
* @author goofy.wang
*/
public class AVLTree<T extends Comparable> {
private AVLNode<T> root;
/**
* 添加节点的方法，如果值在树中存在相等的节点，则将此节点中的值替换为当前值
* @param nodeValue
*/
public void append(T nodeValue){
AVLNode<T> newNode = new AVLNode<T>(nodeValue);
if(this.root == null){
this.root = newNode;
}else{
this.innerAppend(this.root, newNode);
}
}
/**
* 判断树中是否存在某个值对象的方法
* @param nodeValue
* @return
*/
public boolean contains(T nodeValue){
if(this.root == null){
return false;
}
AVLNode<T> condition = new AVLNode<T>(nodeValue);
if(root.compareTo(condition) == 0){
return true;
}else{
return this.containsInChilren(this.root, condition);
}
}
/**
* 从树中删除某个值对象的方法
* @param nodeValue
* @return 如果存在该元素且删除完成返回true，如果不存在该元素则返回false
*/
public boolean remove(T nodeValue){
if(root == null){
return false;
}
AVLNode<T> toBeRemove = new AVLNode<T>(nodeValue);
if(root.compareTo(toBeRemove) == 0){
if(root.hasRight()){
AVLNode<T> minumumNodeFromRight = this.getMinumumNode(this.root.getRight());
if(this.root.getRight().compareTo(minumumNodeFromRight) == 0){
AVLNode<T> left = this.root.getLeft();
this.root.getRight().setLeft(left);
this.root = this.root.getRight();
}else{
this.innerDelete(this.root.getRight(), minumumNodeFromRight);
minumumNodeFromRight.setRight(this.root.getRight());
minumumNodeFromRight.setLeft(this.root.getLeft());
this.root = minumumNodeFromRight;
}
this.calcAndRotateIfNeeded(this.root);
}else{
this.root = this.root.getLeft();
}
}else{
this.innerDelete(this.root, toBeRemove);
}
return false;
}
private void innerAppend(AVLNode<T> currentNode, AVLNode<T> newNode){
int compareResult = currentNode.compareTo(newNode);
if(compareResult > 0){
if(currentNode.hasLeft()){
this.innerAppend(currentNode.getLeft(), newNode);
}else{
currentNode.setLeft(newNode);
}
}else if(compareResult < 0){
if(currentNode.hasRight()){
this.innerAppend(currentNode.getRight(), newNode);
}else{
currentNode.setRight(newNode);
}
}else{
currentNode.setValue(newNode.getValue());
}
/**
*
* 此方法是标准的二叉树插入操作，唯一要注意的是下面这行代码
* 因为我们是递归调用innerAppend方法，直到把要插入的节点放到正确的位置上
* 所以在节点被放置完毕后,此节点的所有父节点都需要重新计算一次高度，并在必要时进行旋转
*
* 只有一个例外，就是当节点是更新操作的时候，是不需要执行下面这行代码的
* 其实我们可以通过boolean变量来控制是否要执行，不过我比较懒
*
*/
this.calcAndRotateIfNeeded(currentNode);
}
private boolean containsInChilren(AVLNode<T> currentNode, AVLNode<T> condition){
if(currentNode == null){
return false;
}
int compareResult = currentNode.compareTo(condition);
if(compareResult > 0){
return this.containsInChilren(currentNode.getLeft(), condition);
}else if(compareResult < 0){
return this.containsInChilren(currentNode.getRight(), condition);
}else{
return true;
}
}
/**
* 删除方法，因为我们在执行删除逻辑的时候，需要处理当前节点的父节点与子节点的关系，所以把父节点作为参数传递进来
* 方法内不判断是否要删除父节点，而是判断是否要删除父节点的子节点
* @param parentNode
* @param condition
* @return
*/
private boolean innerDelete(AVLNode<T> parentNode, AVLNode<T> condition){
int compareResult = parentNode.compareTo(condition);
boolean deleted = false;
if(compareResult > 0 && parentNode.hasLeft()){
/**
* 如果父节点比当前要删除的节点大，并且当前父节点存在左节点
* 则判断当前父节点的左节点是否是要删除的节点，如果是就删除当前父节点的左节点
* 如果不是则递归
*/
AVLNode<T> leftSub = parentNode.getLeft();
if(leftSub.compareTo(condition) == 0){
this.realDeleteLeft(parentNode);
deleted = true;
}else{
deleted = this.innerDelete(leftSub, condition);
}
}else if(parentNode.hasRight()){
AVLNode<T> rightSub = parentNode.getRight();
if(rightSub.compareTo(condition) == 0){
this.realDeleteRight(parentNode);
deleted = true;
}else{
deleted = this.innerDelete(rightSub, condition);
}
}
/**
* 如果确实删除了当前节点的某个层级子节点，则当前节点需要重新计算高度，并有可能完成旋转
*/
if(deleted){
this.calcAndRotateIfNeeded(parentNode);
}
return deleted;
}
private void realDeleteLeft(AVLNode<T> parentNode){
AVLNode<T> toBeDelete = parentNode.getLeft();
AVLNode<T> oldLeft = toBeDelete.getLeft();
AVLNode<T> oldRight = toBeDelete.getRight();
if(oldRight == null) {
/**
* 当前要删除的节点不存在右子树
* 删除逻辑3的场景
*/
parentNode.setLeft(oldLeft);
}else{
AVLNode<T> minumumNodeFromRight = this.getMinumumNode(oldRight);
if(minumumNodeFromRight.compareTo(oldRight) == 0){
/**
* 要删除的右子树的根节点没有左节点
* 删除逻辑4.1的场景
*/
parentNode.setLeft(oldRight);
oldRight.setLeft(oldLeft);
}else{
/**
* 要删除的节点的右子树的根节点存在比根节点还小的子节点
* 但是这个要找的节点的位置还不确定，所以我偷懒用递归从右子树中删除最小节点
* 删除逻辑4.2的场景
*/
this.innerDelete(oldRight, minumumNodeFromRight);
parentNode.setLeft(minumumNodeFromRight);
minumumNodeFromRight.setLeft(oldLeft);
minumumNodeFromRight.setLeft(oldRight);
}
this.calcAndRotateIfNeeded(parentNode.getLeft());
}
}
private void realDeleteRight(AVLNode<T> parentNode){
AVLNode<T> toBeDelete = parentNode.getRight();
AVLNode<T> oldLeft = toBeDelete.getLeft();
AVLNode<T> oldRight = toBeDelete.getRight();
if(oldRight == null){
parentNode.setRight(oldLeft);
}else{
AVLNode<T> minumumNodeFromRight = this.getMinumumNode(oldRight);
if(oldRight.compareTo(minumumNodeFromRight) == 0) {
/**
* 走入这个分支，说明要删除的节点的右子树的根节点没有左子树
*/
parentNode.setRight(oldRight);
oldRight.setLeft(oldLeft);
}else{
this.innerDelete(oldRight, minumumNodeFromRight);
parentNode.setRight(minumumNodeFromRight);
minumumNodeFromRight.setRight(oldRight);
minumumNodeFromRight.setLeft(oldLeft);
}
this.calcAndRotateIfNeeded(parentNode.getRight());
}
}
/**
* 给定一个节点，从这个节点和这个节点的所有子节点中找到值最小的节点
* @param currentNode
* @return
*/
private AVLNode<T> getMinumumNode(AVLNode<T> currentNode){
if(currentNode.hasLeft()){
return this.getMinumumNode(currentNode.getLeft());
}else{
return currentNode;
}
}
/**
* 重新计算节点高度，并在需要旋转时控制节点进行旋转的方法
* 当某个节点的子节点高度发生变化的时候，会调用这个方法
* @param node
*/
private void calcAndRotateIfNeeded(AVLNode<T> node){
node.calculateDepth();
if(node.needRotate()){
node.rotate();
}
}
}
预告
接下来我想写的是多路查找树中的2-3树
