AVLツリー実装(削除含む)
6535 ワード
インターネットで人を参考にして、テストをしていません.
#ifndef AVLTree_H
#define AVLTree_H
template<typename T>
class AVLTree
{
AVLTree();
AVLTree(const AVLTree & rhs);
~AVLTree();
const T & findMin() const;
const T & findMax() const;
bool contains(const T & x) const;
bool isEmpty() const;
void printTree() const;
void makeEmpty();
void insert(const T & x);
void remove(const T & x);
const AVLTree & operator=(const AVLTree & rhs);
private:
struct AVLNode
{
T element;
int height;
AVLNode * left;
AVLNode * right;
AVLNode(const T & theElement,AVLNode *lt = NULL,AVLNode *rt = NULL,int h = 0):element(theElement),left(lt),right(rt),height(h) {}
};
AVLTree * root;
int max(int a,int b)
{
return a > b ? a:b;
}
void insert(const T & x,AVLTree * &t) const
{
if(t == NULL)
t = new AVLNode(x);
else if(x < t->element)
{
insert(x,t->left);
if(height(t->left) - height(t->right) == 2)
{
if(x < t->element->left)
{
rotateWithLeftChild(t);
}
else
{
doubleWithLefrChild(t);
}
}
}
else if(x > t->element)
{
insert(x,t->right);
if(height(t->right) - height(t->left) == 2)
{
if(x > t->right->element)
rotateWithRightChild(t);
else
doubleWithRightChild(t);
}
}
else
t -> height = max(height(t->left),height(t->right) ) +1;
}
void remove(const T & x,AVLNode * &t) const
{
if(t == NULL)
return ;
if(x == t->element)
{
if(t->right == NULL) // t
{
AVLNode* temp = t;
t = t->left;
delete temp;
}
else // , t->right ( t )
{
AVLNode* temp = t->right;
t->element = findMin(temp)->element;
t->right = remove(t->element,t->right);
t->height = max(height(t->left),height(t->right)) + 1;
}
return t;
}
else if(x < t->element)
t->left = remove(x,t->left);
else
t->right = remove(x,t->right);
t->height = max(height(t->left),height(t->right)) + 1;
if(t->left != NULL)
t->left = rotate(t->left);
if(t->right != NULL)
t->right = rotate(t->right);
t = rotate(t);
return t;
}
AVLNode * findMin(AVLNode * t) const
{
if(t == NULL)
return NULL;
else
{
while(t->left != NULL)
t = t->left;
return t;
}
}
AVLNode * findMax(AVLNode * t) const
{
if(t == NULL)
return NULL;
else
{
while(t->right != NULL)
t = t->right;
return t;
}
}
bool contains(const T & x,AVLNode *t) const
{
if(t == NULL)
return false;
else if(x < t->element)
return contains(x,t->left);
else if(c > t->element)
return contains(x,t->right);
else
return true;
}
void makeEmpty(AVLNode *t) const
{
if(t == NULL)
;
else
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
t = NULL;
}
}
AVLNode * clone(AVLNode * t) const
{
if(t == NULL)
return NULL;
else
return new AVLNode(t->element,clone(t->left),clone(t->right));
}
void printTree(AVLNode * &t) const
{//
cout << t->element << endl;
printTree(t->left);
printTree(t->right);
}
int height(AVLNode * t) const
{
return t == NULL ? -1 : t->height;
}
AVLNode* rotateWithLeftChild(AVLNode * & k2)
{
AVLNode * k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left),height(k2->right)) +1;
k1->height = max(height(k2->left),height(k2->right)) +1;
k2 = k1;
return k1;
}
AVLNode* doubleWithLeftChild(AVLNode * & k3)
{
rotateWithLeftChild(k3->left);
return rotateWithLeftChild(k3);
}
AVLNode* rotateWithRightChild(AVLNode * & k2)
{
AVLNode * k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k2->height = max(height(k2->right),height(k2->left)) +1;
k1->height = max(height(k2->right),height(k2->left)) +1;
k2 = k1;
return k1;
}
AVLNode* doubleWithRightChild(AVLNode * & k3)
{
rotateWithRightChild(k3->right);
return rotateWithRightChild(k3);
}
// AVL
AVLNode* rotate(AVLNode * t)
{
if(height(t->left) - height(t->right) == 2)
{
if(height(t->left->left) >= height(t->left->right))
t = rotateWithLeftChild(t);
else
t = doubleWithLeftChild(t);
}
else if(height(t->right) - height(t->left) == 2)
{
if(height(t->right->right) >= height(t->right->left))
t = rotateWithRightChild(t);
else
t = doubleWithRightChild(t);
}
return t;
}
};
#endif
#include "AVLTree.h"
#include <iostream>
using namespace std;
template<typename T>
AVLTree<T>::AVLTree()
{
root = NULL;
}
template<typename T>
AVLTree<T>::AVLTree(const AVLTree & rhs)
{
root = NULL;
*this = rhs;
}
template<typename T>
AVLTree<T>::~AVLTree()
{
makeEmpty();
}
template<typename T>
const T & AVLTree<T>::findMin() const
{
if(!isEmpty())
return findMin(root)->element;
}
template<typename T>
const T & AVLTree<T>::findMax() const
{
if(!isEmpty())
return findMax(root)->element;
}
template<typename T>
bool AVLTree<T>::contains(const T & x) const
{
return contains(x,root);
}
template<typename T>
bool AVLTree<T>::isEmpty() const
{
return root == NULL;
}
template<typename T>
void AVLTree<T>::printTree() const
{
if(isEmpty())
cout << "Empty tree." << endl;
else
printTree(root);
}
template<typename T>
void AVLTree<T>::makeEmpty()
{
makeEmpty(root);
}
template<typename T>
void AVLTree<T>::insert(const T & x)
{
insert(x,root);
}
template<typename T>
void AVLTree<T>::remove(const T & x)
{
remove(x,root);
}
/* Deep Copy*/
template<typename T>
const AVLTree<T> &AVLTree<T>::operator=(const AVLTree<T> & rhs)
{
if( this != &rhs )
{
makeEmpty();
root = clone(rhs.root);
}
return *this;
}