数据结构与算法之AVL树(九)

目录

• 基本概念
• 添加节点后恢复平衡操作
  • 处理失衡的方法 LL，RR，LR，RL
  • 图解 + 核心代码实现 + 原理讲解
• 删除节点后恢复平衡操作
• 处理失衡的方法 LL，RR，LR，RL
• 总结

一 简介

AVL树是最早发明的自平衡二叉搜索树之一

备注：AVL 取名于两位发明者的名字
G. M. Adelson-Velsky和 E. M. Landis(来自苏联的科学家)

1.1 几个概念

• 平衡因子(Balance Factor)：某结点的左右子树的高度差
• AVL树的特点
  • 每个节点的平衡因子只可能是 1、0、-1(绝对值 ≤ 1，如果超过 1，称之为“失衡”)
  • 每个节点的左右子树高度差不超过 1
  • 搜索、添加、删除的时间复杂度是 O(logn)

image.png

1.2 平衡对比

输入数据:35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82

• 普通二叉搜索树 AVL树

  
  二叉搜索树.png

• AVL树

AVL树.png

1.3 添加导致的失衡

示例：往下面这棵子树中添加 13

• 最坏情况：可能会导致所有祖先节点都失衡
• 父节点、非祖先节点，都不可能失衡

添加节点失衡.png

二 处理失衡

2.1 LL - 右旋转（单旋）

LL.png

伪代码：

1.g.left = p.right
2.p.right = g
3.让 p 成为这棵子树的根节点
4.仍然是一棵二叉搜索树，T0 < n < T1 < p < T2 < g < T3
5.还需要维护：
5.1 T2，p，g的 parent 属性 
5.2 先后更新 g，p的高度

2.2 RR - 左旋转（单旋）

RR.png

• 伪代码实现

1. g.right = p.left
2. p.left = g
3. 让p成为这棵子树的根节点
4. 仍然是一棵二叉搜索树:T0 < g < T1 < p < T2 < n < T3 ◼ 整棵树都达到平衡
5. 还需要注意维护的内容 
5.1 T1、p、g 的 parent 属性 
5.2 先后更新 g、p 的高度

2.3 LR – RR左旋转，LL右旋转(双旋)

LR.png

2.4 RL – LL右旋转，RR左旋转(双旋)

RL.png

三 代码实现

新建一个类AVLTree继承自BST，并重写构造节点的方法createNode:parent，返回一个AVL树节点AVLNode，该节点继承自TreeNode。

3.1 AVLNode类

• AVLNode.h

/**
 AVL树节点
 */
@interface AVLNode : TreeNode

/** int - 高度*/
@property(nonatomic,assign)int height;

/** 平衡因子 */
- (int)balanceFactor;

/** 更新高度 */
- (void)updateHeight;

/** 返回节点数较多的节点 */
- (TreeNode *)tallerChild;

@end

• AVLNode.m

@implementation AVLNode

/** 平衡因子 */
- (int)balanceFactor {
    int leftHeight = self.left == nil ? 0 : ((AVLNode *)(self.left)).height;
    int rightHeight = self.right == nil ? 0 : ((AVLNode *)(self.right)).height;
    return leftHeight - rightHeight;
}

/** 更新高度 */
- (void)updateHeight {
    int leftHeight = self.left == nil ? 0 : ((AVLNode *)(self.left)).height;
    int rightHeight = self.right == nil ? 0 : ((AVLNode *)(self.right)).height;
    
    self.height = 1 + MAX(leftHeight, rightHeight);
}

/** 返回节点数较多的节点 */
- (TreeNode *)tallerChild {
    int leftHeight = self.left == nil ? 0 : ((AVLNode *)(self.left)).height;
    int rightHeight = self.right == nil ? 0 : ((AVLNode *)(self.right)).height;
    
    if (leftHeight > rightHeight) {
        return self.left;
    } else if (leftHeight < rightHeight) {
        return self.right;
    }
    
    return [self isLeftChild] ? self.left : self.right;
}

@end

3.2 AVLTree类

• AVLTree.h

/**
 AVL树
 */
@interface AVLTree : BST

@end

• AVLTree.m

@implementation AVLTree

/** 初始化 */
- (AVLNode *)createNode:(id)element parent:(AVLNode *)parent {
    return [[AVLNode alloc] initWithElement:element parent:parent];
}

/// 新添加节点之后的处理
- (void)afterAdd:(TreeNode *)node {
    while ((node = node.parent) != nil) {
        if ([self isBalanced:(AVLNode *)node]) {
            // 更新高度
            [self updateHeight:(AVLNode *)node];
        } else {
            // 恢复平衡
            [self rebalance:(AVLNode *)node];
            // 整颗树恢复平衡
            break;
        }
    }
}

/**
 恢复平衡
 @param grand 高度最低的那个不平衡节点
 */
- (void)rebalance:(AVLNode *)grand {
    AVLNode *parent = (AVLNode *)(grand.tallerChild);
    TreeNode *node = parent.tallerChild;
    
    if (parent.isLeftChild) {   // L
        if (node.isLeftChild) { // LL
            [self rotateRight:grand];
        } else {    // LR
            [self rotateLeft:parent];
            [self rotateRight:grand];
        }
    } else {    // R
        if (node.isLeftChild) { // RL
            [self rotateRight:parent];
            [self rotateLeft:grand];
        } else {    // RR
            [self rotateLeft:grand];
        }
    }
}

/** 左旋转 grand - 爷爷节点 */
- (void)rotateLeft:(AVLNode *)grand {
    TreeNode *parent = grand.right;
    TreeNode *child = parent.left;
    grand.right = child;
    parent.left = grand;
    [self afterRotate:grand parent:parent child:child];
}

/** 右旋转 */
- (void)rotateRight:(AVLNode *)grand {
    TreeNode *parent = grand.left;
    TreeNode *child = parent.right;
    grand.left = child;
    parent.right = grand;
    [self afterRotate:grand parent:parent child:child];
}

/** 更新节点*/
- (void)afterRotate:(TreeNode *)grand parent:(TreeNode *)parent child:(TreeNode *)child {
    // 让parent成为子树的根节点
    parent.parent = grand.parent;

    if (parent.isLeftChild) {
        grand.parent.left = parent;
    } else if (grand) {
        grand.parent.right = parent;
    } else {    // grand 是 root节点
        self.root = parent;
    }
    
    // 更新child的parent
    if (child != nil) {
        child.parent = grand;
    }
    
    // 更新grand的parent
    grand.parent = parent;
    
    // 更新高度
    [self updateHeight:(AVLNode *)grand];
    [self updateHeight:(AVLNode *)parent];
}

/** 是否是平衡树 */
- (BOOL)isBalanced:(AVLNode *)node {
    return abs(node.balanceFactor) <= 1;
}

/** 更新子树高度 */
- (void)updateHeight:(AVLNode *)node {
    [node updateHeight];
}

最后在二叉树BST添加节点的方法后需要平衡二叉树，即调用

afterAdd: //方法 - 平衡二叉树

3.3 测试代码

// AVL树
- (void)avlTreeTest {
    NSArray *datas = @[@67, @52, @92, @96, @53, @95, @13, @63, @34, @82, @76, @54, @9, @68, @39];
    
    AVLTree *avl = [[AVLTree alloc] init];
    for (int i = 0; i < datas.count; i++) {
        [avl add:datas[i]];
    }
    
    NSLog(@"%@",avl.description);
}

• 运行结果 - 添加节点后不平衡二叉树

fe.png

• 运行结果 - 添加节点后平衡二叉树

  
  image.png

四 统一所有旋转操作

image.png

由上图可知，最终结果，中序排列顺序为 a,b,c,d,e,f,g

代码实现如下

• 平衡二叉树操作

/**
 恢复平衡
 @param grand 高度最低的那个不平衡节点
 */
- (void)rebalance2:(AVLNode *)grand {
    AVLNode *parent = (AVLNode *)grand.tallerChild;
    AVLNode *node = (AVLNode *)parent.tallerChild;
    
    if (parent.isLeftChild) {   // L
        if (node.isLeftChild) { // LL
            [self rotate:grand a:node.left b:node c:node.right d:parent e:parent.right f:grand g:grand.right];
        } else {    // LR
            [self rotate:grand a:parent.left b:parent c:node.left d:node e:node.right f:grand g:grand.right];
        }
    } else {    // R
        if (node.isLeftChild) { // RL
            [self rotate:grand a:grand.left b:grand c:node.left d:node e:node.right f:parent g:parent.right];
        } else {    // RR
            [self rotate:grand a:grand.left b:grand c:parent.left d:parent e:node.left f:node g:node.right];
        }
    }
}

• 旋转操作

/// 旋转操作
- (void)rotate:(TreeNode *)r    // 子树的根节点
             a:(TreeNode *)a b:(TreeNode *)b c:(TreeNode *)c
             d:(TreeNode *)d
             e:(TreeNode *)e f:(TreeNode *)f g:(TreeNode *)g {
    // 让 d 成为这棵子树的根节点
    d.parent = r.parent;
    
    if (r.isLeftChild) {
        r.parent.left = d;
    } else if (r.isRightChild) {
        r.parent.right = d;
    } else {
        self.root = d;
    }
    
    // a-b-c
    b.left = a;
    if (a != nil) {
        a.parent = b;
    }
    b.right = c;
    if (c != nil) {
        c.parent = b;
    }
    [self updateHeight:b];
    
    // e-f-g
    f.left = e;
    if (e != nil) {
        e.parent = f;
    }
    f.right = g;
    if (g != nil) {
        g.parent = f;
    }
    [self updateHeight:f];
    
    // b-d-f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    [self updateHeight:d];
}

代码实现要结合上图一起看

五 删除导致的失衡

示例:删除下面这棵子树中的 16

image.png

• 只可能会导致父节点失衡
• 除父节点以外的其他节点，都不可能失衡

恢复平衡操作

5.1 LL – 右旋转(单旋)

• 如果绿色节点不存在，更高层的祖先节点可能也会失衡，需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡...
• 极端情况下，所有祖先节点都需要进行恢复平衡的操作，共 O(logn) 次调整

调整前.png 调整后.png

RR – 左旋转(单旋)

调整前.png 调整后.png

5.3 LR – RR左旋转，LL右旋转(双旋)

调整前.png 调整后.png

5.4 RL – LL右旋转，RR左旋转(双旋)

调整前.png 调整后.png

5.5 删除之后的恢复操作

/** 删除节点后平衡二叉树 */
- (void)afterRemove:(TreeNode *)node {
    while ((node = node.parent) != nil) {
        if ([self isBalanced:(AVLNode *)node]) {
            // 更新高度
            [self updateHeight:(AVLNode *)node];
        } else {
            // 恢复平衡
            [self rebalance:(AVLNode *)node];
        }
    }
}

六 总结

6.1 添加

• 可能会导致所有祖先节点都失衡
• 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 O(1) 次调整】

6.2 删除

• 只可能会导致父节点失衡
• 让父节点恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】

6.3 平均时间复杂度

• 搜索:O(logn)
• 添加:O(logn)，仅需 O(1) 次的旋转操作
• 删除:O(logn)，最多需要 O(logn) 次的旋转操作

---

本文会持续更新中，更多精彩内容敬请期待。

---

本文参考 MJ老师的 恋上数据结构与算法

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励。

---

项目连接链接 - 11_AVLTree