Implement of AVL_Tree using Cpp

Contents

Introduction

AVL_tree是平衡二叉树的一种，能够自动维持平衡。维持平衡的方式则是通过单旋转与双旋转来实现。AVL_Tree规定了子节点的高度相差不超过1，大于等于2时，对树进行调节，使之重新符合要求。
二叉树中，不平衡的情况主要可以分为四种,本质上其实是两种:

– 上图中，$root$是根节点，后缀$R$、$L$分别代表父节点的左右子节点。
– $h$代表本节点的高度，当某个分支比另外一个分支高2时，可以分为四种情况：
– $$R_h < L_h \begin{cases}
1.\ LL_h = 2\ \left(LL\ is\ the\ left\ child\ of\ L\ \right) \
2.\ LR_h = 2\ \left(LR\ is\ the\ right\ child\ of\ L\ \right)
\end{cases}$$

- $$R_h > L_h \begin{cases}
  1.\ RL_h = 2\ \left(RL\ is\ the\ left\ child\ of\ R\ \right) \\
  2.\ RR_h = 2\ \left(RR\ is\ the\ right\ child\ of\ R\ \right) 
  \end{cases} $$

上面所列的四种情况包含了插入一个新值导致树出现不平衡的所有可能，其中，$LL$、$RR$本质上是相同的情况，是镜像问题，另外两个也一样，所以其实只有两个情况需要讨论。
以$LL$为例，只要做一个单旋转即可，具体如下所示,由二叉搜索树的特性可以知道，这个变化是($RR$与之相似就不讨论了)：
$RL$与$LR$本质上也一样，以$LR$为例,执行两次单旋转即可（即一次双旋转）：

Designs

UML图
基本数据类型结构体定义：

template<typename T>
struct node
{
    T val;
    node* left;
    node* right;
    int height;
    node(T _val = 0, int _h = 1, node *_left = nullptr, node* _right = nullptr):val(_val),
                                                                left(_left),
                                                                right(_right),
                                                                height(_h) {};
};

公共接口

CAvlTree();//ctor 1
CAvlTree(vector<T> &_vec);//ctor 2
~CAvlTree();//dtor
const int height() const;//获取节点高度
const bool isempty() const;//判断是否为空
const NodePtr search(const T val) const;//寻找某个节点，返回指向节点的指针
const NodePtr findMin() const;//寻找最小值，返回其所在节点指针
const NodePtr findMax() const;
void insert(T _val);//插入新节点
void erase(T _val);//消除某节点
void erase(vector<T> vec);//批量消除节点
void print();//打印当前所有节点的信息

私有成员变量：

NodePtr pRoot;//typedef typename node<T>* NodePtr
function<bool(T, T)> comp;

私有方法：

const NodePtr search(const T& val, NodePtr _node) const;//search的内部实现
const bool compare(NodePtr a, NodePtr b) const;//比较元素大小
const int height(const NodePtr& _node) const;//获取高度的内部实现
void destory();//dtor内部实现
void destory(NodePtr& tree);
NodePtr insert(NodePtr &pNode, T &val);//对应内部实现
NodePtr erase(NodePtr &pNode, T &val);
void print(NodePtr _node) const;
const NodePtr findMax(NodePtr _node) const;
const NodePtr findMin(NodePtr _node) const;
NodePtr rrRotation(NodePtr pNode);//右右单旋转
NodePtr rlRotation(NodePtr pNode);//右左单旋转
NodePtr lrRotation(NodePtr pNode);//双旋转
NodePtr llRotation(NodePtr pNode);

单旋转实现细节：

template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::llRotation(NodePtr pNode)
{
    NodePtr pL = pNode->left;
    pNode->left = pL->right;
    pL->right = pNode;
    pNode->height = max(pNode->left->height, pNode->right->height) + 1;
    pL->height = max(pL->left->height, pL->right->height) + 1;
    return pL;
}

双旋转实现细节：

template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::lrRotation(NodePtr pNode)
{
    pNode->left = rrRotation(pNode->left);
    return llRotation(pNode);
}

Complete Implements

#pragma once
#ifndef AVL_TREE_H
#define AVL_TREE_H
#include <functional>
#include <iostream>
#include <queue>
#include <fstream>
using namespace std;
template<typename T>
struct node
{
    T val;
    node* left;
    node* right;
    int height;
    node(T _val = 0, int _h = 1, node *_left = nullptr, node* _right = nullptr):val(_val),left(_left),right(_right),height(_h){};
};

template<typename T>
class CAvlTree
{
public:
    typedef node<T> Node;
    typedef Node* NodePtr;

    CAvlTree();
    CAvlTree(vector<T> &_vec);
    ~CAvlTree();
    const int height() const;
    const bool isempty() const;
    const NodePtr search(const T val) const;
    const NodePtr findMin() const;
    const NodePtr findMax() const;
    void insert(T _val);
    void erase(T _val);
    void erase(vector<T> vec);
    void print();
private:/*private method*/
    const NodePtr search(const T& val, NodePtr _node) const;
    const bool compare(NodePtr a, NodePtr b) const;
    const int height(const NodePtr& _node) const;
    void destory();
    void destory(NodePtr& tree);
    NodePtr insert(NodePtr &pNode, T &val);
    NodePtr erase(NodePtr &pNode, T &val);
    void print(NodePtr _node) const;
    const NodePtr findMax(NodePtr _node) const;
    const NodePtr findMin(NodePtr _node) const;
    NodePtr rrRotation(NodePtr pNode);
    NodePtr rlRotation(NodePtr pNode);
    NodePtr lrRotation(NodePtr pNode);
    NodePtr llRotation(NodePtr pNode);
private:/*private varibles*/
    NodePtr pRoot;
    function<bool(T, T)> comp;
};

template <typename T>
CAvlTree<T>::CAvlTree():comp(less<T>()),pRoot(nullptr)
{
}

template <typename T>
CAvlTree<T>::CAvlTree(vector<T>& _vec):comp(less<T>()),pRoot(nullptr)
{
    for (auto val : _vec)
        insert(pRoot, val);
}

template <typename T>
CAvlTree<T>::~CAvlTree()
{
    destory();
}

template <typename T>
const int CAvlTree<T>::height() const
{
    return height(pRoot);
}

template <typename T>
const bool CAvlTree<T>::isempty() const
{
    return pRoot == nullptr;
}

template <typename T>
const typename CAvlTree<T>::NodePtr CAvlTree<T>::search(const T val) const
{
    return search(val, pRoot);
}

template <typename T>
const typename CAvlTree<T>::NodePtr CAvlTree<T>::findMin() const
{
    if (!pRoot) return nullptr;
    NodePtr ptr = pRoot;
    while (ptr->right)
        ptr = ptr->right;
    return ptr;
}

template <typename T>
const typename CAvlTree<T>::NodePtr CAvlTree<T>::findMax() const
{
    if(!pRoot)  return nullptr;
    NodePtr ptr;
    while (ptr->left)
        ptr = ptr->left;
    return ptr;
}

template <typename T>
void CAvlTree<T>::insert(T _val)
{
    insert(pRoot, _val);
}

template <typename T>
void CAvlTree<T>::erase(T _val)
{
    erase(pRoot, _val);
}

template <typename T>
void CAvlTree<T>::erase(vector<T> vec)
{
    for (auto val : vec)
        erase(pRoot, val);
}

template <typename T>
void CAvlTree<T>::print()
{
    print(pRoot);
}

template <typename T>
const typename CAvlTree<T>::NodePtr CAvlTree<T>::search(const T& val, NodePtr _node) const
{
    if (!_node) return nullptr;
    if (_node->val == val) return _node;
    if(_node->val<val)
    {
        if (_node->left)
            return search(val, _node->left);
        return nullptr;
    }
    if (_node->right)
        return search(val, _node->right);
    return nullptr;
}

template <typename T>
const bool CAvlTree<T>::compare(NodePtr a, NodePtr b) const
{
    if (a == nullptr || b == nullptr)
    {
        cout << "compare error! node should not be nullptr!" << endl;
        return false;
    }
    return comp(a->val, b->val);
}

template <typename T>
const int CAvlTree<T>::height(const NodePtr& _node) const
{
    if (_node != nullptr)
        return _node->height;
    return 0;
}

template <typename T>
void CAvlTree<T>::destory()
{
    destory(pRoot);
}

template <typename T>
void CAvlTree<T>::destory(NodePtr& tree)
{
    if (!tree) return;
    if (tree->left) destory(tree->left);
    if (tree->right) destory(tree->right);
    delete tree;
}

template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::insert(NodePtr& pNode, T &val)
{
    if(pNode==nullptr)
    {
        pNode = new Node(val);
        if(!pNode)
        {
            cout << "fail to create a new node" << endl;
            return nullptr;
        }
    }else if(val < pNode->val)
    {
        insert(pNode->left, val);
        if(height(pNode->left) - height(pNode->right) == 2)
        {
            if (val < pNode->left->val)
                pNode = llRotation(pNode);
            else
                pNode = lrRotation(pNode);
        }
    }else if(val>pNode->val)
    {
        insert(pNode->right, val);
        if(height(pNode->right) - height(pNode->left) == 2)
        {
            if (val > pNode->right->val)
                pNode = rrRotation(pNode);
            else
                pNode = rlRotation(pNode);
        }
    }else//val == pNode->val
    {
        cout << "fail to add the same node!" << endl;
        return nullptr;
    }
    pNode->height = max(height(pNode->left), height(pNode->right)) + 1;
    return pNode;
}

template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::erase(NodePtr& pNode, T& val)
{
    if (!pNode)
        return nullptr;
    if(val<pNode->val)
    {
        erase(pNode->left, val);
    }else if(val>pNode->val)
    {
        erase(pNode->right, val);
    }else
    {
        if(pNode->left && pNode->right)
        {
            if(height(pNode->left)>height(pNode->right))
            {
                NodePtr max = findMax(pNode->left);
                pNode->val = max->val;
                erase(pNode->left, max->val);

            }else
            {
                NodePtr min = findMin(pNode->right);
                pNode->val = min->val;
                erase(pNode->right, min->val);

            }
        }else
        {
            if(!pNode->left && !pNode->right)
            {
                NodePtr tmp = pNode;
                pNode = nullptr;
                delete tmp;
            }else
                pNode = (pNode->left) ? pNode->left : pNode->right;
        }
    }
    if(pNode)   pNode->height = max(height(pNode->left), height(pNode->right)) + 1;
    return pNode;
}

template <typename T>
void CAvlTree<T>::print(NodePtr _node) const
{
    //bfs : use deque
    fstream fout("D:\\CppExam\\AVL_Tree\\tree.txt");
    queue<NodePtr> q;
    if(_node)   q.push(_node);
    while(!q.empty())
    {
        int len = q.size();
        while(len>0)
        {
            fout << q.front()->val << " ";//"(height: " << q.front()->height << ")" << " ";
            if (q.front()->left)    q.push(q.front()->left);
            if (q.front()->right)   q.push(q.front()->right);
            q.pop();
            --len;
        }
        fout << endl;
    }
    fout.close();
}

template <typename T>
const typename CAvlTree<T>::NodePtr CAvlTree<T>::findMax(NodePtr _node) const
{
    NodePtr tmp = _node;
    while (tmp->right)
        tmp = tmp->right;
    return tmp;
}

template <typename T>
const typename CAvlTree<T>::NodePtr CAvlTree<T>::findMin(NodePtr _node) const
{
    NodePtr tmp = _node;
    while (tmp->left)
        tmp = tmp->left;
    return tmp;
}

/**
 * \brief 
 * \param pNode 
 * \return
 *      pNode            pR
 *      /   \           /  \
 *      pL  pR  ->    pNode pRR
 *          / \       /  \  / \
 *         pRL pRR   pL  pRL  ... 
 *             / \
 *          pRRL ...
 */
template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::rrRotation(NodePtr pNode)
{
    NodePtr pR = pNode->right;
    pNode->right = pR->left;
    pR->left = pNode;
    pNode->height = max(height(pNode->left), height(pNode->right)) + 1;
    pR->height = max(height(pR->left), height(pR->right)) + 1;
    return pR;
}

template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::rlRotation(NodePtr pNode)
{
    pNode->right = llRotation(pNode->right);
    return rrRotation(pNode);
}

template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::lrRotation(NodePtr pNode)
{
    pNode->left = rrRotation(pNode->left);
    return llRotation(pNode);
}

/**
 * \brief 
 * \param pNode 
 * \return 
 *      pNode           pL
 *      /   \           /  \
 *      pL  pR  ->      pLL pNode
 *    / \            /  \  / \
 *   pLL pLR        ...   pLR pR
 *  / \
 * pLLL ...
 */
template <typename T>
typename CAvlTree<T>::NodePtr CAvlTree<T>::llRotation(NodePtr pNode)
{
    NodePtr pL = pNode->left;
    pNode->left = pL->right;
    pL->right = pNode;
    pNode->height = max(pNode->left->height, pNode->right->height) + 1;
    pL->height = max(pL->left->height, pL->right->height) + 1;
    return pL;
}


#endif

浏览量: 2,433

AVL树的实现（C++)

Implement of AVL_Tree using Cpp

Introduction

Designs

Complete Implements