题目链接

基本概念

平衡二叉树又称AVL树，它是一种具有平衡因子的特殊二叉排序树。平衡二叉树或者是一棵空树，或者是具有以下几条性质的二叉树：

  1. 若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；

  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；

  3. 它的左右子树也分别为平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

若将二叉树上结点的平衡因子定义为该结点的左子树深度减去它的右子树的深度，则平衡二叉树上的所有结点的平衡因子只可能为-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则这棵二叉树就是不平衡的。

通过平衡二叉树的性质不难得知，其插入、删除、查询都操作的时间复杂度均为O(log2n)。

解释一下右转
在这里插入图片描述
代码如下：

1
2
3
4
5
6
7
8
9
void lg_R(lg** root)
{
    lg *t=(*root)->left;
    (*root)->left=t->right;
    t->right=(*root);
    (*root)->h=lg_geth((*root));
    t->h=lg_geth(t);
    *root=t;
}

左转类似。

总代码如下：

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
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int d,h;			//h为高度，用高度判断当前子树是否平衡，d为存储的数据
    struct node *left;
    struct node *right;
}lg;
int max(int a,int b)	//返回最大值的函数
{
    return a>b?a:b;
}
int h(lg *tree)			//返回当前节点的高度
{
    if(tree==NULL)return 0;
    else return tree->h;
}
int lg_geth(lg *root)	//求当前节点的高度（左右子树的最高高度+1）
{
    return max(h(root->left),h(root->right))+1;
}
int lg_getp(lg *root)	//求当前节点的平衡因子（左子树高度减去右子树高度）
{
    return h(root->left)-h(root->right);
}
void lg_R(lg** root)	//树不平衡右转
{
    lg *t=(*root)->left;
    (*root)->left=t->right;
    t->right=(*root);
    (*root)->h=lg_geth((*root));
    t->h=lg_geth(t);
    *root=t;
}
void lg_L(lg** root)	//左转
{
    lg *t=(*root)->right;
    (*root)->right=t->left;
    t->left=(*root);
    (*root)->h=lg_geth((*root));
    t->h=lg_geth(t);
    *root=t;
}
void lg_insert(int w,lg** root)	//插入节点
{
    if(*root==NULL)
    {
        *root=(lg*)malloc(sizeof(lg));
        (*root)->d=w;
        (*root)->h=1;
        (*root)->left=NULL;
        (*root)->right=NULL;
        return ;
    }
    if((*root)->d>w)
    {
        lg_insert(w,&((*root)->left));
        (*root)->h=lg_geth((*root));
        if(lg_getp(*root)==2)
        {
            if(lg_getp((*root)->left)==1)lg_R(&(*root));
            else if(lg_getp((*root)->left)==-1)
            {
                lg_L(&(*root)->left);
                lg_R(&(*root));
            }
        }
    }
    else
    {
        lg_insert(w,&(*root)->right);
        (*root)->h=lg_geth((*root));
        if(lg_getp((*root))==2)
        {
            if(lg_getp((*root)->right)==1)lg_L(&(*root));
            else if(lg_getp((*root)->right)==-1)
            {
                lg_R(&(*root)->right);
                lg_L(&(*root));
            }
        }
    }
}
int lg_search(lg *root,int num)	//递归查找节点是否存在
{
    if(root==NULL)return 0;
    if(root->d==num)return 1;
    if(root->d<num)return lg_search(root->right,num);
    else return lg_search(root->left,num);
}
int main()
{
    lg *root=NULL;
    int n,m,w,num;
    scanf("%d%d",&n,&m);
    while(n--)
    {
        scanf("%d",&w);
        lg_insert(w,&root);
    }
    while(m--)
    {
        scanf("%d",&num);
        printf("%d ",lg_search(root,num));
    }
    puts("");
    return 0;
}