C++AVL 트 리 의 전체 코드 구현
AVL 트 리 는 한 회전(single rotate)과 두 회전(double rotate)을 통 해 뿌리 노드 의 왼쪽 트 리 와 오른쪽 트 리 의 높이 차 이 를 1 을 초과 하지 않 는 균형 잡 힌 두 갈래 검색 트 리 입 니 다.이 는 두 갈래 검색 트 리 의 시간 복잡 도 를 효과적으로 낮 추어 O(log n)입 니 다.그렇다면 C++AVL 트 리 를 구현 하 는 코드 를 자세히 소개 한다.마지막 단 계 는 신뢰 할 수 있 는 코드 구현 을 제공 합 니 다.
여기에 코드 를 먼저 붙 여 주세요.
모두 에 게 주 는 충 고 는 반드시 제때에 실현 해 야 한다.그렇지 않 으 면 나중에 실현 하 는 데 더 많은 시간 이 걸 릴 것 이다.
/*
*
*
*
*
*/
// ,
#ifndef _AVLTREE_
#define _AVLTREE_
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define MAXFACTOR = 2;
template<class Key , class E>
class AVLNode
{
private:
Key key;
E value;
AVLNode<Key,E>* left;
AVLNode<Key,E>* right;
AVLNode<Key,E>* parent;
public:
AVLNode():left(nullptr),right(nullptr),parent(nullptr){}
AVLNode(Key _key,E _value , AVLNode<Key,E>* _parent = nullptr,AVLNode<Key,E>*_left = nullptr, AVLNode<Key,E>*_right = nullptr):
key(_key),value(_value),left(_left),right(_right),parent(_parent){}
bool isLeaf(){return left==nullptr && right == nullptr ;}
//
Key getKey() const { return key;}
void setKey(Key set) {key = set;}
E getValue() const { return value;}
void setValue(E set) {value = set;}
AVLNode<Key,E>* getLeft() { return left; }
void setLeft (AVLNode< Key,E >* set){ left = set;}
AVLNode<Key,E>* getRight() { return right;}
void setRight (AVLNode<Key,E>* set) {right = set ;}
AVLNode<Key,E>* getParent() {return parent;}
void setParent(AVLNode<Key,E>* set) { parent = set;}
};
template<class Key , class E>
class AVLTree
{
private:
AVLNode<Key,E>* root;
void clear(AVLNode<Key,E>* &r)
{
if(r==nullptr)return;
if(r->getLeft())clear(r->getLeft());
if(r->getRight())clear(r->getRight);
delete r;
}
void Init()
{
root = new AVLNode<Key,E>();
root=nullptr;
}
void preOrder(AVLNode<Key,E>* r,void(*visit) (AVLNode<Key,E> * node))
{
if(r==nullptr)return;
(*visit) (r);
preOrder(r->getLeft() , visit);
preOrder(r->getRight(), visit);
}
void inOrder(AVLNode<Key,E>* r , void(*visit)(AVLNode<Key,E>* node) )
{
if(r==nullptr)return;
inOrder(r->getLeft() , visit);
(*visit)(r);
inOrder(r->getRight(),visit);
}
void postOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
{
if(r==nullptr)return;
postOrder(r->getLeft(),visit);
postOrder(r->getRight(),visit);
(*visit)(r);
}
void levelOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
{
queue< AVLNode<Key,E>* > q;
if(r==nullptr)return;
q.push(r);
while( ! q.empty() )
{
AVLNode<Key,E>* tmp = q.front();
q.pop();
(*visit)(tmp);
if(tmp->getLeft() ) q.push(tmp->getLeft() );
if(tmp->getRight()) q.push(tmp->getRight());
}
}
AVLNode<Key,E>* find(AVLNode<Key,E>* r,Key k)
{
if(r==nullptr)return nullptr;
if(k == r->getKey() ) return r;
else if( k < r->getKey())
{
find(r->getLeft(),k);
}
else {
find(r->getRight(),k);
}
}
//Find the smallest element in the avl tree
AVLNode<Key,E>* getMin(AVLNode<Key,E>* r)
{
if(r->getLeft() == nullptr) return r;
else{
getMin(r->getLeft());
}
}
//Remove the smallest element
AVLNode<Key,E>* deleteMin(AVLNode<Key,E>* rt)
{
if(rt->getLeft() == nullptr) return rt->getRight();
else{
rt->setLeft(deleteMin(rt->getLeft()));
return rt;
}
}
AVLNode<Key,E>* leftRotate(AVLNode<Key,E>* node)
{
if( node == nullptr) return nullptr;
AVLNode<Key,E>* newHead = node->getRight();
node->setRight( newHead -> getLeft() );
newHead -> setLeft( node );
return newHead;
}
AVLNode<Key,E>* rightRotate(AVLNode<Key,E>* node)
{
if(node == nullptr)return nullptr;
AVLNode<Key,E>* newHead = node->getLeft();
node->setLeft( newHead->getRight() );
newHead ->setRight(node);
return newHead;
}
int getHeight(AVLNode<Key,E>*node)
{
if(node == nullptr)return 0;
if(node->isLeaf())return 1;
else return ( getHeight( node->getLeft() ) > getHeight( node->getRight() ) ?
getHeight( node->getLeft() ) : getHeight( node->getRight() ) ) + 1;
}
int getBalanceFactor(AVLNode<Key,E>* node)
{
return getHeight(node->getLeft()) - getHeight(node->getRight() );
}
AVLNode<Key,E>* balance(AVLNode<Key,E>* node)
{
if(!node) return nullptr;
else if ( getBalanceFactor( node ) == 2)
{
if(getBalanceFactor( node ->getLeft() ) == 1)
{
node = rightRotate(node);
}
else
{
node->setLeft(leftRotate( node->getLeft() ) );
node = rightRotate(node);
}
}
else if(getBalanceFactor( node ) == -2)
{
if(getBalanceFactor( node->getRight()) == -1)
{
node = leftRotate(node);
}
else
{
node->setRight( rightRotate( node->getRight() ) );
node = leftRotate(node);
}
}
return node;
}
AVLNode<Key,E>* insert( AVLNode<Key,E>* root ,const pair<Key,E>& it)
{
if(root == nullptr)
{
return new AVLNode<Key,E>(it.first , it.second,NULL,NULL,NULL);
}
else if (it.first < root->getKey() )
{
root ->setLeft( insert(root->getLeft() , it) ) ;
}
else{
root ->setRight( insert(root->getRight() , it) );
}
root = balance(root);
return root;
}
AVLNode<Key,E>* remove(AVLNode<Key,E>* node , const Key k)
{
if(node == nullptr) return nullptr;
if(node->getKey() > k)
{
node->setLeft( remove(node->getLeft() , k) );
node = balance(node);
}
else if(node->getKey() < k)
{
node->setRight( remove(node->getRight(), k) );
node = balance(node);
}
else if(node->getKey() == k)
{
if(! node->isLeaf() )
{
AVLNode<Key,E>* tmp = getMin(node->getRight() );
node->setKey( tmp->getKey() );
node->setValue( tmp->getValue() );
node->setRight( deleteMin(node->getRight() ) );
delete tmp;
}
else {
AVLNode<Key,E>* tmp = node;
node = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight() ;
delete tmp;
}
}
return node;
}
public:
~AVLTree(){clear(root);}
AVLTree(){/*Init();*/ root = nullptr; }
//
void preOrder( void (*visit)(AVLNode<Key,E>* r))
{
preOrder(root,visit);
}
void inOrder(void (*visit)(AVLNode<Key,E>* r))
{
inOrder(root,visit);
}
void postOrder(void (*visit)(AVLNode<Key,E>* r))
{
postOrder(root,visit);
}
void levelOrder( void(*visit)(AVLNode<Key,E>*r) )
{
levelOrder(root,visit);
}
//
void insert(const pair<Key,E> &it)
{
root = insert(root,it);
}
//
void remove(const Key& k)
{
remove(root,k);
}
bool find(const Key&k)
{
return find(root,k);
}
};
#endif
//AVLtest.cpp
#include"NewAvl.h"
#include<iostream>
using namespace std;
template<typename Key,typename E>
void traverse(AVLNode<Key,E>* root)
{
cout<<root->getKey()<<" "<<root->getValue()<<" ";
cout<<endl;
}
int main()
{
AVLTree<int,int>* tree = new AVLTree<int ,int>;
for(int i = 0 ; i < 5 ; i ++)
{
tree->insert(make_pair(i,i));
}
tree->remove(1);
cout<<"PreOrder: "<<endl;
tree->preOrder(traverse);
cout<<endl;
cout<<"LevelOrder: "<<endl;
tree->levelOrder(traverse);
cout<<endl;
cout<<"InOrder: "<<endl;
tree->inOrder(traverse);
cout<<endl;
cout<<"PostOrder: "<<endl;
tree->postOrder(traverse);
cout<<endl;
cout<<tree->find(2)<<endl;
tree->insert(make_pair(9,9));
tree->levelOrder(traverse);
}
실행 결과이상 은 C++AVL 트 리 의 전체 코드 를 실현 하 는 상세 한 내용 입 니 다.C+AVL 트 리 에 관 한 더 많은 자 료 는 저희 의 다른 관련 글 을 주목 하 세 요!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Visual Studio에서 파일 폴더 구분 (포함 경로 설정)Visual Studio에서 c, cpp, h, hpp 파일을 폴더로 나누고 싶었습니까? 어쩌면 대부분의 사람들이 있다고 생각합니다. 처음에 파일이 만들어지는 장소는 프로젝트 파일 등과 같은 장소에 있기 때문에 파일...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.