คุยกับผู้ใช้:Kie/AVL

//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();
}