AVL 树 [数据结构与算法分析 c 语言描述]

1. 概述

主要知识点

  • AVL 树定义
  • 单旋转(左左单旋转、右右单旋转)
  • 双旋转(左右双旋转、右左双旋转)

2. 什么是 AVL 树

定义
带有平衡条件的二叉查找树。
平衡条件:其每个节点的左子树和右子树的高度最多相差1的二叉查找树。(空树的高度为 -1)。

  • 所有的树操作都可以以时间 O(logN) 执行。
  • 当插入时有可能会破坏平衡条件,我们通过旋转(rotation)来进行修正。

3. 如何解决不平衡情况

根据 AVL 树的特性可以知道:α 点的两颗子树的高度差2(α 是需要平衡的节点)。
所以这种不平衡在插入时可能出现的情况如下四种:

  1. α 的左儿子的左子树进行一次插入。(左左单旋转)
  2. α 的左儿子的右子树进行一次插入。 (左右双旋转)
  3. α 的右儿子的左子树进行一次插入。 (右左双旋转)
  4. α 的右儿子的右子树进行一次插入。 (右右单旋转)

以上四种情况可以合成两种情况

  • 1 和 4 是插入发生在外部(左左、右右)单旋转处理。
  • 2 和 3 是插入发生的内部(左右、右左)双旋转处理。

4. 关于旋转

旋转是对树的常用操作,有两个最重要的属性:

  • 旋转轴
  • 旋转方向

4.1 旋转轴的确定

  • 单旋转:α 的孩子节点。
  • 双旋转:α 的孙子节点。

α 为需要平衡的节点即是不满足 AVL 特性的最小树的跟节点。

4.2 旋转方向

  • 左左单旋转(顺时针)。
  • 右右单旋转(逆时针)

4.3 单旋转还是双旋转

  • 情况 1 和情况 4 用单旋转。
  • 情况 2 和情况 3 需要用双旋转。

根据二叉搜索树的特性可以得到(设插入数为 x,旋转轴为 β)

  • x 的大小阶于 α 的值与 β 的值之外(即是情况 1 和 4,外部插入)。
  • x 的大小阶于 α 的值与 β 的值之间(即是情况 2 和 3,内部插入)。

5. 单旋转

单旋转:进行一次旋转。
1、4 的情况需要用到单旋转来修正。
左左单旋转(顺时针)
file
右右单旋转(逆时针)
file

6. 双旋转

进行两次单旋转。
2、3 的情况需要用双旋转来修正。
左右双旋转:先右右单旋转再左左单旋转
file
右左双旋转:先左左单旋转再右右单旋转
file

7. 代码实现

头文件,核心在 insert 跟旋转,其他实现跟二叉搜索树一样二叉搜索树

typedef int element_type;

struct avl_node;
typedef struct avl_node *position;
typedef struct avl_node *avl_tree;

avl_tree make_empty(avl_tree t);
position find(element_type x, avl_tree t);
position find_min(avl_tree t);
position find_max(avl_tree t);
avl_tree insert(element_type x, avl_tree t);
avl_tree delete(element_type x, avl_tree t);
element_type retrieve(position p);

position single_rotate_with_left_left(position k2);
position single_rotate_with_right_right(position k2);
position double_rotate_with_left_right(position k3);
position double_rotate_with_right_left(position k3);

int height(position p);
int max(int a, int b);

void print_tree(avl_tree t);
void test();

struct avl_node
{
    element_type element;
    avl_tree left;
    avl_tree right;
    int height;
}

所有代码

/**
 * AVL树
 */

#include <stdio.h>
#include <stdlib.h>
#include "avltree.h"

#define error(str) fatal_error(str)
#define fatal_error(str) fprintf(stderr, "%s\n", str),exit(1)

int height(position p)
{
    if (NULL == p)
        return -1;
    else
        return p->height;
}

position find(element_type x, avl_tree t)
{
    if (NULL == t)
        return NULL;
    if (x > t->element)
        return find(x, t->right);
    else if (x < t->element)
        return find(x, t->left);
    else
        return t;
}

position find_min(avl_tree t)
{
    if (NULL != t)
        while (NULL != t->left)
            t = t->left;
    return t;
}

position find_max(avl_tree t)
{
    if (NULL == t)
        return NULL;

    if (NULL == t->right)
        return t;
    else
        return find_max(t->right);
}

avl_tree delete( element_type x, avl_tree t)
{
    position temp;
    if (NULL == t)
        error("empty tree");

    if (x > t->element)
        t->right = delete(x, t->right);
    else if (x < t->element)
        t->left = delete(x, t->left);
    else if(t->left && t->right) {
        temp = find_min(t->right);
        t->element = temp->element;
        t->right = delete(t->element, t->right);
    } else {
        temp = t;
        if (NULL == t->left)
            t = t->right;
        else if (NULL == t->right)
            t = t->left;
        free(temp);
        temp = NULL;
    }
    return t;
}

avl_tree make_empty(avl_tree t)
{
    if (NULL != t) {
        make_empty(t->left);
        make_empty(t->right);
        free(t);
    }

    return NULL;
}

avl_tree insert(element_type x, avl_tree t)
{
    if (NULL == t) {
        t = (avl_tree)malloc(sizeof(struct avl_node));
        if (NULL == t)
            fatal_error("out of space");
        t->element = x;
        t->left = t->right = NULL;
        t->height = 0;
    } else if (x < t->element) {
        t->left = insert(x, t->left);
        if ( ( height(t->left) - height(t->right) ) == 2 ) {
            if (x < t->left->element)
                t = single_rotate_with_left_left(t);
            else
                t = double_rotate_with_left_right(t);
        }
    } else if (x > t->element) {
        t->right = insert(x, t->right);
        if ( ( height(t->right) - height(t->right) ) == 2 ) {
            if (x > t->right->element)
                t = single_rotate_with_right_right(t);
            else
                t = double_rotate_with_right_left(t);
        }
    }
    //节点高度为 左右节点高度最大值 + 1
    t->height = max(height(t->left), height(t->right) ) + 1;
    return t;
}

// 左左单旋转
position single_rotate_with_left_left(position k2)
{
    position k1;
    k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k1->height = max( height(k1->left), height(k1->right) ) + 1;
    k2->height = max( height(k2->left), height(k2->right) ) + 1;
    return k1;
}
// 右右单旋转
position single_rotate_with_right_right(position k2)
{
    position k1;
    k1 = k2->right;
    k2->right = k1->left;
    k1->left = k2;
    k1->height = max( height(k1->left), height(k1->right) ) + 1;
    k2->height = max( height(k2->left), height(k2->right) ) + 1;
    return k1;
}
// 左右双旋转
position double_rotate_with_left_right(position k3)
{
    k3->left = single_rotate_with_right_right(k3->left);
    return single_rotate_with_left_left(k3);
}
// 右左双旋转
position double_rotate_with_right_left(position k3)
{
    k3->right = single_rotate_with_left_left(k3->right);
    return single_rotate_with_right_right(k3);
}
int max(int a, int b)
{
    return a > b ? a : b;
}

void print_tree(int depth, int left, avl_tree t)
{
    int i;
    if (t) {
        for(i = 0; i < left; i++)
            printf("    ");
        printf("%d\n", t->element);
        print_tree(depth + 1, left - 1, t->left);
        print_tree(depth + 1, left + 1, t->right);
    } 
}

void test()
{
    avl_tree t;
    printf("\n ====== test for building the AVLTree ====== \n");
    printf("\n [the left-left single rotate case] test with inserting 3, 2, 1 in trun \n");

    t = NULL;
    t = insert(3, t);   
    t = insert(2, t);   
    t = insert(1, t);   
    print_tree(1,5, t); 
}

int main(int argc, char const *argv[])
{
    test();
    return 0;
}

8. 测试截图

file
最后附上一个讲单双旋转讲得很好的文章
单双旋转详解

本作品采用《CC 协议》,转载必须注明作者和本文链接
高度自律,深度思考,以勤补拙
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!