二叉平衡ルックアップツリーAvlTree(C実装)
7541 ワード
1
——————————————————————————————
#ifndef _AVLTREE_H_
#define _AVLTREE_H_
#include <stdlib.h>
#include <iomanip>
#include <iostream>
typedef struct AvlNode *Position;
typedef Position AvlTree;
#define Element int
struct AvlNode
{
Element data;
int height;// 0, 1
AvlTree left;
AvlTree right;
};
static int Height(AvlTree avl);
void SwapAvlNode(Position *p1, Position *p2);
Position GetNotBalancedNode(AvlTree avl);
void MakeEmpty(AvlTree* pavl);
Position Find(Element x, AvlTree avl);
Position FindMin(AvlTree avl);
Position FindMax(AvlTree avl);
void Insert(Element x, AvlTree* pavl);
void Delete(Element x, AvlTree* pavl);
Element Retrieve(Position p);
void SingleRotateWithLeftLeft(Position *pK2);
void SingleRotateWithRightRight(Position *pK2);
void DoubleRotateWithLeftRight(Position *pK3);
void DoubleRotateWithRightLeft(Position *pK3);
void PrintTree(AvlTree avl, int Depth, int ctrl);
#endif
————————————————————————————————
#include "./AvlTree.h"
int Max(int a, int b)
{
if(a <= b)
return b;
return a;
}
void SwapAvlNode(Position *p1, Position *p2)
{
Position tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int Abs(int a)
{
if(a < 0) return -a;
return a;
}
static int Height(AvlTree avl)
{
if(NULL == avl)
return -1;
else
return avl->height;
}
Position GetNotBalancedNode(AvlTree avl)
{
if(NULL == avl)
return NULL;
else
{
if(Height(avl->left) - Height(avl->right) == Abs(2))//not balanced
return avl;
else
{
Position res = GetNotBalancedNode(avl->left);
if(NULL != res)//avl->left is not balanced
return res;
else
return GetNotBalancedNode(avl->right);
}
}
}
void MakeEmpty(AvlTree* pavl)
{
if(NULL != (*pavl))
{
MakeEmpty(&((*pavl)->left));
MakeEmpty(&((*pavl)->right));
free(*pavl);
*pavl = NULL;
}
}
Position Find(Element x, AvlTree avl)
{
Position pos = avl;
while(NULL != pos)
{
if(x < Retrieve(pos))
pos = pos->left;
else if(x > Retrieve(pos))
pos = pos->right;
else
break;
}
return pos;
}
Position FindMin(AvlTree avl)
{
while(NULL != avl && NULL != avl->left)
avl = avl->left;
return avl;
}
Position FindMax(AvlTree avl)
{
while(NULL != avl && NULL != avl->right)
avl = avl->right;
return avl;
}
void Insert(Element x, AvlTree* pavl)
{
if(NULL == (*pavl))
{
Position tmp = (Position)malloc(sizeof(struct AvlNode));
if(NULL == tmp)
return ;
tmp->data = x;
tmp->height = 0;
tmp->left = tmp->right = NULL;
*pavl = tmp;
}
else
{
if(x < Retrieve(*pavl))// *pavl
{
Insert(x, &((*pavl)->left));
if(Height((*pavl)->left) - Height((*pavl)->right) == 2)//
{
if(x < Retrieve((*pavl)->left))//
SingleRotateWithLeftLeft(pavl);
else//
DoubleRotateWithLeftRight(pavl);
}
}
else if(x > Retrieve(*pavl))// *pavl
{
Insert(x, &((*pavl)->right));
if(Height((*pavl)->right) - Height((*pavl)->left) == 2)//
{
if(x > Retrieve((*pavl)->right))//
SingleRotateWithRightRight(pavl);
else//
DoubleRotateWithRightLeft(pavl);
}
}
}
(*pavl)->height = Max(Height((*pavl)->left), Height((*pavl)->right)) + 1;
}
void Delete(Element x, AvlTree* pavl)
{
if(NULL == *pavl)
return ;
if(x < Retrieve((*pavl)))//go left
Delete(x, &((*pavl)->left));
else if(x > Retrieve((*pavl)))//go right
Delete(x, &((*pavl)->right));
else if(NULL != (*pavl)->left && NULL != (*pavl)->right)//*pavl has two children
{
// tmp->data x, tmp->data
Position tmp = FindMin((*pavl)->right);
(*pavl)->data = tmp->data;
Delete(tmp->data, &((*pavl)->right));
}
else//*pavl has none or one child
{
Position tmp = *pavl;
if(NULL == (*pavl)->left)//*pavl has right child
*pavl = (*pavl)->right;
else if(NULL == (*pavl)->right)//*pavl has left child
*pavl = (*pavl)->left;
free(tmp);
}
if(NULL != *pavl)// *pavl
{
(*pavl)->height = Max(Height((*pavl)->left), Height((*pavl)->right)) + 1;
if(2 == Height((*pavl)->left) - Height((*pavl)->right))//not balanced
{
if(NULL == (*pavl)->left->right)
SingleRotateWithLeftLeft(pavl);
else
DoubleRotateWithLeftRight(pavl);
}
else if(2 == Height((*pavl)->right) - Height((*pavl)->left))//not balance
{
if(NULL == (*pavl)->right->left)
SingleRotateWithRightRight(pavl);
else
DoubleRotateWithRightLeft(pavl);
}
}
}
Element Retrieve(Position p)
{
return p->data;
}
void SingleRotateWithLeftLeft(Position *pK2)
{
Position k2 = *pK2;
Position k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k1->height = Max(Height(k1->left), Height(k2)) + 1;
k2->height = Max(Height(k2->left), Height(k2->right)) + 1;
*pK2 = k1;
}
void SingleRotateWithRightRight(Position *pK2)
{
Position k2 = *pK2;
Position k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k1->height = Max(Height(k2), Height(k1->right)) + 1;
k2->height = Max(Height(k2->left), Height(k2->right)) + 1;
*pK2 = k1;
}
void DoubleRotateWithLeftRight(Position *pK3)
{
SingleRotateWithRightRight(&((*pK3)->left));
SingleRotateWithLeftLeft(pK3);
}
void DoubleRotateWithRightLeft(Position *pK3)
{
SingleRotateWithLeftLeft(&((*pK3)->right));
SingleRotateWithRightRight(pK3);
}
void PrintTree(AvlTree avl, int Depth, int ctrl)//ctrl:0=root 1=left 2=right
{
if(NULL != avl)
{
std::cout<<std::setw(Depth);
if(0 == ctrl)
std::cout<<"rt:";
else if(1 == ctrl)
std::cout<<"l";
else if(2 == ctrl)
std::cout<<"r";
std::cout<<avl->data<<std::endl;
PrintTree(avl->left, Depth+3, 1);
PrintTree(avl->right, Depth+3, 2);
}
}