C++实现AVL树的完整代码

AVL树的介绍

AVL树是一种自平衡的二叉搜索树,它通过单旋转(single rotate)和双旋转(double rotate)的方式实现了根节点的左子树与右子树的高度差不超过1,。这有效的降低了二叉搜索树的时间复杂度,为O(log n)。那么,下面小编将详细介绍C++实现AVL树的代码。最后一步提供可靠的代码实现

这里先粘贴代码
给大家的忠告,一定要及时去实现,不然之后再实现要花更多的时间

/*
 *平衡二叉树应该有些功能
 *插入 删除 查找
 *前序遍历 中序遍历 后序遍历 层次遍历
 *统计结点数目
 */
 //代码已经调好,写了很久才写出来

#ifndef _AVLTREE_
#define _AVLTREE_
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define MAXFACTOR = 2;
template<class Key , class E>
class AVLNode
{
    private:
        Key key;
        E value;
        AVLNode<Key,E>* left;
        AVLNode<Key,E>* right;
        AVLNode<Key,E>* parent;
    public:
        AVLNode():left(nullptr),right(nullptr),parent(nullptr){}
        AVLNode(Key _key,E _value , AVLNode<Key,E>* _parent = nullptr,AVLNode<Key,E>*_left = nullptr, AVLNode<Key,E>*_right = nullptr):
                key(_key),value(_value),left(_left),right(_right),parent(_parent){}

        bool isLeaf(){return left==nullptr && right == nullptr ;}

        //元素设置
        Key getKey() const { return key;}
        void setKey(Key set) {key = set;}

        E getValue() const { return value;}
        void setValue(E set) {value = set;}

        AVLNode<Key,E>*  getLeft() { return left; }
        void setLeft (AVLNode< Key,E >* set){ left = set;}

        AVLNode<Key,E>*  getRight()  { return right;}
        void setRight (AVLNode<Key,E>* set) {right = set ;}

        AVLNode<Key,E>* getParent()  {return parent;}
        void setParent(AVLNode<Key,E>* set) { parent = set;}

};
template<class Key , class E>
class AVLTree
{
    private:
        AVLNode<Key,E>* root;
        void clear(AVLNode<Key,E>* &r)
        {
            if(r==nullptr)return;

            if(r->getLeft())clear(r->getLeft());
            if(r->getRight())clear(r->getRight);

            delete r;
        }

        void Init()
        {
            root = new AVLNode<Key,E>();
            root=nullptr;
        }
        void preOrder(AVLNode<Key,E>* r,void(*visit) (AVLNode<Key,E> * node))
        {
            if(r==nullptr)return;
            (*visit) (r);
            preOrder(r->getLeft() , visit);
            preOrder(r->getRight(), visit);
        }

        void inOrder(AVLNode<Key,E>* r , void(*visit)(AVLNode<Key,E>* node) )
        {
            if(r==nullptr)return;
            inOrder(r->getLeft() , visit);
            (*visit)(r);
            inOrder(r->getRight(),visit);
        }

        void postOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
        {
            if(r==nullptr)return;
            postOrder(r->getLeft(),visit);
            postOrder(r->getRight(),visit);
            (*visit)(r);
        }

        void levelOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
        {
            queue< AVLNode<Key,E>* > q;
            if(r==nullptr)return;
            q.push(r);
            while( ! q.empty() )
            {
                AVLNode<Key,E>* tmp = q.front();
                q.pop();
                (*visit)(tmp);
                if(tmp->getLeft() ) q.push(tmp->getLeft() );
                if(tmp->getRight()) q.push(tmp->getRight());

            }
        }

        AVLNode<Key,E>* find(AVLNode<Key,E>* r,Key k)
        {
            if(r==nullptr)return nullptr;
            if(k == r->getKey() ) return r;
            else if( k < r->getKey())
            {
                find(r->getLeft(),k);
            }
            else {
                find(r->getRight(),k);
            }
        }
        //Find the smallest element in the avl tree
        AVLNode<Key,E>* getMin(AVLNode<Key,E>* r)
        {
            if(r->getLeft() == nullptr) return r;
            else{
                getMin(r->getLeft());
            }
        }
        //Remove the smallest element
        AVLNode<Key,E>* deleteMin(AVLNode<Key,E>* rt)
        {
            if(rt->getLeft() == nullptr) return rt->getRight();
            else{
                rt->setLeft(deleteMin(rt->getLeft()));
                return rt;
            }
        }

        AVLNode<Key,E>* leftRotate(AVLNode<Key,E>* node)
        {
            if( node == nullptr) return nullptr;
            AVLNode<Key,E>* newHead = node->getRight();
            node->setRight( newHead -> getLeft() );
            newHead -> setLeft( node );
            return newHead;
        }
        AVLNode<Key,E>* rightRotate(AVLNode<Key,E>* node)
        {
            if(node == nullptr)return nullptr;
            AVLNode<Key,E>* newHead = node->getLeft();
            node->setLeft( newHead->getRight() );
            newHead ->setRight(node);
            return newHead;
        }

        int getHeight(AVLNode<Key,E>*node)
        {
            if(node == nullptr)return 0;
            if(node->isLeaf())return 1;
            else return ( getHeight( node->getLeft() ) > getHeight( node->getRight() ) ?
                        getHeight( node->getLeft() ) : getHeight( node->getRight() ) ) + 1;
        }

        int getBalanceFactor(AVLNode<Key,E>* node)
        {
            return getHeight(node->getLeft()) - getHeight(node->getRight() );
        }
        AVLNode<Key,E>* balance(AVLNode<Key,E>* node)
        {
            if(!node) return nullptr;
            else if ( getBalanceFactor( node ) == 2)
            {
                if(getBalanceFactor( node ->getLeft() ) == 1)
                {
                    node = rightRotate(node);
                }
                else
                {
                    node->setLeft(leftRotate( node->getLeft() ) );
                    node = rightRotate(node);
                }
            }
            else if(getBalanceFactor( node ) == -2)
            {
                if(getBalanceFactor( node->getRight()) == -1)
                {
                    node = leftRotate(node);
                }
                else
                {
                    node->setRight( rightRotate( node->getRight() ) );
                    node = leftRotate(node);
                }
            }
            return node;
        }

        AVLNode<Key,E>* insert( AVLNode<Key,E>* root ,const pair<Key,E>& it)
        {
            if(root == nullptr)
            {
                return new AVLNode<Key,E>(it.first , it.second,NULL,NULL,NULL);
            }
            else if (it.first < root->getKey() )
            {

                root ->setLeft( insert(root->getLeft() , it) ) ;
            }
            else{
                root ->setRight( insert(root->getRight() , it) );

            }
            root = balance(root);
            return root;
        }

        AVLNode<Key,E>* remove(AVLNode<Key,E>*  node , const Key k)
        {
            if(node == nullptr) return nullptr;
            if(node->getKey() > k)
            {
                node->setLeft( remove(node->getLeft() , k) );
                node = balance(node);
            }
            else if(node->getKey() < k)
            {
                node->setRight( remove(node->getRight(), k) );
                node = balance(node);
            }
            else if(node->getKey() == k)
            {
                if(! node->isLeaf() )
                {
                    AVLNode<Key,E>* tmp = getMin(node->getRight() );
                    node->setKey( tmp->getKey() );
                    node->setValue( tmp->getValue() );
                    node->setRight( deleteMin(node->getRight() ) );
                    delete tmp;
                }
                else {
                    AVLNode<Key,E>* tmp = node;
                    node = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight() ;
                    delete tmp;
                }
            }
            return node;
        }

    public:
        ~AVLTree(){clear(root);}
        AVLTree(){/*Init();*/ root = nullptr; }
    //四种遍历方式
        void preOrder( void (*visit)(AVLNode<Key,E>* r))
        {
            preOrder(root,visit);
        }
        void inOrder(void (*visit)(AVLNode<Key,E>* r))
        {
            inOrder(root,visit);
        }
        void postOrder(void (*visit)(AVLNode<Key,E>* r))
        {
            postOrder(root,visit);
        }
        void levelOrder( void(*visit)(AVLNode<Key,E>*r) )
        {
            levelOrder(root,visit);
        }
         //插入
        void insert(const pair<Key,E> &it)
        {
            root = insert(root,it);
        }

        //删除
       void remove(const Key& k)
        {
            remove(root,k);
        }
        bool find(const Key&k)
        {
            return find(root,k);
        }   

};
#endif
//AVLtest.cpp
#include"NewAvl.h"
#include<iostream>
using namespace std;
template<typename Key,typename E>
void traverse(AVLNode<Key,E>* root)
{
    cout<<root->getKey()<<" "<<root->getValue()<<" ";
    cout<<endl;
}
int main()
{
    AVLTree<int,int>* tree = new AVLTree<int ,int>;
    for(int i = 0 ; i < 5 ; i ++)
    {
        tree->insert(make_pair(i,i));
    }
    tree->remove(1);
    cout<<"PreOrder: "<<endl;
    tree->preOrder(traverse);
    cout<<endl;
    cout<<"LevelOrder: "<<endl;
    tree->levelOrder(traverse);
    cout<<endl;
    cout<<"InOrder: "<<endl;
    tree->inOrder(traverse);
    cout<<endl;
    cout<<"PostOrder: "<<endl;
    tree->postOrder(traverse);
    cout<<endl;
    cout<<tree->find(2)<<endl;
    tree->insert(make_pair(9,9));
    tree->levelOrder(traverse);

}

运行结果

以上就是C++实现AVL树的完整代码的详细内容,更多关于C++ AVL树的资料请关注我们其它相关文章!

(0)

相关推荐

  • 关于AVLTree(C++实现)没有统一旋转操作的问题

    最近疫情比较严重,只能在家里休息,利用休息之余,我用C++把AVL树实现了一遍 大学老师只讲一些比较简单的数据结构和算法,这些高级数据结构还是需要自己主动学习并且动手来实现的, 从前只听说过AVLTree,我从看书了解原理到把它一点一点写出来最后在调试一共花了大概3天的时间.应该已经算很长时间了. 一般情况下AVL树是不用我么自己写的,但是为了有一份已经实现的代码作为我以后再来回顾算法实现的依照,我还是决定对自己狠一些把它实现了一遍 以下代码均采用C++11 标准 在ubuntu 18.04上经

  • C++实现AVL树的完整代码

    AVL树的介绍 AVL树是一种自平衡的二叉搜索树,它通过单旋转(single rotate)和双旋转(double rotate)的方式实现了根节点的左子树与右子树的高度差不超过1,.这有效的降低了二叉搜索树的时间复杂度,为O(log n).那么,下面小编将详细介绍C++实现AVL树的代码.最后一步提供可靠的代码实现 这里先粘贴代码 给大家的忠告,一定要及时去实现,不然之后再实现要花更多的时间 /* *平衡二叉树应该有些功能 *插入 删除 查找 *前序遍历 中序遍历 后序遍历 层次遍历 *统计结

  • C++实现AVL树的基本操作指南

    目录 AVL树的概念 AVL树的插入 AVL树的四种旋转 右单旋 左单旋 左右双旋 右左双旋 查找 其他接口 析构函数 拷贝构造 拷贝赋值 总结 AVL树的概念 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下.因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需

  • 图解AVL树数据结构输入与输出及实现示例

    目录 AVL树(平衡二叉树): AVL树的作用: AVL树的基本操作: AVL树的插入,单旋转的第一种情况---右旋: AVL树的插入,单旋转的第二种情况---左旋: AVL树的插入,双旋转的第一种情况---左右(先左后右)旋: AVL树的插入,双旋转的第二种情况---右左(先右后左)旋: AVL树的插入代码实现:(仅供参考) AVL树(平衡二叉树): AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

  • C++数据结构之AVL树的实现

    目录 1.概念 (1)二叉搜索树的缺点 (2)定义节点 2.插入 (1)拆分 (2)找节点与插节点 (3)更新平衡因子与旋转 3.判断 4.完整代码及测试代码 完整代码 测试代码 1.概念 (1)二叉搜索树的缺点 要手撕AVL树,我们首先要知道什么是AVL树.AVL树是在二叉搜索树的基础之上改造的.当我们插入的是一个有序的序列的时候,二叉搜素树会使用一条直线来进行存储,这样并不利于查找. 当遇到这种情况的时候我们就需要对这棵树来进行调整.AVL树会通过旋转等操作,来规避这种情况.最终满足每一个节

  • Java详解AVL树的应用

    目录 一.什么是AVL树 1.二叉搜索树 2.为什么引入了AVL树 3.什么是AVL树 二.自己构造AVL树 三.AVL树的插入和删除 1.插入 1.1.右单旋 1.2.左单旋 1.3.左右双旋 1.4.右左双旋 2.删除 一.什么是AVL树 在认识AVL树之前我们先认识一下什么是二叉搜索树: 1.二叉搜索树 二叉搜索树又称为二叉排序树,二叉搜索树满足所有的左孩子节点都小于其根节点的值,所有的右孩子节点都大于其根节点的值,二叉搜索树上的每一棵子树都是一棵二叉搜索树,因此二叉搜索树通过中序遍历可以

  • jquery实现树形菜单完整代码

    本实例实现了树形的动态菜单,兼容IE8,火狐,Chrome等浏览器.使用了jQuery的toggle() 方法.效果和代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/199

  • 数据结构之AVL树详解

    1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树.AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis.AVL树种查找.插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.本文介绍了AVL树的设计思想和基本操作. 2. 基本术语 有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树

  • java算法实现红黑树完整代码示例

    红黑树 定义 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组. 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接:没有任何一个结点同时和两条红链接相连:该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同. 满足这样定义的红黑树和相应的2-3树是一一对应的. 旋转 旋转又分为左旋和右旋.通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接.对比操作前后,可以看出,该操作

  • p5.js 毕达哥拉斯树的实现代码

    本文介绍了p5.js 毕达哥拉斯树的实现代码,分享给大家,具体如下: 效果如下: 主要方法 translate() rotate() rect() push() pop() map() 主要思想 递归 草图 过程分解 一.毕达哥拉斯树的递归函数 function Pythagorian(x){ noStroke(); fill(107, 142, 35,map(x, 0, a, 150, 255));//根据正方形边长设置填充色 rect(0,0,x,x);//绘制当前的正方形 if(x <=

  • C++实现KDTree 附完整代码

    目录 简介 举例 分割的作用 一维 二维 n维 关于kdtree的重要问题 一.树的建立 关键代码 简介   k-d树(k-dimensional),是一种分割k维数据空间的数据结构(对数据点在k维空间中划分的一种数据结构),主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索). kdTree概念 kd-tree或者k维树是计算机科学中使用的一种数据结构,用来组织表示k维空间中点的集合.它是一种带有其他约束条件的二分查找树.Kd-tree对于区间和近邻搜索十分有用.一般位于三维空间中的邻

随机推荐