알고리즘 -- AVL 트 리 삭제

AVL 트 리 삭제
정의.
AVL 트 리 는 균형 인자 가 - 1, 1, 0 인 이 진 트 리 로 균형 인자 가 2 이면 균형 화 를 해 야 한다.균형 화 과정 은 좌회전 이나 우회전, LL, LR, RR, RL4 가지 상황 이다.
성능:
높이: log (n), 최 악의 경우 O (logn) 회 를 비교 해 야 합 니 다.다른 밸 런 스 트 리 와 달리 한 노드 에 불 균형 이 생기 면 나무 전체 에 영향 을 줄 수 있다.
과정, 예 를 들 어 하나의 배열 은 5, 6, 8, 3, 2, 4, 7 이다.길이그러면 삽입 한 경 우 는 요.
정 의 된 머리 는:

#define NULL    0
template
class AVL_Node//AVL      
{
public:
	T key;
	AVL_Node* leftChild;
	AVL_Node *rightChild;
	AVL_Node *parent;//    AVL               
	AVL_Node(T key)
	{
		this->key=key;
		leftChild=NULL;
		rightChild=NULL;
		parent=NULL;
	}
};

template
class AVL_Tree//AVL      
{
public:
	int nodeNum;
	AVL_Node *root;
	AVL_Tree()
	{
		nodeNum=0;
		root=NULL;
	}
	void AVL_TREE_INSERT(AVL_Tree*avlTree,T key);//  
	void AVL_TREE_DELETE(AVL_Tree*avlTree,T key);//  
	bool RotateRight(AVL_Tree*avlTree,AVL_Node*node);//  
	bool RotateLeft(AVL_Tree*avlTree,AVL_Node*node);//  
	int AVL_TREE_HIGH(AVL_Node*node);//      
	AVL_Node* AVL_TREE_SEARCH(T key);
	void AVL_TREE_BALANCE(AVL_Tree*avlTree,AVL_Node* node);
};

삭 제 된 코드:
가장 중요 한 것 은 삭제 할 결점 을 찾 는 것 이다.이 결점 은 원래 의 결점 일 수도 있 고, 전구 결점 일 수도 있다.
결점 을 삭제 할 아이의 결점 을 찾 아 지침 을 정확하게 복사 합 니 다.
구체 적 인 코드:

template//    
void AVL_Tree::AVL_TREE_DELETE(AVL_Tree*avlTree,T key)
{
	//  ：1、      
	//2、       。      。
	//3、     
	AVL_Node*index=avlTree->root;
	AVL_Node*delNodeChild=NULL;

	while (index)//      ，           
	{
		if (key==index->key)
		{
			break;
		}
		else if (index->leftChild&&keykey)
		{
			index=index->leftChild;
		}
		else if(index->rightChild&&key>index->key)
		{
			index=index->rightChild;
		}
	}
	AVL_Node*delNode=index;//           ，      。
	if (index->leftChild==NULL||index->rightChild==NULL)
	{
		delNode=index;
	}
	else  //        。
	{   //               ，    
		delNode=index->leftChild;
		while(delNode->rightChild)//        ，           。
		{
			delNode=delNode->rightChild;
		}
	}
   //                   ，                 ，             ，
	//            
	if (delNode->leftChild)
	{
		delNodeChild=delNode->leftChild;
	}
	if(delNode->rightChild)
	{
		delNodeChild=delNode->rightChild;
	}
	if (delNodeChild)// deleteNode      ，              。
	{
		delNodeChild->parent=delNode->parent;
	}
	if (delNode->parent==NULL)//            ，             ，          NULL
	{
		avlTree->root=delNodeChild;
	}
	else//              。            ，             ，
	{   //       delNode ，  delete,          ，       ，          
		if (delNode==delNode->parent->leftChild)
		{
			delNode->parent->leftChild=delNodeChild;
		}
		else if (delNode==delNode->parent->rightChild)
		{
			delNode->parent->rightChild=delNodeChild;
		}
	}
	if (index!=delNode)//                   
	{
		index->key=delNode->key;//      。
	}
	if (nodeNum>2)//       2           
	{
		AVL_TREE_BALANCE(avlTree,delNode->parent);//                 
	}
	//delete delNode;
	nodeNum--;	
}


int main()
{
	AVL_Tree*avlTree=new AVL_Tree();
	int testArray[7]={5,6,8,3,2,4,7};
	for (int i=0;i<7;i++)
	{
		avlTree->AVL_TREE_INSERT(avlTree,testArray[i]);

	}
	for (int i=0;i<7;i++)
	{
		avlTree->AVL_TREE_DELETE(avlTree,testArray[i]);
	}
	return 0;
}

균형 화 된 코드 는 앞의 삽입 코드 를 보십시오
소결:
1. 결점 을 삭제 해 야 하 는 아이의 결점 이 비어 있어 야 한다 고 생각 합 니 다. 이때 아버지의 결점 을 가 진 아이의 결점 은 바로 NULL 입 니 다.
2. 결점 을 삭제 해 야 하 는 아버지의 결점 은 비어 있 습 니 다.그러면 아 이 는 결점 을 근점 으로 한다.
3. 균형 결점 은 아버지 결점 은 현재 하나의 결점 만 있 는 상황 을 고려 해 야 한다.
4. 삭 제 를 기다 리 는 노드 로 사용 되 지만 오른쪽 트 리 만 있 는 경우 가 있 기 때문에 삭 제 를 기다 리 는 노드 에 왼쪽 트 리 가 존재 하지 않 으 면 오른쪽 트 리 를 가리 키 는 것 입 니 다.
처음에는 prev 지침 을 사 용 했 지만 delNode 를 사용 하지 않 았 습 니 다. 고려 해 야 할 상황 이 더 많 았 습 니 다.
첫 번 째 로 중요 한 것 은 야생 지침 입 니 다. delNode 가 없 으 면 지침 이 가리 키 는 공간 이 삭제 되 었 지만 지침 의 값 은 아래 코드 와 같이 존재 합 니 다.

          int * pp = new int;
	   int *ppp=pp;
           *pp = 16;
	   int *&p=pp;
	   delete p;
	   p=NULL;

이때 p 를 비 워 두 고 포인터 가 존재 하지 않 습 니 다. 그런데 pp 는 요?그래서 * & ppp = pp 를 정확하게 삭제 할 수 있 습 니 다.그 다음 에 Null 로 설정 되 어 있 습 니 다.
이것 이 바로 지침 과 지침 만 인용 하 는 것 과 다르다.그러나 우리 프로그램 에 서 는 포인터 A 의 값 만 얻 었 기 때문에 가리 키 는 공간의 내용 을 비 울 수 있 지만 A 의 값 은 비어 있 지 않 습 니 다.이때 A 가 야 지침 이다.