จากวิกิพีเดีย สารานุกรมเสรี
//AVL.C
#include <stdio.h>
#include <conio.h>
typedef struct nodeT {
int dat;
int height,weight;
struct nodeT *left,*right,*parent;
} NODET;
typedef struct tree {
NODET *root;
} TREE;
TREE *createT();
void insert(TREE *,int);
void printT(NODET *);
void doAVL(TREE *,NODET *);
void rotateL(TREE *,NODET *);
void rotateR(TREE *,NODET *);
int maximum(int,int);
int main() {
TREE *T;
T = createT();
int count,i,dat;
scanf("%d",&count);
fflush(stdin);
for (i=0;i<count;i++) {
scanf("%d",&dat);
insert(T,dat);
}
printT(T -> root);
getch();
return (0);
}
TREE *createT() {
TREE *T;
T = (TREE *)malloc(sizeof(TREE));
return (T);
}
void insert(TREE *T, int dat) {
NODET *N,*ptr,*par;
N = (NODET *)malloc(sizeof(NODET));
N -> left = N -> right = NULL;
N -> dat = dat;
N -> height = 1;
N -> weight = 0;
if (T -> root == NULL) {
T -> root = N;
N -> parent = NULL;
} else {
ptr = T -> root;
while (ptr != NULL) {
par = ptr;
if (dat > ptr -> dat) ptr = ptr -> right;
else if (dat == ptr -> dat) return;
else ptr = ptr -> left;
}
N -> parent = par;
if (dat > par -> dat) par -> right = N;
else par -> left = N;
ptr = par;
while (ptr != NULL) {
if (ptr -> left == NULL) {
ptr -> weight = -(ptr -> right -> height);
ptr -> height = ptr -> right -> height + 1;
}
else if (ptr -> right == NULL) {
ptr -> weight = ptr -> left -> height;
ptr -> height = ptr -> left -> height + 1;
}
else {
ptr -> weight = ptr -> left -> height - ptr -> right -> height;
ptr -> height = maximum(ptr -> left -> height, ptr -> right -> height) + 1;
}
//height and weight recounted
doAVL(T,ptr);
ptr = ptr -> parent;
}
printf("\n");
}
}
void printT(NODET *N) {
if (N != NULL) {
printf("%d ",N -> dat);
printT(N -> left);
printT(N -> right);
}
}
void doAVL(TREE *T,NODET *N) {
if (N -> weight < -1)
if (N -> right -> weight == -1) rotateL(T,N -> right);
else {
rotateR(T,N -> right -> left);
N -> right -> right -> height ++;
N -> right -> height ++;
rotateL(T,N -> right);
}
if (N -> weight > 1)
if (N -> left -> weight == 1) rotateR(T,N -> left);
else {
rotateL(T,N -> left -> right);
N -> left -> left -> height ++;
N -> left -> height ++;
rotateR(T,N -> left);
}
}
void rotateL(TREE *T,NODET *N) {
NODET *ptr,*par;
par = N -> parent;
if (par -> parent == NULL) {
T -> root = N;
N -> parent = NULL;
} else {
N -> parent = par -> parent;
if (par -> parent -> left == par) par -> parent -> left = N;
else par -> parent -> right = N;
}
par -> right = N -> left;
if (par -> right != NULL) par -> right -> parent = par;
par -> parent = N;
N -> left = par;
N -> weight = 0;
par -> height -=2;
par -> weight = 0;
}
void rotateR(TREE *T,NODET *N) {
NODET *ptr,*par;
par = N -> parent;
if (par -> parent == NULL) {
T -> root = N;
N -> parent = NULL;
} else {
N -> parent = par -> parent;
if (par -> parent -> left == par) par -> parent -> left = N;
else par -> parent -> right = N;
}
par -> left = N -> right;
if (par -> left != NULL) par -> left -> parent = par;
par -> parent = N;
N -> right = par;
N -> weight = 0;
par -> height -=2;
par -> weight = 0;
}
int maximum(int a,int b) {
if (a>b) return(a);
return(b);
}
#include <stdio.h>
#include <stdlib.h>
#define max(x,y) (x>y?x:y)
struct node{
long x,height;
struct node *left, *right;
};
struct node *root;
long hh(struct node *p){
if(p==NULL)return -1;
return p->height;
}
struct node* rLeft(struct node *p){
struct node *tmp = p->right;
p->right=p->right->left;
p->height=max(hh(p->left),hh(p->right))+1;
tmp->left=p;
tmp->height=max(hh(tmp->left),hh(tmp->right))+1;
return tmp;
}
struct node* rRight(struct node *p){
struct node *tmp = p->left;
p->left=p->left->right;
p->height=max(hh(p->left),hh(p->right))+1;
tmp->right=p;
tmp->height=max(hh(tmp->left),hh(tmp->right))+1;
return tmp;
}
struct node* rLeftRight(struct node *p){
p->left=rLeft(p->left);
return rRight(p);
}
struct node* rRightLeft(struct node *p){
p->right=rRight(p->right);
return rLeft(p);
}
struct node* insert(struct node *p,long x){
if(p==NULL){
p=(struct node*)malloc(sizeof(struct node));
p->x=x;
p->height=0;
p->left=NULL;
p->right=NULL;
}else if(x < p->x) {
p->left=insert(p->left,x);
if(hh(p->left)-hh(p->right)==2){
if(x < p->left->x){
p=rRight(p);
}else{
p=rLeftRight(p);
}
}
}else if(x > p->x){
p->right=insert(p->right,x);
if(hh(p->right)-hh(p->left)==2){
if(x > p->right->x){
p=rLeft(p);
}else{
p=rRightLeft(p);
}
}
}
p->height=max(hh(p->left),hh(p->right))+1;
return p;
}
void show(struct node*p,long lv){
long i;
if(p!=NULL){
show(p->right,lv+1);
for(i=1;i<=lv*4;i++)printf(" ");
printf("%ld\n\n",p->x);
show(p->left,lv+1);
}
}
int main(){
long x;
scanf("%ld",&x);
while(x!=0){
root=insert(root,x);
scanf("%ld",&x);
}
show(root,1);
getch();
}