AVL Tree C語言實作

<img src="https://img-blog.csdn.net/20141016123222082" alt="" /><pre name="code" class="cpp">#ifndef _AVLTree_H
删除過程
Steps to consider when deleting a node in an AVL tree are the following:
1.If node X is a leaf or has only one child, skip to step 5. (node Z will be node X)
2.Otherwise, determine node Y by finding the largest node in node X's left sub tree (in-order predecessor) or the smallest in its right sub tree (in-order successor).
3.Replace node X with node Y (remember, tree structure doesn't change here, only the values). In this step, node X is essentially deleted when its internal values were overwritten with node Y's.
4.Choose node Z to be the old node Y.
5.Attach node Z's subtree to its parent (if it has a subtree). If node Z's parent is null, update root. (node Z is currently root)
6.Delete node Z.
7.Retrace the path back up the tree (starting with node Z's parent) to the root, adjusting the balance factors as needed.
           

struct Avlnode;
typedef struct Avlnode *Position;
typedef struct Avlnode *Avltree;

Avltree MakeEmpty(Avltree t);
Position Find(int x,Avltree t);
Position FindMin(Avltree t);
Position FindMax(Avltree t);
int height(Avltree t);
Avltree Insert(int x,Avltree t);
Avltree Delete(int x,Avltree t);
int Retrieve(Position p);


#endif

struct Avlnode{
	int n;
	Avltree left,right;
	int height;
};

Avltree MakeEmpty(Avltree t){
	if(t!=NULL){
		MakeEmpty(t->left);
		MakeEmpty(t->right);
		free(t);
	}
	return NULL;
}

Position Find(int x,Avltree t){
	while(t!=NULL){
		if(x == t->n) break;
		if(x<t->n)
			t = t->left;
		else t = t->right;
	}
	return t;
}

Position FindMin(Avltree t){
	while(t!=NULL&&t->left!=NULL){
		t = t->left;
	}
	return t;
}

Position FindMax(Avltree t){
	while(t!=NULL&&t->right!=NULL){
		t = t->right;
	}
	return t;
}

int height(Avltree t){
	if(t == NULL)
		return -1;
	else return t->height;
}

Avltree Insert(int x,Avltree t){
	if(t == NULL){
		t = (Avltree)malloc(sizeof(struct Avlnode));
		if(t == NULL){
			printf("Out of Space\n");
			return NULL;
		}
		t->left = t->right = NULL;
		t->height = 0;
		t->n = x;
	}
	else if(x<t->n){
		t->left = Insert(x,t->left);
		if(height(t->left)-height(t->right) == 2)
			if(x<t->left)
				t = SingleRotateLeft(t);
			else t = DoubleRotateLeft(t);
	}
	else if(x>t->n){
		t->right = Insert(x,t->right);
		if(height(t->right) - height(t->left) == 2)
			if(x>t->right)
				t = SingleRotateRight(t);
			else DoubleRotateRight(t);
	}
	t->height = height(t->left)>height(t->right)?height(t->left)+1:height(t->right) + 1;
	return t;
}

Position SingleRotateLeft(Avltree a){
	Avltree b;
	b = a->left;
	a->left = b->right;
	b->right = a;
	a->height = height(a->left)>height(a->right)?height(a->left)+1:height(a->right)+1;
	b->height = height(b->left)>height(b->right)?height(b->left)+1:height(b->right)+1;
	return b;
}

Position SingleRotateRight(Avltree a){
	Avltree b;
	b = a->right;
	a->right = b->left;
	b->left  = a;
	a->height = height(a->left)>height(a->right)?height(a->left)+1:height(a->right)+1;
	b->height = height(b->left)>height(b->right)?height(b->left)+1:height(b->right)+1;
	return b;
}

Position DoubleRotateLeft(Avltree a){
	a->left = SingleRotateRight(a->left);
	return SingleRotateLeft(a);
}

Position DoubleRotateRight(Avltree a){
	a->right = SingleRotateLeft(a->right);
	return SingleRotateRight(a);
}

int Retrieve(Position p){
	return p->n;
}


Avltree Delete(Avltree t,int x){
	Position p;
	if(t == NULL){
		printf("Can't find the element\n");
		return NULL;
	}
	if(t->n == x){
	if(t->left == NULL||t->right == NULL){
		if(t->left == NULL)
			p = t->right;
		else p = t->left;
		if(p){
			t->n = p->n;
			t->height = 0;
		}
		else p = t;
		free(p);
	}
	else{
		p = FindMax(t->left);
		t->n = p->n;
		t->left = Delete(t,p->n);
	}
	}
	else if(x<t->n){
		t->left = Delete(t->left,x);
		if(height(t->left)-height(t->right) == 2)
			if(x<t->left)
				t = SingleRotateLeft(t);
			else t = DoubleRotateLeft(t);
	}
	else if(x>t->n){
		t->right = Delete(t->right,x);
		if(height(t->right) - height(t->left) == 2)
			if(x>t->right)
				t = SingleRotateRight(t);
			else DoubleRotateRight(t);
	}
	t->height = height(t->left)>height(t->right)?height(t->left)+1:height(t->right) + 1;
	return t;
}