AVL Tree 밸 런 스 이 진 트 리 기본 삽입 삭제 노드 기능 구현
12642 단어 데이터 구조 및 알고리즘
AVL 트 리 를 실현 하 는 것 은 주로 두 가지 기능 이다. 특정한 노드 를 삽입 하고 특정한 노드 를 삭제 하 는 것 이다.
AVL Tree 의 정의,
1. 이 진 트 리 입 니 다.
2. 각 노드 좌우 서브 트 리 의 높이 차이 (평형 인자) 의 차 이 는 최대 1 이다.
실현:
얻 은 이 진 트 리 를 균형 이 잡 힌 이 진 트 리 로 만 들 기 위해 서 는
먼저 BSTNode 에 노드 높이 를 계산 하 는 방법 getHeight () 를 추가 하여 두 노드 의 높이 가 2 차이 가 날 때 균형 파괴 로 간주한다.
int getHeight(){
if(this == NULL)
return 0;
if(left == NULL && right == NULL)
return 1;
else{
return 1 + max(left->getHeight(), right->getHeight());
}
}그 다음 에 불 균형 이 발생 하 는 네 가지 상황 에 대해 토론 하고 노드 (빨간색) 를 추가 합 니 다.
1） LL， 왼쪽 트 리 의 왼쪽 노드 에 새로 만 들 기
LL 코드 구현:
template
BSTNode* AVLTree::LL(BSTNode* &topNode){
BSTNode * leftSonNode = topNode->left;
topNode->left = leftSonNode->right;
leftSonNode->right = topNode;
return leftSonNode;
} 2） RR， 오른쪽 하위 트 리 의 오른쪽 노드 에 새로 만 들 기
RR 코드 구현:
template
BSTNode* AVLTree::RR(BSTNode* &topNode){
BSTNode *rightSonNode = topNode->right;
topNode->right = rightSonNode->left;
rightSonNode->left = topNode;
return rightSonNode;
}
3） LR， 왼쪽 트 리 의 오른쪽 노드 에 새로 만 들 기
LR 코드 구현:
template
BSTNode* AVLTree::LR(BSTNode* &topNode){
topNode->left = RR(topNode->left);
return LL(topNode);
}
4） RL， 오른쪽 트 리 의 왼쪽 노드 에 새로 만 들 기
RL 코드 구현:
template
BSTNode* AVLTree::RL(BSTNode* &topNode){
topNode->right = LL(topNode->right);
return RR(topNode);
}
삭제 작업 에 대해 매번 한 노드 를 삭제 한 후에 하위 노드 의 가장 왼쪽 노드 의 값 을 고려 하여 삭제 노드 를 교체 합 니 다. 그러나 주의해 야 할 것 은...
교체 한 후에 노드 를 수정 하여 각 노드 에 Rotate 작업 을 해 야 합 니 다. 특정한 노드 를 삭제 한 후에 균형 트 리 의 파 괴 를 처리 해 야 합 니 다.
다음은 Delete 함수 의 실현:
template
BSTNode* AVLTree::Delete(const Type& key){
return root = Delete(root, key);
}
template
BSTNode* AVLTree::Delete(BSTNode* &node, const Type &key){
if(node == NULL){
return NULL;
}
/**
* if we find the matched key,
* delete the matched node and replace it by the most left node
* of its right child
*/
else if(key == node->key){
if(!node->right){
BSTNode *newNode = node->left;
delete node;
return newNode;
}else{
BSTNode *secondMostLeftNode = node->right;
if(secondMostLeftNode->left == NULL){
return secondMostLeftNode;
}
while(secondMostLeftNode->left->left)
secondMostLeftNode = secondMostLeftNode->left;
BSTNode *mostLeftNode = secondMostLeftNode->left;
secondMostLeftNode->left->left = node->left;
secondMostLeftNode->left->right = node->right;
secondMostLeftNode->left = NULL;
return mostLeftNode;
}
}
//from bottom to the top
else if(key < node->key){
node->left = Delete(node->left, key);
}
else{
node->right = Delete(node->right, key);
}
if(node->left)
node->left = Rotate(node->left);
if(node->right)
node->right = Rotate(node->right);
node = Rotate(node);
return node;
}
/**
* Rotate one node and its sub tree
*/
template
BSTNode* AVLTree::Rotate(BSTNode* node){
if(node->left->getHeight() - node->right->getHeight() == 2){
if(node->left->left->getHeight() >= node->left->right->getHeight())
node = LL(node);
else
node = LR(node);
}
if(node->right->getHeight() - node->left->getHeight() == 2){
if(node->right->right->getHeight() >= node->right->left->getHeight())
node = RR(node);
else
node = RL(node);
}
return node;
} 그 다음 에 전체 밸 런 스 트 리 에 노드 를 삭제 하고 main 함수 에서 테스트 하 는 코드 를 삽입 합 니 다.
#include
#include
#include
using namespace std;
template
class AVLTree;
/**
* Binary Search Tree Node: BSTNode class
*/
template
class BSTNode{
friend class AVLTree;
private:
Type key;
BSTNode *left;
BSTNode *right;
public:
BSTNode(): left(NULL), right(NULL){}
BSTNode(const Type& key): key(key), left(NULL), right(NULL){}
Type getkey(){return key;}
int getHeight(){
if(this == NULL)
return 0;
if(left == NULL && right == NULL)
return 1;
else{
return 1 + max(left->getHeight(), right->getHeight());
}
}
void clear(){
if(this == NULL)
return;
left->clear();
right->clear();
delete this;
}
void Output_DLR(){ //Node -> left -> Right order
if(this != NULL){
cout << key << ", ";
left->Output_DLR();
right->Output_DLR();
}
}
};
/**
* AVLTree class
*/
template
class AVLTree{
private:
BSTNode *root;
public:
AVLTree(): root(NULL){}
BSTNode* Insert(BSTNode* &, const Type&);
BSTNode* Insert(const Type& );
BSTNode* Delete(BSTNode* &, const Type&);
BSTNode* Delete(const Type& );
BSTNode* Rotate(BSTNode* );
BSTNode* GetRoot();
BSTNode* LL(BSTNode* &);
BSTNode* LR(BSTNode* &);
BSTNode* RL(BSTNode* &);
BSTNode* RR(BSTNode* &);
void Clear();
void Output_DLR();
void Output_LRN();
};
template
BSTNode* AVLTree::LL(BSTNode* &topNode){
BSTNode * leftSonNode = topNode->left;
topNode->left = leftSonNode->right;
leftSonNode->right = topNode;
return leftSonNode;
}
template
BSTNode* AVLTree::RR(BSTNode* &topNode){
BSTNode *rightSonNode = topNode->right;
topNode->right = rightSonNode->left;
rightSonNode->left = topNode;
return rightSonNode;
}
template
BSTNode* AVLTree::LR(BSTNode* &topNode){
topNode->left = RR(topNode->left);
return LL(topNode);
}
template
BSTNode* AVLTree::RL(BSTNode* &topNode){
topNode->right = LL(topNode->right);
return RR(topNode);
}
template
BSTNode* AVLTree::GetRoot(){
return root;
}
template
BSTNode* AVLTree::Insert(const Type& key){
return Insert(root, key);
}
template
BSTNode* AVLTree::Insert(BSTNode* &node, const Type &key){
if(node == NULL){
return node = new BSTNode(key);
}
//from bottom to the top
else if(key < node->key){
Insert(node->left, key);
if(node->left->getHeight() - node->right->getHeight() == 2){
if(key < node->left->key)
node = LL(node);
else
node = LR(node);
}
}
else{
Insert(node->right, key);
if(node->right->getHeight() - node->left->getHeight() == 2){
if(key > node->right->key)
node = RR(node);
else
node = RL(node);
}
}
return node;
}
template
BSTNode* AVLTree::Delete(const Type& key){
return root = Delete(root, key);
}
template
BSTNode* AVLTree::Delete(BSTNode* &node, const Type &key){
if(node == NULL){
return NULL;
}
/**
* if we find the matched key,
* delete the matched node and replace it by the most left node
* of its right child
*/
else if(key == node->key){
if(!node->right){
BSTNode *newNode = node->left;
delete node;
return newNode;
}else{
BSTNode *secondMostLeftNode = node->right;
if(secondMostLeftNode->left == NULL){
return secondMostLeftNode;
}
while(secondMostLeftNode->left->left)
secondMostLeftNode = secondMostLeftNode->left;
BSTNode *mostLeftNode = secondMostLeftNode->left;
secondMostLeftNode->left->left = node->left;
secondMostLeftNode->left->right = node->right;
secondMostLeftNode->left = NULL;
return mostLeftNode;
}
}
//from bottom to the top
else if(key < node->key){
node->left = Delete(node->left, key);
}
else{
node->right = Delete(node->right, key);
}
if(node->left)
node->left = Rotate(node->left);
if(node->right)
node->right = Rotate(node->right);
node = Rotate(node);
return node;
}
/**
* Rotate one node and its sub tree
*/
template
BSTNode* AVLTree::Rotate(BSTNode* node){
if(node->left->getHeight() - node->right->getHeight() == 2){
if(node->left->left->getHeight() >= node->left->right->getHeight())
node = LL(node);
else
node = LR(node);
}
if(node->right->getHeight() - node->left->getHeight() == 2){
if(node->right->right->getHeight() >= node->right->left->getHeight())
node = RR(node);
else
node = RL(node);
}
return node;
}
template
void AVLTree::Clear(){
root->clear();
root = NULL;
}
template
void AVLTree::Output_DLR(){
if(!root)
cout << "EMPTY TREE! " << endl;
else
root->Output_DLR();
}
template
void AVLTree::Output_LRN(){
if(!root)
cout << "EMPTY TREE! " << endl;
else
root->Output_LRN();
}
//Test Main
int main() {
AVLTree *tree = new AVLTree();
cout << "First, Test Insert(key) funciton: " << endl;
cout << "Test LL : " << endl;
//test LL
tree->Insert(8);
tree->Insert(6);
tree->Insert(11);
tree->Insert(4);
tree->Insert(7);
tree->Insert(2);
cout << "DLR Output LL: " << endl;
tree->GetRoot()->Output_DLR();
tree->Clear();
//test RR
cout << endl << endl << "Test RR : " << endl;
tree->Insert(8);
tree->Insert(6);
tree->Insert(10);
tree->Insert(9);
tree->Insert(12);
tree->Insert(14);
cout << "DLR Output RR: " << endl;
tree->GetRoot()->Output_DLR();
tree->Clear();
//test LR
cout << endl << endl << "Test LR : " << endl;
tree->Insert(9);
tree->Insert(6);
tree->Insert(11);
tree->Insert(4);
tree->Insert(7);
tree->Insert(8);
cout << "DLR Output LR: " << endl;
tree->GetRoot()->Output_DLR();
tree->Clear();
//test RL
cout << endl << endl << "Test RL : " << endl;
tree->Insert(6);
tree->Insert(4);
tree->Insert(12);
tree->Insert(10);
tree->Insert(14);
tree->Insert(8);
cout << "DLR Output RL: " << endl;
tree->GetRoot()->Output_DLR();
tree->Clear();
//test Delete(const Type& )
cout << endl << endl << "Test Delete : " << endl;
tree->Insert(6);
tree->Insert(7);
tree->Insert(9);
tree->Insert(13);
tree->Insert(15);
tree->Insert(4);
tree->Insert(5);
tree->Insert(17);
tree->Insert(19);
tree->Insert(12);
tree->Insert(10);
tree->Insert(14);
tree->Insert(8);
cout << "DLR Output Before Delete: " << endl;
tree->Output_DLR();
tree->Delete(7);
cout << endl << "DLR Output After Delete: " << endl;
tree->Output_DLR();
tree->Clear();
return 0;
}
테스트 출력:
마지막 테스트 Delete 결과 에 대해 서 는 밸 런 스 트 리 의 변 화 를 관찰 할 수 있 습 니 다. 데 이 터 는 같 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 1000 개 노크 #6. ZigZag ConversionProblem 문제는 에서 빌리고 있지만, 예제를 보는 한 Paypal의 인터뷰에서 출제 된 것이 있다고 추측됩니다. Solution 지그재그에 나열한 다음 각 행을 t0 , t1 , t1 . 파이썬 버전 코드: 계...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
