AVL tree (binary balanced search tree) implemented in C/C++

At first, I thought it was very complicated and scary, but then I thought it was not so scary, it was just a switch of the left and right subtrees.

The principle of AVL rotation is no longer explained, do not understand their own Baidu search books to understand the principle of rotation. The following is part of the code to implement the AVL tree

The first is the construction of the tree structure

 struct tree
 {
    struct tree* ls;   / / left son
    struct tree* rs;   / / right son
    int siz,con,data,height;  // Size, content, data, height
 };
 typedef struct tree stu;
 typedef struct tree* ptr;
Copy the code

Here is the code implementation of the rotation

1. Left and right single turn

When the single spin is no longer explained, baidu search books to understand all kinds of situations.

 void left(ptr* now){             / / left
    ptr tmp=(*now)->rs;          // In fact, the essence is the replacement of left and right son
    (*now)->rs=tmp->ls;
    tmp->ls=*now;
    tmp->siz=(*now)->siz;
    pushup(*now),pushup(tmp);
    *now=tmp;
    return;
 }
Copy the code

void right(ptr* now){             / / right
    ptr tmp=(*now)->ls;
    (*now)->ls=*now;
    tmp->siz=(*now)->siz;
    pushup(*now),pushup(tmp);
    *now=tmp;
    return;
}
Copy the code

2. Insert, balance, refresh process

This balancing part of the code is the heart of AVL and it’s really just one more balancing operation than a normal binary search tree and you just write the binary search tree and you add the balancing operation

Insert -> Balance -> Refresh

void ins(ptr* now,int num)   // If you are careful to distinguish, it is just more judgment and balance than binary search tree
{
	if (*now==NULL)
	{
		*now=(ptr)malloc(sizeof(stu));
		(*now)->siz=(*now)->con=1;
		(*now)->data=num,(*now)->height=0;
		(*now)->ls=(*now)->rs=NULL; return;
	}
	if ((*now)->data==num)
	{
		(*now)->con++;
		pushup(*now); return;
	}
	if ((*now)->data>num) ins(&(*now)->ls,num);
	else ins(&(*now)->rs,num);
	pushup(*now); balance(now); return;
}
Copy the code

void balance(ptr *now)    // The balancing operation is invoked for different situations
{
	if (*now==NULL) return;
	if (h((*now)->ls)-h((*now)->rs)==2)
	{
		if (h((*now)->ls->ls)>h((*now)->ls->rs)) right(now);
		else left(&(*now)->ls),right(now); return;  
	}
	if (h((*now)->rs)-h((*now)->ls)==2)
	{
		if (h((*now)->rs->rs)>h((*now)->rs->ls)) left(now);
		else right(&(*now)->rs),left(now); return;
	}
	return;
}
Copy the code

 void pushup(ptr now){            // Reload is equivalent to rebuilding the tree
     if(now==NULL) return;        // Refresh the current tree height, data content, etc
     now->height=1;
     now->siz=now->con;
     now->siz+=size(now->ls);
     now->siz+=size(now->rs);
     if(h(now->ls)>h(now->ls))
        now->height+=h(now->ls); 
     else now->height+=h(now->rs);
     return;
 }
Copy the code

3. Balance after nodes are deleted

void del(ptr* now,int num)
{
	if (*now==NULL) return;
	if ((*now)->data==num)
	{
		if ((*now)->con>1) (*now)->con--;
		else
		{
			ptr cng=*now;
			if ((*now)->ls==NULL) *now=(*now)->rs,free(cng);
			else if ((*now)->rs==NULL) *now=(*now)->ls,free(cng);
			else
			{
				cng=(*now)->rs;
				while (cng->ls) cng=cng->ls;
				(*now)->data=cng->data;
				(*now)->con=cng->con,cng->con=1;
				del(&(*now)->rs,cng->data); }}}else
	{
		if ((*now)->data>num) del(&(*now)->ls,num);
		else del(&(*now)->rs,num);
	}
	pushup(*now); balance(now); return;
}

Copy the code

4. Print the AVL tree node

1. Preorder traversal

void print(ptr p)
{
	printf("data:%d,con:%d,",p->data,p->con);
	printf("siz:%d,h:%d ",p->siz,p->height);
	return;
}

void printfst(ptr now)
{
	if (now)
	{
		print(now);
		if (now->ls) printfst(now->ls);
		if (now->rs) printfst(now->rs);
	}
	else printf("NULL");
	return;
}
Copy the code

2. In order traversal

void printmid(ptr now)
{
	if (now)
	{
		if (now->ls) printmid(now->ls);
		print(now);
		if (now->rs) printmid(now->rs);
	}
	else printf("NULL");
	return;
}
Copy the code

3. Back-order traversal

void printlst(ptr now)
{
	if (now)
	{
		if (now->ls) printlst(now->ls);
		if (now->rs) printlst(now->rs);
		print(now);
	}
	else printf("NULL");
	return;
}
Copy the code

5. To summarize

This is the AVL tree for the linked list, and later we will add the array to implement the AVL tree, in general, it’s not too difficult, compared to the complex graph recursion, this is really more explicit, is the rotation -> balance -> refresh process. The double spin process will be added later. Also welcome everyone to study and exchange together.