AVL树

我就鸽了一天哦！！！【雾】

AVL树，是一种平衡(balanced)的二叉搜索树(binary search tree, 简称为BST)；AVL树是带有平衡条件的二叉查找树。由于各种算法教材上对 AVL 的介绍十分冗长，造成了很多人对 AVL 树复杂、不实用的印象。但实际上，AVL 树的原理简单，实现也并不复杂。好像的确是这样啊【雾】…相对来说这个平衡条件必须要容易保持，而且他须保证书的深度是O（log N)最简单的想法是要求左右树相同的高度。它有以下两个性质：

  • 任意一个结点的key，比它的左孩子key大，比它的右孩子key小；
  • 任意结点的孩子结点之间高度差距最大为1；
  • 空二叉树是一个 AVL 树
  • 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树。
  • 树高为 O（log N）；
  • 空树的高度定为-1

平衡因子：右子树高度 - 左子树高度

另一种平衡条件是要求每个节点都必须要有相同的左子树和右子树。如果空子树的高度定义为-1，那么只有具有2^K-1个节点的理想平衡树满足这个条件，因此虽然这个平衡树保证了树的深度小，但是它太严格了，难以使用。前面我们说了要想满足AVL树的条件，左子树和右子树的高度必须<=1

一棵树最少节点数满足斐波那契数列，且S(h)=S(h-1)+S(h-2)+1,对于h=0;S(1)=1;h1=1,S(h)=2;h代表AVL树中的高。

这部分的验证代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include< bits/stdc++.h>
using namespace std;
int f(int n){
    if(n==0)
    return 1;
    else if(n==1)
    return 2;
    else return f(n-1)+f(n-2)+1;
}
int main(){
int n;
cin>>n;
cout<<f(n-1)+f(n-2)+1<<endl;
system("pause");
}

当进行插入操作时

我们需要更新通向根节点路径那些节点的所有平衡信息，而进行插入操作时，我们需要更新通向根节点路径上的那些节点的所有平衡信息，而插入操作可能存在的困难在于，插入一个根节点可能破坏AVL树的特性，如果发生了这种情况，那么要把性质恢复以后才认为这一步插入完成，事实上，这总可以通过对树的简单修正来做到，当然了这个我们称作旋转。

当然了在插入以后，只有那些从插入点到根节点的路径上的节点间的平衡可能被改变，因为只有这些节点的子树可能发生变化，当我们沿着这条路径更新平衡信息时，我们可以找到一个节点，他的新平衡破坏了AVL的平衡条件，所以我们需要找出这样一个节点并重新平衡这棵树，并证明，这一平衡保证满足AVL特性。

如果把必须重新平衡的节点叫做a好了由于任意节点最多有两个孩子，因此当高度不平衡时，a点的两棵子树高度差为2.很容易看出不平衡可能存在以下几种情况

  • 对a的左儿子的左子树进行一次插入

失衡结点" 的左子树比右子树高 2，左孩子（即 x）下的左子树比右子树高 1。我们只需对 “以 y 为根的子树” 进行 “左左旋转 (ll_rotate)” 即可。一次旋转后，恢复平衡。

  • 对a的左儿子的右子树进行一次插入

所谓的左右，即 “失衡结点” 的左子树比右子树高 2，左孩子（即 x）下的右子树比左子树高 1。观察发现，若先对 “以 x 为根的子树” 进行 “右右旋转 (rr_rotate)”，此时 “以 y 为根的子树” 恰好符合 “左左失衡”，所以再进行一次 “左左旋转 (ll_rotate)”。两次旋转后，恢复平衡。

  • 对a的右儿子的左子树进行一次插入

所谓的右左，即 “失衡结点” 的右子树比左子树高 2，右孩子（即 x）下的左子树比右子树高 1。观察发现，若先对 “以 x 为根的子树” 进行 “左左旋转 (ll_rotate)”，此时 “以 y 为根的子树” 恰好符合 “右右失衡”，所以再进行一次 “右右旋转 (rr_rotate)”。两次旋转后，恢复平衡。

  • 对a的右儿子的右子树进行一次插入

所谓的右右，即 “失衡结点” 的右子树比左子树高 2，右孩子（即 x）下的右子树比左子树高 1。我们只需对 “以 y 为根的子树” 进行 “右右旋转 (rr_rotate)” 即可。一次旋转后，恢复平衡。

单旋转

单旋转顾名思义就是通过一次旋转来达到AVL树平衡的目的，前面的左左平衡和右右平衡是但旋转，刚好是镜像对称

双旋转

顾名思义通过两次旋转来达到平衡的目的左右和右左平衡是双旋转，也刚好是镜面对称。但深度依旧没办法降低，一次旋转无法降低它的深度就需要双旋转了。

多说无益！！！那就直接扔代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include< bits/stdc++.h>
using namespace std;
typedef struct AVLnode *Position;
typedef struct AVLnode *AVLTree;
typedef int ElementType;
struct AVLnode
{
    ElementType Element;
    AVLTree Left;
    AVLTree Right;
    int Height;
};
static int Height(Position P)
{
    if (P == nullptr)
        return -1;
    else
        return P->Height;
}
static Position singleRotateWithRight(Position k2)
{
    Position k1;
    k1 = k2->Right;
    k2->Right = k1->Left;
    k1->Left = k2;
    k2->Height = max(Height(k2->Left), Height(k2->Right)) + 1;
    k1->Height = max(Height(k1->Right), Height(k2->Left)) + 1;
    return k1; //返回新的根节点，后面也是一样哒
}
static Position singleRotateWithLeft(Position k2)
{
    Position k1;
    k1 = k2->Left;
    k2->Left = k1->Right;
    k1->Right = k2;
    k2->Height = max(Height(k2->Left), Height(k2->Right)) + 1;
    k1->Height = max(Height(k1->Left), Height(k2->Right)) + 1;
    return k1;
}
static Position DoubleRotateWithRight(Position k3)
{
    k3->Right = singleRotateWithLeft(k3->Right);
    return singleRotateWithRight(k3);
}

static Position DoubleRotateWithLeft(Position k3)
{
    k3->Left = singleRotateWithRight(k3->Left);
    return singleRotateWithLeft(k3);
}
AVLTree Insert(ElementType X, AVLTree T)
{
    if (T == nullptr)
    {
        T = new AVLnode;
        if (T == nullptr)
            cout << "error";
        else
        {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = nullptr;
        }
    }
    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 = singleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);
    }
    else if (X > T->Element)
    {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)
            if (X > T->Right->Element)
                T = singleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
    }
    T->Height = max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}
int main()
{
    AVLTree T;
    T = nullptr;
    T = Insert(1, T);
    T = Insert(15, T);
    T = Insert(3, T);

    printf("Root: %d\n", T->Element);
    system("pause");
    return 0;
}

反正大概我知道的就那么多了【逃】