数据结构与算法——AVL树类的C++实现

关于二叉搜索树（也称为二叉查找树）能够參考：数据结构与算法——二叉查找树类的C++实现

AVL-tree是一个"加上了额外平衡条件"的二叉搜索树，其平衡条件的建立是为了确保整棵树的深度为O(logN)。要求不论什么节点的左右子树高度相差最多1。

该AVL树结点的数据结构:

struct AvlNode{

    Comparable element;

    AvlNode * left;

    AvlNode * right;

    int height;

    AvlNode(const Comparable & e, AvlNode * lt, AvlNode * rt, int h = 0):element(e), left(lt), right(rt), height(h){}

};

该结点数据结构事实上是一个结点类。

该AVL树的主要成员函数：

void makeEmpty();//清空该树

bool isEmpty() const;//推断该树是否为空

void lessOrderPrintTree();//从小到大输出该AVL平衡树

void biggerOrderPrintTree();//从大到小输出该AVL平衡树

void insert(const Comparable & x);//插入值为x的结点

Comparable findMin() const;//找到最小值

Comparable findMax() const;//找到最大值

主要成员函数介绍：

/****************************************************************

*   函数名称：void insert(const Comparable & x, AvlNode * t)

*   功能描写叙述: 在结点t的后面插入值为x的结点

*   參数列表: x为要插入结点的值

*             t为当前的结点

*   返回结果：void

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::insert(const Comparable & x, AvlNode * & t)

{

    if(t == NULL)//当前结点为空

        t = new AvlNode(x, NULL, NULL);

    else if(x < t->element){

        insert(x, t->left);

        if(height(t->left) - height(t->right) == 2){

            if(x < t->left->element)//单旋转。左左插入

                rotateWithLeftChild(t);

            else

                doubleWithLeftChild(t);//双旋转。左右插入

        }

    }

    else if(x > t->element){

        insert(x, t->right);

        if(height(t->right) - height(t->left) == 2){

            if(x > t->right->element)//单旋转，右右插入

                rotateWithRightChild(t);

            else

                doubleWithRightChild(t);//双旋转，右左插入

        }

    }

    //假设x的值和当前结点的值同样，则忽略。

也能够向之前二叉查找树一样给每一个结点再加一个num成员变量。

t->height = max(height(t->left), height(t->right)) + 1;//更新结点t的高度

}

/****************************************************************

*   函数名称：rotateWithLeftChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行单旋转。用于左左插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::rotateWithLeftChild(AvlNode * & k2)

{

    cout << "左单旋转" << endl;

    AvlNode * k1 = k2->left;

    k2->left = k1->right;

    k1->right = k2;

    k2->height = max(height(k2->left), height(k2->right)) + 1;

    k1->height = max(height(k1->left), k2->height) + 1;

    k2 = k1;

}

/****************************************************************

*   函数名称：rotateWithRightChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行单旋转。用于左右插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::rotateWithRightChild(AvlNode * & k1)

{

    cout << "右单旋转" << endl;

    AvlNode * k2 = k1->right;

    k1->right = k2->left;

    k2->left = k1;

    k1->height = max(height(k1->left), height(k1->right)) + 1;

    k2->height = max(height(k2->right), k1->height) + 1;

    k1 = k2;

}

/****************************************************************

*   函数名称：doubleWithLeftChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行双旋转，用于左右插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::doubleWithLeftChild(AvlNode * & k3)

{

    cout << "**********************" << endl;

    cout << "左双旋转: " << endl;

    rotateWithRightChild(k3->left);

    rotateWithLeftChild(k3);

    cout << "**********************" << endl;

}

/****************************************************************

*   函数名称：doubleWithRightChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行双旋转。用于右左插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::doubleWithRightChild(AvlNode * & k1)

{

    cout << "**********************" << endl;

    cout << "右双旋转: " << endl;

    rotateWithLeftChild(k1->right);

    rotateWithRightChild(k1);

    cout << "**********************" << endl;

}

关于右单旋转的一个图例：

结合图形看该旋转函数：

template<typename Comparable>

void AvlTree<Comparable>::rotateWithRightChild(AvlNode * & k1)

{

    cout << "右单旋转" << endl;

    AvlNode * k2 = k1->right;

    k1->right = k2->left;

    k2->left = k1;

    k1->height = max(height(k1->left), height(k1->right)) + 1;

    k2->height = max(height(k2->right), k1->height) + 1;

    k1 = k2;

}

左单旋转是相同的道理。

关于右双旋转的一个图例：

数据结构与算法——AVL树类的C++实现

结合图形看该旋转函数：

template<typename Comparable>

void AvlTree<Comparable>::doubleWithRightChild(AvlNode * & k1)

{

    cout << "**********************" << endl;

    cout << "右双旋转: " << endl;

    rotateWithLeftChild(k1->right);

    rotateWithRightChild(k1);

    cout << "**********************" << endl;

}

该函数中的凝视是为了測试该函数是否运行了。

以下给出一个完整的实測：

依次向树中插入结点: 1, 2, 3, 4, 5, 6, 7, 16, 15。

先用图示来表现一下详细的实现过程，然后用程序来验证一下。在main函数的tree2树就是用该数据序列生成的AVL树，能够看信息打印是否经过了对应的旋转。

    AvlTree<int> tree2;

    cout << "构造AVL树trre2: " << endl;

    for(int i = 1; i < 8; ++i)

        tree2.insert(i);

    tree2.insert(16);

    tree2.insert(15);

    tree2.lessOrderPrintTree();

    tree2.biggerOrderPrintTree();

输出为：

构造AVL树trre2:

右单旋转

右单旋转

右单旋转

右单旋转

**********************

右双旋转:

左单旋转

右单旋转

**********************

从小到大输出：1 2 3 4 5 6 7 15 16

从大到小输出：16 15 7 6 5 4 3 2 1

以下是该AVL树类的源码：

/*************************************************************************

	> File Name: AvlTree.cpp

	> Author:

	> Mail:

	> Created Time: 2016年04月08日 星期五 10时14分48秒

 ************************************************************************/

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

template<typename Comparable>

class AvlTree{

    public:

        AvlTree(){ root = NULL; }

        ~AvlTree();

        void makeEmpty();//清空该树

        bool isEmpty() const;//推断该树是否为空

        void lessOrderPrintTree();//从小到大输出该AVL平衡树

        void biggerOrderPrintTree();//从大到小输出该AVL平衡树

        void insert(const Comparable & x);//插入值为x的结点

        Comparable findMin() const;//找到最小值

        Comparable findMax() const;//找到最大值

    private:

        struct AvlNode{

            Comparable element;

            AvlNode * left;

            AvlNode * right;

            int height;

            AvlNode(const Comparable & e, AvlNode * lt, AvlNode * rt, int h = 0):element(e), left(lt), right(rt), height(h){}

        };

        AvlNode * root;

    private:

        void makeEmpty(AvlNode * t);

        void lessOrderPrintTree(AvlNode * t);

        void biggerOrderPrintTree(AvlNode * t);

        int height(AvlNode * t) const;//获得当前结点t的高度

        void insert(const Comparable & x, AvlNode * & t);//在t处。插入值为x的结点

        void rotateWithLeftChild(AvlNode * & k2);//单旋转，左左插入的情况

        void rotateWithRightChild(AvlNode * & k1);//单旋转，右右插入的情况

        void doubleWithLeftChild(AvlNode * & k3);//双旋转。左右插入的情况

        void doubleWithRightChild(AvlNode * & k1);//双旋转。右左插入的情况

        Comparable findMin(AvlNode * t) const;//找到最小值

        Comparable findMax(AvlNode * t) const;//找到最大值

};

/****************************************************************

*   函数名称：findMax()

*   功能描写叙述: 找到该树的最大值

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

Comparable AvlTree<Comparable>::findMax() const

{

    if(!isEmpty())

        return findMax(root);

}

/****************************************************************

*   函数名称：findMax(AvlNode * t)

*   功能描写叙述: 找到该树的最大值

*   參数列表: t表示当前结点

*   返回结果：无

*****************************************************************/

template<typename Comparable>

Comparable AvlTree<Comparable>::findMax(AvlNode * t) const

{

    if(t->right== NULL)

        return t->element;

    else

        return findMax(t->right);

}

/****************************************************************

*   函数名称：findMin()

*   功能描写叙述: 找到该树的最小值

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

Comparable AvlTree<Comparable>::findMin() const

{

    if(!isEmpty())

        return findMin(root);

}

/****************************************************************

*   函数名称：findMin(AvlNode * t)

*   功能描写叙述: 找到该树的最小值

*   參数列表: t表示当前结点

*   返回结果：无

*****************************************************************/

template<typename Comparable>

Comparable AvlTree<Comparable>::findMin(AvlNode * t) const

{

    if(t->left == NULL)

        return t->element;

    else

        return findMin(t->left);

}

/****************************************************************

*   函数名称：~AvlTree()

*   功能描写叙述: 析构函数，释放结点内存空间

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

AvlTree<Comparable>::~AvlTree()

{

    makeEmpty();

}

/****************************************************************

*   函数名称：void insert(const Comparable & x)

*   功能描写叙述: 插入值为x的结点

*   參数列表: x为要插入结点的值

*   返回结果：void

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::insert(const Comparable & x)

{

    insert(x, root);

}

/****************************************************************

*   函数名称：void insert(const Comparable & x, AvlNode * t)

*   功能描写叙述: 在结点t的后面插入值为x的结点

*   參数列表: x为要插入结点的值

*             t为当前的结点

*   返回结果：void

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::insert(const Comparable & x, AvlNode * & t)

{

    if(t == NULL)//当前结点为空

        t = new AvlNode(x, NULL, NULL);

    else if(x < t->element){

        insert(x, t->left);

        if(height(t->left) - height(t->right) == 2){

            if(x < t->left->element)//单旋转。左左插入

                rotateWithLeftChild(t);

            else

                doubleWithLeftChild(t);//双旋转，左右插入

        }

    }

    else if(x > t->element){

        insert(x, t->right);

        if(height(t->right) - height(t->left) == 2){

            if(x > t->right->element)//单旋转，右右插入

                rotateWithRightChild(t);

            else

                doubleWithRightChild(t);//双旋转，右左插入

        }

    }

    //假设x的值和当前结点的值同样，则忽略。也能够向之前二叉查找树一样给每一个结点再加一个num成员变量。

    t->height = max(height(t->left), height(t->right)) + 1;//更新结点t的高度

}

/****************************************************************

*   函数名称：rotateWithLeftChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行单旋转。用于左左插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::rotateWithLeftChild(AvlNode * & k2)

{

    cout << "左单旋转" << endl;

    AvlNode * k1 = k2->left;

    k2->left = k1->right;

    k1->right = k2;

    k2->height = max(height(k2->left), height(k2->right)) + 1;

    k1->height = max(height(k1->left), k2->height) + 1;

    k2 = k1;

}

/****************************************************************

*   函数名称：rotateWithRightChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行单旋转，用于左右插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::rotateWithRightChild(AvlNode * & k1)

{

    cout << "右单旋转" << endl;

    AvlNode * k2 = k1->right;

    k1->right = k2->left;

    k2->left = k1;

    k1->height = max(height(k1->left), height(k1->right)) + 1;

    k2->height = max(height(k2->right), k1->height) + 1;

    k1 = k2;

}

/****************************************************************

*   函数名称：doubleWithLeftChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行双旋转，用于左右插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::doubleWithLeftChild(AvlNode * & k3)

{

    cout << "**********************" << endl;

    cout << "左双旋转: " << endl;

    rotateWithRightChild(k3->left);

    rotateWithLeftChild(k3);

    cout << "**********************" << endl;

}

/****************************************************************

*   函数名称：doubleWithRightChild(AvlNode *t)

*   功能描写叙述: 将当前结点进行双旋转，用于右左插入的时候

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::doubleWithRightChild(AvlNode * & k1)

{

    cout << "**********************" << endl;

    cout << "右双旋转: " << endl;

    rotateWithLeftChild(k1->right);

    rotateWithRightChild(k1);

    cout << "**********************" << endl;

}

/****************************************************************

*   函数名称：int height(AvlNode *t) const

*   功能描写叙述: 获得当前结点t的高度

*   參数列表: t是指向当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

int AvlTree<Comparable>::height(AvlNode * t) const

{

    return (t == NULL) ? -1 : t->height;

}

/****************************************************************

*   函数名称：biggerOrderPrintTree()

*   功能描写叙述: 依照从大到小的顺序输出该树结点

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::biggerOrderPrintTree()

{

    cout << "从大到小输出：";

    biggerOrderPrintTree(root);

    cout << endl;

}

/****************************************************************

*   函数名称：biggerOrderPrintTree(AvlNode * t)

*   功能描写叙述: 依照从大到小的顺序输出该树结点

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::biggerOrderPrintTree(AvlNode * t)

{

    if(t != NULL){

        biggerOrderPrintTree(t->right);

        cout << t->element << " ";

        biggerOrderPrintTree(t->left);

    }

}

/****************************************************************

*   函数名称：lessOrderPrintTree()

*   功能描写叙述: 依照从小到大的顺序输出该树结点

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::lessOrderPrintTree()

{

    cout << "从小到大输出：";

    lessOrderPrintTree(root);

    cout << endl;

}

/****************************************************************

*   函数名称：lessOrderPrintTree()

*   功能描写叙述: 依照从小到大的顺序输出该树结点

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::lessOrderPrintTree(AvlNode * t)

{

    if(t != NULL){

        lessOrderPrintTree(t->left);

        cout << t->element << " ";

        lessOrderPrintTree(t->right);

    }

}

/****************************************************************

*   函数名称：makeEmpty()

*   功能描写叙述: 将该AVL平衡树清空

*   參数列表: 无

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::makeEmpty()

{

   makeEmpty(root);

}

/****************************************************************

*   函数名称：makeEmpty(struct AvlNode * t)

*   功能描写叙述: 释放t指针指向的结点

*   參数列表: t 当前结点的指针

*   返回结果：无

*****************************************************************/

template<typename Comparable>

void AvlTree<Comparable>::makeEmpty(AvlNode * t)

{

    if(t != NULL){

        makeEmpty(t->left);

        makeEmpty(t->right);

        delete t;

    }

}

/****************************************************************

*   函数名称：isEmpty()

*   功能描写叙述: 推断该树是否为空

*   參数列表: 无

*   返回结果：假设为空则返回true;否则返回false;

*****************************************************************/

template<typename Comparable>

bool AvlTree<Comparable>::isEmpty() const

{

    return (root == NULL) ? true : false;

}

//測试主函数

int main()

{

    vector<int> v;

    AvlTree<int> tree;

    for(int i = 0; i < 10; i++)

        v.push_back(rand() % 10);

    cout << "v: ";

    for(int i = 0; i < 10; ++i)

        cout << v[i] << " ";

    cout << endl;

    cout << "构造AVL树trre1: " << endl;

    for(int i = 0; i < 10; ++i)

        tree.insert(v[i]);

    tree.insert(13);

    tree.insert(12);

    tree.insert(11);

    tree.lessOrderPrintTree();

    tree.biggerOrderPrintTree();

    AvlTree<int> tree2;

    cout << "构造AVL树trre2: " << endl;

    for(int i = 1; i < 8; ++i)

        tree2.insert(i);

    tree2.insert(16);

    tree2.insert(15);

    tree2.lessOrderPrintTree();

    tree2.biggerOrderPrintTree();

    int min = tree2.findMin();

    cout << "min = " << min << endl;

    int max = tree2.findMax();

    cout << "max = " << max << endl;

    return 0;

}

数据结构与算法——AVL树类的C++实现的更多相关文章

[数据结构与算法] &colon; AVL树
头文件 typedef int ElementType; #ifndef _AVLTREE_H_ #define _AVLTREE_H_ struct AvlNode; typedef struct ...
数据结构和算法(Golang实现)(28)查找算法-AVL树
AVL树二叉查找树的树高度影响了查找的效率,需要尽量减小树的高度,AVL树正是这样的树. 一.AVL树介绍 AVL树是一棵严格自平衡的二叉查找树,1962年,发明者Adelson-Velsky和La ...
数据结构(三)实现AVL树
AVL树的定义一种自平衡二叉查找树,中面向内存的数据结构. 二叉搜索树T为AVL树的满足条件为: T是空树 T若不是空树,则TL.TR都是AVL树,且|HL-HR| <= 1 (节点的左子树高 ...
【数据结构】平衡二叉树—AVL树
(百度百科)在计算机科学中,AVL树是最先发明的自平衡二叉查找树.在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树.查找.插入和删除在平均和最坏情况下都是O(log n).增 ...
数据结构与算法分析-AVL树
1.AVL树是带有平衡条件的二叉查找树. 2.AVL树的每个节点高度最多相差1. 3.AVL树实现的难点在于插入或删除操作.由于插入和删除都有可能破坏AVL树高度最多相差1的特性,所以当特性被破坏时需 ...
数据结构——二叉查找树、AVL树
二叉查找树:由于二叉查找树建树的过程即为插入的过程,所以其中序遍历一定为升序排列! 插入:直接插入,插入后一定为根节点查找:直接查找删除:叶子节点直接删除,有一个孩子的节点删除后将孩子节点接入到父 ...
[算法] avl树实现
大二的时候数据结构课死活没看懂的一个东东,看了2小时,敲了2小时,调了2小时... 平衡树某一节点的左右子树高度相差大于1的时候即需要调整,调整可分为四中情况 ll,rr,lr,rl其中lr,rl是由 ...
数据结构与算法—Trie树
Trie,又经常叫前缀树,字典树等等.它有很多变种,如后缀树,Radix Tree/Trie,PATRICIA tree,以及bitwise版本的crit-bit tree.当然很多名字的意义其实有交 ...
Android版数据结构与算法(六)&colon;树与二叉树
版权声明:本文出自汪磊的博客,未经作者允许禁止转载. 之前的篇章主要讲解了数据结构中的线性结构,所谓线性结构就是数据与数据之间是一对一的关系,接下来我们就要进入非线性结构的世界了,主要是树与图,好了接 ...

随机推荐

Java环境设置
win7/win8下JDK环境变量设置方法首先需要到官网上下载JDK这款软件,本人下载的是jdk-7u40-windows-i586版本,安装完成显示jdk1.7.0_67. 其次选择安装路径.本人 ...
The partial sum problem
算法:搜索描述 One day,Tom's girlfriend give him an array A which contains N integers and asked him:Can yo ...
jenkins使用开始踩坑（1）
上篇文章安装教程 :https://www.cnblogs.com/linuxchao/p/linuxchao-jenkins-setup.html 一.前戏话说上一篇文章安装完 JDK 和 je ...
新数据革命：开源C&num;图形化爬虫引擎Hawk5发布
https://ferventdesert.github.io/Hawk/ Hawk是一款由沙漠之鹰历时五年个人业余时间开发的,开源图形化爬虫和数据清洗工具,GitHub Star超过2k+,前几代版 ...
连接字符串配置在App&period;config中
<?xml version="1.0" encoding="utf-8"?> <configuration> <connectio ...
centos7下部署elasticSearch集群
OS:Centos7x虚拟机 1H2Gjdk:1.8elasticsearch:5.6.0 单节点配置请参考:centos7下elasticSearch安装配置配置master节点 # 在配置文件的 ...
Ubuntu 登陆界面无限循环问题以及 root用户无法使用命令问题
在Ubuntu下配置好了eclipse之后,马上着手用eclipse试运行ns3.在./waf编译的时候出现了"Permission denied"问题. 在网络上查阅了相关资料之 ...
&commat;Java类加载器及双亲委派模型
类与类加载器虚拟机设计团队把类加载阶段的"通过一个类的全限定名来获取此类的二进制字节流"这个动作放到Java虚拟机外部去实现,以便让应用程序自己决定如何去获取所需要的类.实现这个 ...
Python Map 并行
Map是一个酷酷的小东西,也是在Python代码轻松引入并行的关键.对此不熟悉的人会认为map是从函数式语言(如Lisp)借鉴来的东西.map是一个函数 - 将另一个函数映射到一个序列上.例如: ur ...
tornado获取application/json类型的入参
tornado本身是不支持直接获取json入参的,在BaseHandler中定义方法get_json_argument,以供调用 class BaseHandler(tornado.web.Reque ...