An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.




Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print ythe root of the resulting AVL tree in one line.
Sample Input 1:
1 2 |
5 88 70 61 96 120 |
Sample Output 1:
1 |
70 |
Sample Input 2:
1 2 |
7 88 70 61 96 120 90 65 |
Sample Output 2:
1 |
88 |
偷懒写了递归版……
代码如下:
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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include<stdio.h> #include<stdlib.h> #define AVL_BALANCED 0 #define AVL_LEFT_HEAVY 1 #define AVL_RIGHT_HEAVY -1 typedef struct bistree_node { int data; int factor; struct bistree_node *left; struct bistree_node *right; } bistree_node; typedef struct bistree { bistree_node *root; } bistree; bistree_node *roate_left(bistree_node *root) { bistree_node *left,*grandchild; left=root->left; if(left->factor==AVL_LEFT_HEAVY) { root->left=left->right; left->right=root; root->factor=AVL_BALANCED; left->factor=AVL_BALANCED; return left; } grandchild=left->right; root->left=grandchild->right; grandchild->right=root; left->right=grandchild->left; grandchild->left=left; switch(grandchild->factor) { case AVL_LEFT_HEAVY: left->factor=AVL_BALANCED;; root->factor=AVL_RIGHT_HEAVY; break; case AVL_BALANCED: left->factor=AVL_BALANCED; root->factor=AVL_BALANCED; break; case AVL_RIGHT_HEAVY: left->factor=AVL_LEFT_HEAVY;; root->factor=AVL_BALANCED; break; } grandchild->factor=AVL_BALANCED; return grandchild; } bistree_node *roate_right(bistree_node *root) { bistree_node *right,*grandchild; right=root->right; if(right->factor==AVL_RIGHT_HEAVY) { root->right=right->left; right->left=root; root->factor=AVL_BALANCED; right->factor=AVL_BALANCED; return right; } grandchild=right->left; root->right=grandchild->left; grandchild->left=root; right->left=grandchild->right; grandchild->right=right; switch(grandchild->factor) { case AVL_LEFT_HEAVY: right->factor=AVL_RIGHT_HEAVY; root->factor=AVL_BALANCED; break; case AVL_BALANCED: right->factor=AVL_BALANCED; root->factor=AVL_BALANCED; break; case AVL_RIGHT_HEAVY: right->factor=AVL_BALANCED; root->factor=AVL_LEFT_HEAVY; break; } grandchild->factor=AVL_BALANCED; return grandchild; } bistree_node *insert(bistree_node *root,int data,int *balance) { if(root==NULL) { root=(bistree_node *)malloc(sizeof(bistree_node)); root->left=NULL; root->right=NULL; root->factor=AVL_BALANCED; root->data=data; *balance=0; return root; } if(root->data>=data) { root->left=insert(root->left,data,balance); if(*balance==0) { switch(root->factor) { case AVL_LEFT_HEAVY: root=roate_left(root); *balance=1; break; case AVL_BALANCED: root->factor=AVL_LEFT_HEAVY; break; case AVL_RIGHT_HEAVY: root->factor=AVL_BALANCED; *balance=1; break; } } } else { root->right=insert(root->right,data,balance); if(*balance==0) { switch(root->factor) { case AVL_LEFT_HEAVY: root->factor=AVL_BALANCED; *balance=1; break; case AVL_BALANCED: root->factor=AVL_RIGHT_HEAVY; break; case AVL_RIGHT_HEAVY: root=roate_right(root); *balance=1; break; } } } return root; } int main() { int n,i,temp,balance=0; bistree *tree; scanf("%d",&n); tree=(bistree *)malloc(sizeof(bistree)); tree->root=NULL; for(i=0;i<n;i++) { scanf("%d",&temp); balance=0; tree->root=insert(tree->root,temp,&balance); } printf("%d\n",tree->root->data); } |
为什么你甲级的顺序是乱的?
我 PAT-Advanced 没有按照顺序做,更新时也是随便更的,现在想想似乎中间还有几道题没做,所以显得有点乱……(不过我也懒得调顺序了