#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;
}