数据结构_我不会AVL

数据结构_我不会AVL_wbhavl

问题描述

　　欢迎来到暴走数据结构，我是洪尼玛。今天，我们来玩 AVL 树，怎么玩呢？很简单：给
你 n 个数字，你需要按顺序插入一棵 AVL树中，然后输出每个数所在节点的深度（从 1 开始）。
因为我不会 AVL 树，所以希望聪明的你们来帮我完成这个任务

★数据输入
输入第一个数为 n（n≤100000）表示数字的个数
接下来一行输入 n 个数，范围在 1 到 n 之间，每个数只出现一次

★数据输出
按输入的顺序依次输出每个数所在节点的深度

输入示例	输出示例
6 1 2 3 4 5 6	3 2 3 1 2 3

★提示
注意：输出行末不能有空格
对于 50%的数据， 1<=n<=100
对于 100%的数据， 1<=n<=100000

思路

　　没说明技巧，就是avl树

　　具体实现自行百度

code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 struct Node
  6 {
  7     int data;
  8     int height;
  9     int left;
 10     int right;
 11 };
 12 
 13 Node *arr = NULL;
 14 
 15 inline int Max(int a,int b) {return a>b?a:b;}
 16 inline int GetHeight(int root){
 17     return arr[root].height; //return root==0 ? 0 : arr[root]->height;
 18 }
 19 inline void CalcHeight(int root){
 20     arr[root].height = Max(GetHeight(arr[root].left),GetHeight(arr[root].right)) + 1;
 21 }
 22 //------------------------------------------------------------------------------------
 23 int RightRotate(int root)
 24 {
 25     int newroot = arr[root].left;
 26     arr[root].left = arr[newroot].right;
 27     arr[newroot].right = root;
 28     CalcHeight(root);
 29     CalcHeight(newroot);
 30     return newroot;
 31 }
 32 int LeftRotate(int root)
 33 {
 34     int newroot = arr[root].right;
 35     arr[root].right = arr[newroot].left;
 36     arr[newroot].left = root;
 37     CalcHeight(root);
 38     CalcHeight(newroot);
 39     return newroot;
 40 }
 41 int LeftRightRotate(int root)
 42 {
 43     arr[root].left = LeftRotate(arr[root].left);
 44     return RightRotate(root);
 45 }
 46 int RightLeftRotate(int root)
 47 {
 48     arr[root].right = RightRotate(arr[root].right);
 49     return LeftRotate(root);
 50 }
 51 //------------------------------------------------------------------------------------
 52 int Insert(int root, int data)
 53 {
 54     if(root==0)
 55     {
 56         arr[data].data = data;
 57         arr[data].height = 1;
 58         return data;
 59     }
 60     else if(data < arr[root].data)
 61     {
 62         arr[root].left = Insert(arr[root].left,data);
 63         if(GetHeight(arr[root].left) - GetHeight(arr[root].right) >= 2)
 64         {
 65             if(data < arr[arr[root].left].data)
 66                 root = RightRotate(root);
 67             else//if(data > arr[arr[root]->left]->data)
 68                 root = LeftRightRotate(root);
 69         }
 70     }
 71     else if(data > arr[root].data)
 72     {
 73         arr[root].right = Insert(arr[root].right,data);
 74         if(GetHeight(arr[root].right) - GetHeight(arr[root].left) >= 2)
 75         {
 76             if(data > arr[arr[root].right].data)
 77                 root = LeftRotate(root);
 78             else//if(data < arr[arr[root]->right]->data)
 79                 root = RightLeftRotate(root);
 80         }
 81     }//else ==
 82     CalcHeight(root);
 83     return root;
 84 }
 85 
 86 void dfs(int index,int step)
 87 {
 88     if(index==0) return;
 89     arr[index].height = step;
 90     dfs(arr[index].left,step+1);
 91     dfs(arr[index].right,step+1);
 92 }
 93 
 94 int main()
 95 {
 96     int n;
 97     scanf("%d",&n);
 98     int *data = (int *)malloc(sizeof(int)*(n+1));
 99     arr = (Node *)malloc(sizeof(Node)*(n+1));
100     memset(arr,0,sizeof(Node)*(n+1));
101     //------------------------------------------------
102     int root = 0;
103     int i;
104     for(i=0; i<n; i++)
105     {
106         scanf("%d",data+i);
107         root = Insert(root,data[i]);
108     }
109     dfs(root,1);
110     for(i=0; i<n; i++)
111     {
112         if(i==n-1)
113             printf("%d
",arr[data[i]].height);
114         else
115             printf("%d ",arr[data[i]].height);
116     }
117     
118     //------------------------------------------------
119     free(arr);
120     free(data);
121     return 0;
122 }