#ifndef AVL_TREE_H
#define AVL_TREE_H
#include <cassert>
#include <algorithm>
#ifdef _PRINT
#include <vector>
#include <iostream>
#include <memory>
#include <functional>
#endif // _PRINT
namespace ghost{
/// AVL树
template<typename ComparableT>
class AVLTree{
public:
typedef ComparableT DataType;
private:
/// 节点,缓存了自身的高度
struct Node_{
DataType data; // 可进行比较的数据
Node_* pLeftChild; // 指向左儿子
Node_* pRightChild; // 指向右儿子
int height; // 作为根节点的树高度,
Node_()
: pLeftChild(0)
, pRightChild(0)
, height(0) // 约定叶子高度为0,故节点高度初始化为0
{
}
explicit Node_(const DataType& d)
: data(d)
, pLeftChild(0)
, pRightChild(0)
, height(0) // 约定叶子高度为0,故节点高度初始化为0
{
}
Node_(const Node_&) = delete;
Node_& operator =(const Node_&) = delete;
};
Node_* pRoot_; // 指向根节点
public:
/// 默认初始化为空树
AVLTree()
: pRoot_(0)
{
#ifdef _PRINT
std::cout<<"创建AVL树"<<std::endl;
#endif // _PRINT
}
~AVLTree()
{
Clear();
}
AVLTree(const AVLTree&) = delete;
AVLTree& operator =(const AVLTree&) = delete;
public:
/// 获取树高度,空树返回-1,只有个节点返回0
int GetHeight() const{return GetHeight_(pRoot_);}
#ifdef _PRINT
/// 打印者,即需要打印的对象
class Printer{
public:
virtual ~Printer(){}
public:
virtual void Print() const{}
virtual bool IsValid() const{return false;}
};
typedef std::shared_ptr<Printer> PSharedPrinter; // 打印者共享指针
typedef std::vector<PSharedPrinter> PrinterContainer; // 打印者共享指针的容器
/// 节点打印者
class NodePrinter : public Printer{
Node_* pNode_;
size_t width_;
PrinterContainer& nextPrinters_;
public:
NodePrinter(Node_* p, PrinterContainer& printers)
: pNode_(p)
, width_(0)
, nextPrinters_(printers)
{
assert(pNode_);
UpdateWidth();
}
virtual ~NodePrinter(){}
NodePrinter(const NodePrinter&) = delete;
NodePrinter& operator =(const NodePrinter&) = delete;
public:
void UpdateWidth()
{
width_ = CalcDataWidth_(pNode_->data);
}
virtual void Print() const
{
// 计算左右子树宽度
size_t leftChildWidth = CalcWidth_(pNode_->pLeftChild);
size_t rightChildWidth = CalcWidth_(pNode_->pRightChild); // +1是为了将数据隔开
// 打印左边空白
for (size_t i = 0; i < leftChildWidth; ++i)
{
std::cout<<' ';
}
// 打印节点
std::cout<<"["<<pNode_->data<<"]";
// 打印右边空白
for (size_t i = 0; i < rightChildWidth; ++i)
{
std::cout<<' ';
}
// 将左儿子放入下一层需要打印的节点集合中
if (pNode_->pLeftChild)
{
nextPrinters_.push_back(PSharedPrinter(new NodePrinter(pNode_->pLeftChild, nextPrinters_)));
}
// 将自身所占空位放入下一层需要打印的节点集合中
nextPrinters_.push_back(PSharedPrinter(new BlankPrinter(width_)));
// 将右儿子放入下一层需要打印的节点集合中
if (pNode_->pRightChild)
{
nextPrinters_.push_back(PSharedPrinter(new NodePrinter(pNode_->pRightChild, nextPrinters_)));
}
// 将自身所占空位放入下一层需要打印的节点集合中
nextPrinters_.push_back(PSharedPrinter(new BlankPrinter(width_)));
}
virtual bool IsValid() const{return true;}
};
/// 空白打印者,主要完成打印父节点所占用的空白
class BlankPrinter : public Printer{
size_t count_;
public:
explicit BlankPrinter(size_t c) : count_(c){}
virtual ~BlankPrinter(){}
public:
virtual void Print() const
{
for (size_t i = 0; i < count_; ++i)
{
std::cout<<' ';
}
}
};
/// 广度优先打印节点,目前只支持打印int型数据
void Print() const
{
std::cerr<<"不支持打印的数据类型:"<<typeid(DataType).name()<<"\n";
}
private:
/// 计算十进制数位数
static size_t CalcDataWidth_(int n)
{
assert(false);
}
/**
计算树宽度
因为约定空树宽度为0,叶子宽度为1,所以树宽度等于左右子树宽度和+数据所占的位数
*/
static size_t CalcWidth_(const Node_* pRoot)
{
if (!pRoot)
{
return 0;
}
return CalcWidth_(pRoot->pLeftChild) + CalcWidth_(pRoot->pRightChild) + CalcDataWidth_(pRoot->data);
}
#endif // _PRINT
public:
/// 插入数据
void Insert(const DataType& data)
{
#ifdef _PRINT
std::cout<<"插入数据:"<<data<<std::endl;
#endif // _PRINT
Insert_(data, pRoot_);
}
/// 删除数据
void Erase(const DataType& data)
{
#ifdef _PRINT
std::cout<<"删除数据:"<<data<<std::endl;
#endif // _PRINT
Erase_(data, pRoot_);
}
/// 清空
void Clear()
{
#ifdef _PRINT
std::cout<<"清空"<<std::endl;
#endif // _PRINT
// 销毁所有节点
RecursDestroyNode_(pRoot_);
pRoot_ = 0;
}
private:
/// 创建节点
static Node_* CreateNode_(const DataType& data)
{
return new Node_(data);
}
/// 销毁节点
static void DestroyNode_(Node_* pNode)
{
delete pNode;
}
/// 递归销毁节点
static void RecursDestroyNode_(Node_* pNode)
{
if (pNode)
{
// 先递归销毁子节点
RecursDestroyNode_(pNode->pLeftChild);
RecursDestroyNode_(pNode->pRightChild);
// 再销毁自身
DestroyNode_(pNode);
}
}
/// 获取树高度,约定空树高度为-1
static int GetHeight_(const Node_* pRoot)
{
return pRoot ? pRoot->height : -1;
}
/**
计算树高度
因为约定空树高度为-1,叶子高度为0,所以树高度等于左右子树较高者高度+1
*/
static int CalcHeight_(const Node_* pRoot)
{
assert(pRoot); // 断言树存在
return std::max(GetHeight_(pRoot->pLeftChild), GetHeight_(pRoot->pRightChild)) + 1;
}
/**
与子树进行单旋转
由于旋转后节点将成为其原儿子的儿子,故节点指针pNode将会指向其原儿子
pChild1指向被旋转的儿子成员指针,pChild2指向另一个儿子成员指针
*/
static void SingleRatateWithChild_(Node_*& pNode, Node_* Node_::* pChild1, Node_* Node_::* pChild2)
{
assert(pChild1 && pChild2); // 断言成员变量指针有效
assert(pNode); // 断言节点存在
// 节点的儿子1重定向于儿子1的儿子2
Node_* pOriginalChild = pNode->*pChild1;
pNode->*pChild1 = pOriginalChild->*pChild2;
// 节点的原儿子1的儿子2重定向于节点
pOriginalChild->*pChild2 = pNode;
// 旋转之后需要重新计算高度
pNode->height = CalcHeight_(pNode);
pOriginalChild->height = CalcHeight_(pOriginalChild);
// pNode指向其原儿子
pNode = pOriginalChild;
}
/// 与左子树进行单旋转
static void RotateWithLeftChild_(Node_*& pNode)
{
SingleRatateWithChild_(pNode, &Node_::pLeftChild, &Node_::pRightChild);
}
/// 与右子树进行单旋转
static void RotateWithRightChild_(Node_*& pNode)
{
SingleRatateWithChild_(pNode, &Node_::pRightChild, &Node_::pLeftChild);
}
/**
与子树进行双旋转
由于旋转后节点将成为其原儿子的儿子,故节点指针pNode将会指向其原儿子
pChild1指向被旋转的儿子成员指针,pChild2指向另一个儿子成员指针
*/
static void DoubleRatateWithChild_(Node_*& pNode, Node_* Node_::* pChild1, Node_* Node_::* pChild2)
{
assert(pChild1); // 断言成员变量指针有效
// 先对儿子进行一次旋转
SingleRatateWithChild_(pNode->*pChild1, pChild2, pChild1);
// 再对自己进行一次旋转
SingleRatateWithChild_(pNode, pChild1, pChild2);
}
/// 与左子树进行双旋转
static void DoubleRotateWithLeftChild_(Node_*& pNode)
{
DoubleRatateWithChild_(pNode, &Node_::pLeftChild, &Node_::pRightChild);
}
/// 与右子树进行双旋转
static void DoubleRotateWithRightChild_(Node_*& pNode)
{
DoubleRatateWithChild_(pNode, &Node_::pRightChild, &Node_::pLeftChild);
}
/**
确定左子树是否过高(破坏了AVL平衡条件),是则与其进行旋转
当在左子树中插入新节点,或者在右子树中删除节点时使用
*/
static void RatateWithLeftChildIfNeed_(Node_*& pNode)
{
// AVL平衡条件为左右子树高度相差不超过1
// 左子树比右子树高2,需要通过旋转来使之重新达到AVL平衡条件
if (2 == GetHeight_(pNode->pLeftChild) - GetHeight_(pNode->pRightChild))
{
if (GetHeight_(pNode->pLeftChild->pLeftChild) > GetHeight_(pNode->pLeftChild->pRightChild))
{
// 左子树的左子树高于左子树的右子树,应当与左子树进行单旋转
RotateWithLeftChild_(pNode);
}
else
{
// 左子树的右子树高于左子树的左子树,应当与左子树进行双旋转
DoubleRotateWithLeftChild_(pNode);
}
}
}
/**
确定右子树是否过高(破坏了AVL平衡条件),是则与其进行旋转
当在右子树中插入新节点,或者在左子树中删除节点时使用
*/
static void RatateWithRightChildIfNeed_(Node_*& pNode)
{
// AVL平衡条件为左右子树高度相差不超过1
// 右子树比左子树高2,需要通过旋转来使之重新达到AVL平衡条件
if (2 == GetHeight_(pNode->pRightChild) - GetHeight_(pNode->pLeftChild))
{
if (GetHeight_(pNode->pRightChild->pRightChild) > GetHeight_(pNode->pRightChild->pLeftChild))
{
// 右子树的右子树高于右子树的左子树,应当与右子树进行单旋转
RotateWithRightChild_(pNode);
}
else
{
// 右子树的左子树高于右子树的右子树,应当与右子树进行双旋转
DoubleRotateWithRightChild_(pNode);
}
}
}
/**
插入新节点:
如果当前节点为空则说明找到了插入的位置,创建新节点,返回插入成功
如果数据小于当前节点数据则到左子树中插入,如果插入成功,可能需要旋转使之重新平衡(左子树过高),重新计算高度
如果数据大于当前节点数据则道右子树中插入,如果插入成功,可能需要旋转使之重新平衡(右子树过高),重新计算高度
如果数据等于当前节点数据则什么都不做,返回插入失败
*/
static bool Insert_(const DataType& data, Node_*& pNode)
{
if (!pNode)
{
// 找到位置,创建节点
pNode = CreateNode_(data);
assert(pNode); // 断言创建节点成功
return true;
}
else if (data < pNode->data)
{
// 将较小的数据插入到左子树
if (Insert_(data, pNode->pLeftChild))
{
// 成功插入新节点
// 如果需要,则与左子树进行旋转以维持AVL平衡条件
RatateWithLeftChildIfNeed_(pNode);
// 重新计算高度
pNode->height = CalcHeight_(pNode);
return true;
}
}
else if (data > pNode->data)
{
// 将较大的数据插入到右子树
if (Insert_(data, pNode->pRightChild))
{
// 成功插入新节点
// 如果需要,则与右子树进行旋转以维持AVL平衡条件
RatateWithRightChildIfNeed_(pNode);
// 重新计算高度
pNode->height = CalcHeight_(pNode);
return true;
}
}
else
{
// 重复数据(什么也不做,或者进行计数)
}
return false;
}
/**
删除节点
查找被删除的节点:
如果当前节点为空则说明没有找到被删除的节点,返回删除失败
如果被删除的数据小于节点数据,则在节点的左子树中查找并删除,如果删除成功,可能需要旋转使之重新平衡(右子树过高),重新计算高度
如果被删除的数据大于节点数据,则在节点的右子树中查找并删除,如果删除成功,可能需要旋转使之重新平衡(左子树过高),重新计算高度
如果被删除的数据等于节点数据,则找到被删除的节点,开始删除,返回删除成功
删除节点过程,将被删除的节点作为标记节点:
如果标记节点存在左右双子树,利用右子树的最小节点的数据替换此节点数据,然后删除右子树的最小节点:
如果右子树有左子树,从左子树中找到最小节点,将其右子树提升一级,可能需要旋转使其父节点重新平衡(其父节点的右子树过高),重新计算其父节点高度
如果右子树没有左子树,此时右子树则即是最小节点,将其右子树提升一级
可能需要旋转使标记节点重新平衡(标记节点的左子树过高),重新计算标记节点高度
如果标记节点不存在左右双子树,删除标记节点,提升其子树
*/
static bool Erase_(const DataType& data, Node_*& pNode)
{
if (!pNode)
{
// 没有找到节点
return false;
}
else if (data < pNode->data)
{
// 节点较小,在左子树中删除
if (Erase_(data, pNode->pLeftChild))
{
// 成功删除节点
// 如果需要,则与右子树进行旋转以维持AVL平衡条件
RatateWithRightChildIfNeed_(pNode);
// 重新计算高度
pNode->height = CalcHeight_(pNode);
return true;
}
}
else if (data > pNode->data)
{
// 节点较大,在右子树中删除
if (Erase_(data, pNode->pRightChild))
{
// 成功删除节点
// 如果需要,则与左子树进行旋转以维持AVL平衡条件
RatateWithLeftChildIfNeed_(pNode);
// 重新计算高度
pNode->height = CalcHeight_(pNode);
return true;
}
}
else
{
// 找到了需要被删除的节点
if (pNode->pLeftChild && pNode->pRightChild)
{
// 存在双子树,利用右子树最小节点替换,并删除右子树最小节点
Node_* pMin = pNode->pRightChild;
if (pNode->pRightChild->pLeftChild)
{
// 右子树存在左子树,从右子树的左子树中找最小节点
Node_* pMinParent = pNode->pRightChild;
while (pMinParent->pLeftChild->pLeftChild)
{
pMinParent = pMinParent->pLeftChild;
}
pMin = pMinParent->pLeftChild;
// 提升最小节点的右子树
pMinParent->pLeftChild = pMin->pRightChild;
// 如果需要,最小节点的父节点则与其右子树进行旋转以维持AVL平衡条件
RatateWithRightChildIfNeed_(pMinParent);
// 重新计算最小节点的父节点的高度
pMinParent->height = CalcHeight_(pMinParent);
}
else
{
// 右子树不存在左子树,那么提升右子树的右子树
pNode->pRightChild = pNode->pRightChild->pRightChild;
}
// 用最小节点替换
pNode->data = pMin->data;
// 删除最小节点
DestroyNode_(pMin);
// 如果需要,则与左子树进行旋转以维持AVL平衡条件
RatateWithLeftChildIfNeed_(pNode);
// 重新计算高度
pNode->height = CalcHeight_(pNode);
}
else
{
// 不存在双子树,则直接用儿子替换
Node_* pTemp = pNode;
pNode = pNode->pLeftChild ? pNode->pLeftChild : pNode->pRightChild;
// 销毁节点
DestroyNode_(pTemp);
}
return true;
}
return false;
}
}; // class AVLTree
#ifdef _PRINT
template<>
void AVLTree<int>::Print() const
{
if (!pRoot_)
{
return;
}
PrinterContainer nextPrinters; // 下一层需要打印的对象集合
nextPrinters.push_back(PSharedPrinter(new NodePrinter(pRoot_, nextPrinters)));
while (nextPrinters.end() != std::find_if(nextPrinters.begin(), nextPrinters.end(), std::mem_fn(&Printer::IsValid)))
{
auto printers(std::move(nextPrinters)); // 当前需要打印的对象集合
// 打印一行
std::for_each(printers.begin(), printers.end(), std::mem_fn(&Printer::Print));
// 换行
std::cout<<std::endl;
}
}
template<>
size_t AVLTree<int>::CalcDataWidth_(int n)
{
if (0 == n)
{
return 1+2; // +2是为[]符号占位
}
size_t ret = 2; // 2是为[]符号占位
if (0 > n)
{
// 复数,添加符号位
++ret;
n = -n;
}
while (n)
{
++ret;
n /= 10;
}
return ret;
}
#endif // _PRINT
} // namespace ghost
#endif // AVL_TREE_H
#define _PRINT
#include "AVLTree.h"
#include <iostream>
#include <ctime>
/// 打印AVL树
template<typename T>
void PrintAVLTree(const ghost::AVLTree<T>& tree)
{
#ifdef _PRINT
std::cout<<"--------------AVLTree--------------"<<std::endl;
tree.Print();
std::cout<<"------------------------------------------"<<std::endl;
#else
std::cerr<<"未开启打印预处理器,不提供AVL树的打印!\n";
#endif // _PRINT
}
static const size_t TEST_DATA_COUNT = 10; // 测试数据的个数
static const size_t TEST_DATA_LOWER_LIMIT = 0; // 测试数据的下限
static const size_t TEST_DATA_UPPER_LIMIT = 10; // 测试数据的上限
/// 随机构造测试数据
int BuildTestData()
{
return TEST_DATA_LOWER_LIMIT + rand() % (TEST_DATA_UPPER_LIMIT-TEST_DATA_LOWER_LIMIT);
}
int main()
{
srand((int)time(0));
ghost::AVLTree<int> tree;
// 随机插入测试数据
for (size_t i = 0; i < TEST_DATA_COUNT; ++i)
{
tree.Insert(BuildTestData());
PrintAVLTree(tree);
}
// 随机删除测试数据
for (size_t i = 0; i < TEST_DATA_COUNT; ++i)
{
tree.Erase(BuildTestData());
PrintAVLTree(tree);
}
// tree.Insert(5);
// PrintAVLTree(tree);
//
// tree.Insert(2);
// PrintAVLTree(tree);
//
// tree.Insert(8);
// PrintAVLTree(tree);
//
// tree.Insert(1);
// PrintAVLTree(tree);
//
// tree.Insert(4);
// PrintAVLTree(tree);
//
// tree.Insert(7);
// PrintAVLTree(tree);
//
// tree.Insert(3);
// PrintAVLTree(tree);
//
// tree.Insert(6); // 此时应触发一次单旋转
// PrintAVLTree(tree);
return 0;
}