Hiệu chỉnh lại chỉ số cân bằng sau khi quay kép trên cây AVL

[Luan_Truong (Luân Trường)]

#include <iostream>
#include <stdlib.h>
using namespace std ;
struct nodetype{
	int key ;
	int info ;
	int bf ; // balance factor : chi so can bang
	nodetype *left , *right ;
};
typedef nodetype* NODEPTR ;

void initialize(NODEPTR &root){
	root=NULL ;
}

NODEPTR Rotate_left(NODEPTR root ){
	NODEPTR p ;
	if(root==NULL){
		cout<<"Khong the quay cay vi cay bi rong\n";
	}
	else
	{
		if(root->right=NULL){
			cout<<"Khong the quay trai vi khong co cay con phai\n";
		}
		else{
			p=root->right ;
			root->right=p->left ;
			p->left=root ;
		}	
	}
	return p ;
}

NODEPTR Rotate_right(NODEPTR ya){ // thay ya bang root
	NODEPTR s ; // thay s = p
	if(ya==NULL){
		cout<<"Khong the quay cay vi cay bi rong\n";
	}
	else{
		if(ya->left==NULL){
			cout<<"Khong the quay phai vi khong co cay con trai\n";
		}
		else{
			s=ya->left ;
			ya->left=s->right ;
			s->right=ya ;
		}
	}
}

void Insert_tree(NODEPTR &root , int x , int a){ // x va a lan luot la khoa va info cua node la can then
	NODEPTR fp , p , q    // fp la cha cua p , q la con cua p
	fya , ya     // ya la nut truoc gan nhat cua nut bi mat can bang , fya la cha cua ya 
	s ;// la con cua ya
	int imbal ; /*
					1: khi lech ben trai
					0: 2 nhanh bang nhau
					-1: lech ben phai
					bien imbal : xac dinh huong lech
				*/ 
	//Khoi tao cac gia tri
	fp=NULL , p=root ;
	fya=NULL ; ya=p ;
	// Tim vi tri can them node moi va xac dinh vi tri cua ya , fa
	while(p!=NULL){
		if(x==q->key) return ; // bi trung khoa
		if(x<p->key) q=p->left ;
		else q=p->right ;
		if(q!=NULL){
			if(q->bf!=0){ // bien can bang trong q = 1 || =-1 
			fya=p ;
			ya=q ;
			}
		}	
		fp=p ;
		p=q ;
	}
	// Ket thuc vong while o tren thi p,q = NULL 
	p= new nodetype ; p->info = a , p->key=x , p->bf=0 ;
	p->left=NULL , p->right=NULL ;
	// Lien ket them p vao cay
	if(x<fp->key) fp->left=p ;
	else fp->right=p ;
	/* Hieu chinh chi so can bang cac nut giua ya va q
		Neu bi lech ve phia trai thi chi so can bang = 1 
		Neu bi lech ve phia phai thi chi so can bang =-1  
	*/
	if(x<ya->key) p=ya->left ;
	else p=ya->right ;
	s=p ; // s la con cua ya
	//---Bat dau di hieu chinh chi so can bang
	while(p!=q){
		if(x<p->left){
			p->bf=1 ;
			p=p->left ;
		}
		else{
			p->bf=-1 ;
			p=p->right ;
		}
	}
	// Xac dinh huong lech
	if(x<ya->key) imbal=1 ;
	else imbal =-1 ;
	// Tu chi so can bang cua ya ban dau de tu do => co can can bang lai cay hay khong
	// TH1: ya->key=0 :du them vao ben trai hay ben phai thi cay cung can bang => khong can can bang lai cay nhi phan tim kiem
	//Truoc khi return nho hieu chinh lai chi so can bang cua ya
	if(ya->bf==0) {
		ya->bf=imbal ;
		return ;	
	}
	//TH2 : ya bi lech sang ben trai , them node vao ben phai  ya->bf=1 va imbal=-1
	//		ya bi lech sang ben phai , them node vao bne trai  ya->bf=-1 va imbal = 1
	//   => Sau khi them sau thi khong can can bang lai cay 
	// Truoc khi return nho hieu chinh lai chi so can bang cua ya
	if(ya->bf!=imbal) {
		ya->bf=0 ;
		return ;	
	}
	//TH3 : ya->bf=imbal 
	if(s->bf==imbal){
		if(imbal==1) p=Rotate_left(ya) ; // Quay trai
		else p=Rotate_right(ya) ; // Quay phai
		// hieu chinh lai chi so can bang sau khi quay 
		ya->bf=0 ;
		s->bf=0 ;
	}
	else{ // Quay kep
		if(imbal==1){ // Quay trai - phai
			ya->left=Rotate_left(s) ;
			p = Rotate_right(ya) ;
		}
		else{ // Quay phai - trai
			ya->right=Rotate_right(s) ;
			p=Rotate_left(ya) ;
		} 
		// Sau khi quay xong thi tiep tuc hieu chinh chi so can bang
		if(p->bf==0){ // truong hop p la nut moi them vao
			ya->bf=0;
			s->bf=0 ;
		}
		else{
			if(p->bf==imbal){
				ya->bf=-imbal ;
				s->bf = 0 ;
			}
			else{
				ya->bf=0 ;
				s->bf=imbal ;
			}
			p->bf=0 ;
		}	
	}
	if(fya==NULL) root=p ;
	else{
		if(ya==fya->left) 
			fya->left=p;
		else
			fya->right=p;
	}
}
int main(){
	NODEPTR root ;
	initialize(root) ;
}

Em không hiểu đoạn hiệu chỉnh lại chỉ số cân bằng sau khi quay kép này , mn giải thích cho em với ạ , em cảm ơn!

// Sau khi quay xong thi tiep tuc hieu chinh chi so can bang
		if(p->bf==0){ 
			ya->bf=0;
			s->bf=0 ;
		}
		else{
			if(p->bf==imbal){
				ya->bf=-imbal ;
				s->bf = 0 ;
			}
			else{
				ya->bf=0 ;
				s->bf=imbal ;
			}
			p->bf=0 ; // Sau khi quay kep thi nhanh trai bang nhanh phai
		}