详解如何用c++实现平衡二叉树

一、概述

平衡二叉树具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

平衡二叉树大部分操作和二叉查找树类似,主要不同在于插入删除的时候平衡二叉树的平衡可能被改变,并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变,因为只有这些结点的子树可能变化。

二、平衡二叉树不平衡的情形

把需要重新平衡的结点叫做α,由于任意两个结点最多只有两个儿子,因此高度不平衡时,α结点的两颗子树的高度相差2.容易看出,这种不平衡可能出现在下面4中情况中:

1.对α的左儿子的左子树进行一次插入

2.对α的左儿子的右子树进行一次插入

3.对α的右儿子的左子树进行一次插入

4.对α的右儿子的右子树进行一次插入

情形1和情形4是关于α的镜像对称,二情形2和情形3也是关于α的镜像对称,因此理论上看只有两种情况,但编程的角度看还是四种情形。

第一种情况是插入发生在“外边”的情形(左左或右右),该情况可以通过一次单旋转完成调整;第二种情况是插入发生在“内部”的情形(左右或右左),这种情况比较复杂,需要通过双旋转来调整。

三、调整措施

3.1、单旋转

上图是左左的情况,k2结点不满足平衡性,它的左子树k1比右子树z深两层,k1子树中更深的是k1的左子树x,因此属于左左情况。

为了恢复平衡,我们把x上移一层,并把z下移一层,但此时实际已经超出了AVL树的性质要求。为此,重新安排结点以形成一颗等价的树。为使树恢复平衡,我们把k2变成这棵树的根节点,因为k2大于k1,把k2置于k1的右子树上,而原本在k1右子树的Y大于k1,小于k2,就把Y置于k2的左子树上,这样既满足了二叉查找树的性质,又满足了平衡二叉树的性质。

这种情况称为单旋转。

3.2、双旋转

对于左右和右左两种情况,单旋转不能解决问题,要经过两次旋转。

对于上图情况,为使树恢复平衡,我们需要进行两步,第一步,把k1作为根,进行一次右右旋转,旋转之后就变成了左左情况,所以第二步再进行一次左左旋转,最后得到了一棵以k2为根的平衡二叉树。

四、AVL树的删除操作

同插入操作一样,删除结点时也有可能破坏平衡性,这就要求我们删除的时候要进行平衡性调整。

删除分为以下几种情况:

首先在整个二叉树中搜索要删除的结点,如果没搜索到直接返回不作处理,否则执行以下操作:

1.要删除的节点是当前根节点T。

如果左右子树都非空。在高度较大的子树中实施删除操作。

分两种情况:

(1)、左子树高度大于右子树高度,将左子树中最大的那个元素赋给当前根节点,然后删除左子树中元素值最大的那个节点。

(1)、左子树高度小于右子树高度,将右子树中最小的那个元素赋给当前根节点,然后删除右子树中元素值最小的那个节点。

如果左右子树中有一个为空,那么直接用那个非空子树或者是NULL替换当前根节点即可。

2、要删除的节点元素值小于当前根节点T值,在左子树中进行删除。

递归调用,在左子树中实施删除。

这个是需要判断当前根节点是否仍然满足平衡条件,

如果满足平衡条件,只需要更新当前根节点T的高度信息。

否则,需要进行旋转调整:

如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度,进行相应的单旋转。否则进行双旋转。

3、要删除的节点元素值大于当前根节点T值,在右子树中进行删除。

五、代码实现

AvlTree.h

#include <iostream>
#include <algorithm>
using namespace std;
#pragma once

//平衡二叉树结点
template <typename T>
struct AvlNode
{
    T data;
    int height; //结点所在高度
    AvlNode<T> *left;
    AvlNode<T> *right;
    AvlNode<T>(const T theData) : data(theData), left(NULL), right(NULL), height(0){}
};

//AvlTree
template <typename T>
class AvlTree
{
public:
    AvlTree<T>(){}
    ~AvlTree<T>(){}
    AvlNode<T> *root;
    //插入结点
    void Insert(AvlNode<T> *&t, T x);
    //删除结点
    bool Delete(AvlNode<T> *&t, T x);
    //查找是否存在给定值的结点
    bool Contains(AvlNode<T> *t, const T x) const;
    //中序遍历
    void InorderTraversal(AvlNode<T> *t);
    //前序遍历
    void PreorderTraversal(AvlNode<T> *t);
    //最小值结点
    AvlNode<T> *FindMin(AvlNode<T> *t) const;
    //最大值结点
    AvlNode<T> *FindMax(AvlNode<T> *t) const;
private:
    //求树的高度
    int GetHeight(AvlNode<T> *t);
    //单旋转 左
    AvlNode<T> *LL(AvlNode<T> *t);
    //单旋转 右
    AvlNode<T> *RR(AvlNode<T> *t);
    //双旋转 右左
    AvlNode<T> *LR(AvlNode<T> *t);
    //双旋转 左右
    AvlNode<T> *RL(AvlNode<T> *t);
};

template <typename T>
AvlNode<T> * AvlTree<T>::FindMax(AvlNode<T> *t) const
{
    if (t == NULL)
        return NULL;
    if (t->right == NULL)
        return t;
    return FindMax(t->right);
}

template <typename T>
AvlNode<T> * AvlTree<T>::FindMin(AvlNode<T> *t) const
{
    if (t == NULL)
        return NULL;
    if (t->left == NULL)
        return t;
    return FindMin(t->left);
}

template <typename T>
int AvlTree<T>::GetHeight(AvlNode<T> *t)
{
    if (t == NULL)
        return -1;
    else
        return t->height;
}

//单旋转
//左左插入导致的不平衡
template <typename T>
AvlNode<T> * AvlTree<T>::LL(AvlNode<T> *t)
{
    AvlNode<T> *q = t->left;
    t->left = q->right;
    q->right = t;
    t = q;
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
    q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;
    return q;
}

//单旋转
//右右插入导致的不平衡
template <typename T>
AvlNode<T> * AvlTree<T>::RR(AvlNode<T> *t)
{
    AvlNode<T> *q = t->right;
    t->right = q->left;
    q->left = t;
    t = q;
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
    q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;
    return q;
}

//双旋转
//插入点位于t的左儿子的右子树
template <typename T>
AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t)
{
    //双旋转可以通过两次单旋转实现
    //对t的左结点进行RR旋转,再对根节点进行LL旋转
    RR(t->left);
    return LL(t);
}

//双旋转
//插入点位于t的右儿子的左子树
template <typename T>
AvlNode<T> * AvlTree<T>::RL(AvlNode<T> *t)
{
    LL(t->right);
    return RR(t);
}

template <typename T>
void AvlTree<T>::Insert(AvlNode<T> *&t, T x)
{
    if (t == NULL)
        t = new AvlNode<T>(x);
    else if (x < t->data)
    {
        Insert(t->left, x);
        //判断平衡情况
        if (GetHeight(t->left) - GetHeight(t->right) > 1)
        {
            //分两种情况 左左或左右

            if (x < t->left->data)//左左
                t = LL(t);
            else                  //左右
                t = LR(t);
        }
    }
    else if (x > t->data)
    {
        Insert(t->right, x);
        if (GetHeight(t->right) - GetHeight(t->left) > 1)
        {
            if (x > t->right->data)
                t = RR(t);
            else
                t = RL(t);
        }
    }
    else
        ;//数据重复
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}

template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *&t, T x)
{
    //t为空 未找到要删除的结点
    if (t == NULL)
        return false;
    //找到了要删除的结点
    else if (t->data == x)
    {
        //左右子树都非空
        if (t->left != NULL && t->right != NULL)
        {//在高度更大的那个子树上进行删除操作

            //左子树高度大,删除左子树中值最大的结点,将其赋给根结点
            if (GetHeight(t->left) > GetHeight(t->right))
            {
                t->data = FindMax(t->left)->data;
                Delete(t->left, t->data);
            }
            else//右子树高度更大,删除右子树中值最小的结点,将其赋给根结点
            {
                t->data = FindMin(t->right)->data;
                Delete(t->right, t->data);
            }
        }
        else
        {//左右子树有一个不为空,直接用需要删除的结点的子结点替换即可
            AvlNode<T> *old = t;
            t = t->left ? t->left: t->right;//t赋值为不空的子结点
            delete old;
        }
    }
    else if (x < t->data)//要删除的结点在左子树上
    {
        //递归删除左子树上的结点
        Delete(t->left, x);
        //判断是否仍然满足平衡条件
        if (GetHeight(t->right) - GetHeight(t->left) > 1)
        {
            if (GetHeight(t->right->left) > GetHeight(t->right->right))
            {
                //RL双旋转
                t = RL(t);
            }
            else
            {//RR单旋转
                t = RR(t);
            }
        }
        else//满足平衡条件 调整高度信息
        {
            t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
        }
    }
    else//要删除的结点在右子树上
    {
        //递归删除右子树结点
        Delete(t->right, x);
        //判断平衡情况
        if (GetHeight(t->left) - GetHeight(t->right) > 1)
        {
            if (GetHeight(t->left->right) > GetHeight(t->left->left))
            {
                //LR双旋转
                t = LR(t);
            }
            else
            {
                //LL单旋转
                t = LL(t);
            }
        }
        else//满足平衡性 调整高度
        {
            t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
        }
    }

    return true;
}

//查找结点
template <typename T>
bool AvlTree<T>::Contains(AvlNode<T> *t, const T x) const
{
    if (t == NULL)
        return false;
    if (x < t->data)
        return Contains(t->left, x);
    else if (x > t->data)
        return Contains(t->right, x);
    else
        return true;
}

//中序遍历
template <typename T>
void AvlTree<T>::InorderTraversal(AvlNode<T> *t)
{
    if (t)
    {
        InorderTraversal(t->left);
        cout << t->data << ' ';
        InorderTraversal(t->right);
    }
}

//前序遍历
template <typename T>
void AvlTree<T>::PreorderTraversal(AvlNode<T> *t)
{
    if (t)
    {
        cout << t->data << ' ';
        PreorderTraversal(t->left);
        PreorderTraversal(t->right);
    }
}

main.cpp

#include "AvlTree.h"

int main()
{
    AvlTree<int> tree;
    int value;
    int tmp;
    cout << "请输入整数建立二叉树(-1结束):" << endl;
    while (cin >> value)
    {
        if (value == -1)
            break;
        tree.Insert(tree.root,value);
    }
    cout << "中序遍历";
    tree.InorderTraversal(tree.root);
    cout << "\n前序遍历:";
    tree.PreorderTraversal(tree.root);
    cout << "\n请输入要查找的结点:";
    cin >> tmp;
    if (tree.Contains(tree.root, tmp))
        cout << "已查找到" << endl;
    else
        cout << "值为" << tmp << "的结点不存在" << endl;
    cout << "请输入要删除的结点:";
    cin >> tmp;
    tree.Delete(tree.root, tmp);
    cout << "删除后的中序遍历:";
    tree.InorderTraversal(tree.root);
    cout << "\n删除后的前序遍历:";
    tree.PreorderTraversal(tree.root);
}

测试结果

以上就是详解如何用c++实现平衡二叉树的详细内容,更多关于c++平衡二叉树的资料请关注我们其它相关文章!

时间: 2021-06-10

C语言数据结构之平衡二叉树(AVL树)实现方法示例

本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

平衡二叉树的实现实例

复制代码 代码如下: /*首先平衡二叉树是一个二叉排序树:其基本思想是:在构建二叉排序树的过程中,当每插入一个节点时,先检查是否因为插入而破坏了树的平衡性,若是,找出最小不平衡树,进行适应的旋转,使之成为新的平衡二叉树.*/#include<cstdio>#include<cstdlib>#define LH 1#define EH 0#define RH -1 using namespace std; typedef struct BTNode{ int data; int BF

平衡二叉树的左右旋以及双旋转的图文详解

高度平衡的搜索二叉树 一棵平衡树,或是空树,或是具有以下性质的二叉搜索树:左子树和右子树都是AVL树,且左右子树的高度之差的绝对值不超过1. 该二叉树,根结点的右子树高度为3,左子树高度为2.结点上方的数字为平衡因子,因为右子树高度比左子树高度大1,所以根结点的平衡因子为1. 一颗平衡二叉树,如果有n个结点,其高度可保持O(log2^n),平均搜索长度也可以保持在O(log2^n) 平衡化旋转  AVL树相较于普通的二叉搜索树,自主要的就是做了平衡化处理,使得二叉树变的平衡,高度降低. 在插入一

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

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

平衡二叉树AVL操作模板

复制代码 代码如下: /*** 目的:实现AVL* 利用数组对左右儿子简化代码,但是对脑力难度反而增大不少,只适合acm模板* 其实avl在acm中基本不用,基本被treap取代* avl一般只要求理解思路,不要求写出代码,因为真心很烦*/ #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <

python 平衡二叉树实现代码示例

平衡二叉树: 在上一节二叉树的基础上我们实现,如何将生成平衡的二叉树 所谓平衡二叉树: 我自己定义就是:任何一个节点的左高度和右高度的差的绝对值都小于2 如图所示,此时a的左高度等于3,有高度等于1,差值为2,属于不平衡中的左偏 此时的处理办法就是: 将不平衡的元素的左枝的最右节点变为当前节点, 此时分两种情况: 一.左枝有最右节点 将最右节点的左枝赋予其父节点的右枝 二.左枝没有最右节点, 直接将左枝节点做父级节点,父级节点做其右枝 如图所示,图更清楚些. 可能会有疑问,为什么这样变换? 假定

C语言 数据结构平衡二叉树实例详解

数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

C语言数据结构 快速排序实例详解

C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart

Linux 下C语言连接mysql实例详解

Linux 下C语言连接mysql实例详解 第一步: 安装mysql, 参考:http://www.jb51.net/article/39190.htm 第二步: 安装mysql.h函数库 sudo apt-get install libmysqlclient-dev 执行之后就可以看到/usr/include/MySQL目录了 然后开始我们的链接. 首先看我的数据库 mysql> show databases; +--------------------+ | Database | +----

C语言文件复制实例详解

C语言文件复制实例详解 文件复制,在Linux中,将生成的read.o 重新文件拷贝一份复制到ReadCopy.o中,并且更改ReadCopy.o文件的操作权限.使其能够正常运行. 实例代码: #include <stdio.h> int main(){ FILE *r_file = fopen ("read.o","rb"); FILE *w_file = fopen ("ReadCopy.o","w"); ch

C语言柔性数组实例详解

本文实例分析了C语言柔性数组的概念及用法,对于进一步学习C程序设计有一定的借鉴价值.分享给大家供大家参考.具体如下: 一般来说,结构中最后一个元素允许是未知大小的数组,这个数组就是柔性数组.但结构中的柔性数组前面必须至少一个其他成员,柔性数组成员允许结构中包含一个大小可变的数组,sizeof返回的这种结构大小不包括柔性数组的内存.包含柔数组成员的结构用malloc函数进行内存的动态分配,且分配的内存应该大于结构的大小以适应柔性数组的预期大小.柔性数组到底如何使用? 不完整类型 C和C++对于不完

C语言关系运算符实例详解

在程序中经常需要比较两个数据的大小,以决定程序下一步的工作.比如一个程序限制了只能成年人使用,儿童因为年龄不够,没有权限使用.这时候程序就需要获取用户输入的年龄并做出判断,如果超过18岁就正常运行,否则给出无权使用的提示. 比较两个数据大小的运算符称为关系运算符(Relational Operators). 在C语言中有以下关系运算符: 1) <(小于) 2) <=(小于或等于) 3) >(大于) 4) >=(大于或等于) 5) ==(等于) 6) !=(不等于) 关系运算符都是双

C语言内存对齐实例详解

本文详细讲述了C语言程序设计中内存对其的概念与用法.分享给大家供大家参考之用.具体如下: 一.字节对齐基本概念 现代计算机中内存空间都是按照byte划分的,从理论上讲似乎对任何类型的变量的访问可以从任何地址开始,但实际情况是在访问特定类型变量的时候经常在特定的内存地址访问,这就需要各种类型数据按照一定的规则在空间上排列,而不是顺序的一个接一个的排放,这就是对齐. 对齐的作用和原因:各个硬件平台对存储空间的处理上有很大的不同.一些平台对某些特定类型的数据只能从某些特定地址开始存取.比如有些架构的C

C语言数据结构 链表与归并排序实例详解

C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

C语言数据结构之图的遍历实例详解

C语言数据结构之图的遍历实例详解 输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st

C语言树状数组的实例详解

C语言树状数组的实例详解 最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^ 首先她的常数比线段树小,其次她的实现复杂度也远低于线段树 (并没有黑线段树的意思=-=) 所以熟练掌握她是非常有必要的.. 关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了 1,单点修改,求区间和 #define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y void Update(int i,int v)