文档章节

平衡二叉树

首席吹牛官
 首席吹牛官
发布于 2015/05/22 12:56
字数 1718
阅读 0
收藏 0

                  二叉树的查找,插入和删除操作的时间与树的高度有关,如果树尽量的矮胖,那么时间就短,那就要是满二叉树,或者说满N叉树,对于一颗M个节点的满N叉树时间复杂度为,但是维护满叉树,难度是很大的。所以AVL树(平衡树)放宽了条件,允许左右子树的高度差在一定的范围之内,avl树平衡条件是左右子树高度相差不能为2,而不是满叉树左右子树高度相同。AVL是以提出它的两位苏联数学家的名字头字母命名的。一棵N个节点的AVL树,高度最高为1.44logx(N+1)-0.328,比满二叉树高度增加44%。

                  在avl树中通过对不满足限制条件的子树就行旋转规格来确保av树的平衡条件一直成立。在AVL树中有LL,LR,RR和RL四种旋转方式。

                  下面给出几个示例:

                  依次插入3,5,6,2,1,4

                  按照和二叉树插入的方式一样,插入3,5,6:

                  现在不平横了,3节点左子树的高度为-1(空树为-1),右子树为1,相差为2,不平衡,插入在3节点的右子树的右子树,这种情况称为RR,转换为,这样就平衡了。继续插入2和1,情况如下:节点3失去平衡,1插在3的左子树的左子树,LL情况,需要旋转,如下:树重新平衡,现在继续插入4,如下:,节点5失去平衡,4插在它的左子树的右子树上,这种情况为LR,需要两次旋转,第一次为RR,5的左子树,然后LL5这棵树。变换后如下:

就不一一分析了,下面是实现代码。

/************************************************
*
*author:周翔
*e-mail:604487178@qq.com
*blog:http://blog.csdn.net/zhx6044
*
*
*************************************************/

#ifndef AVLTREE_HPP
#define AVLTREE_HPP

#include "linkQueue.hpp"

template <typename T>
T max(const T &t1, const T &t2)
{
    return (t1 < t2) ? t2 : t1 ;
}

template <typename T>
class AvlTree
{
public:
    AvlTree();
    ~AvlTree();
    bool find(const T& t) const;
    bool insert(const T &t);
    void remove(const T &t);
    bool isEmpty() const;
    void clear();
    int height(typename AvlTree::node *n);
    /**
     * @brief levelTraverse 层虚遍历
     * @param os
     */
    void levelTraverse(std::ostream &os = std::cout) const;
private:

    typedef enum {LEFT, RIGHT} TreeType;
    struct node {
        T data;
        node *lc,*rc;
        int height;//高度
        node():lc(0),rc(0),height(0){

        }
        node(const T &t,node *_lc = 0, node *_rc = 0,int _hei = 0):
            data(t),
            lc(_lc),
            rc(_rc),
            height(_hei){

        }
    };

    node *root;

    bool insert(const T &t, node *&n);
    bool remove(const T &t, node *&n);
    void clear(node *n);
    //四种旋转,
    void LL(node *&n);
    void RR(node *&n);
    void LR(node *&n);
    void RL(node *&n);
};

template <typename T>
inline
AvlTree<T>::AvlTree():root(0)
{

}


template <typename T>
AvlTree<T>::~AvlTree()
{
    clear();
}

template <typename T>
void AvlTree<T>::clear(node *n)
{
    if (n->lc != 0) {
        clear(n->lc);
    }
    if (n->rc != 0) {
        clear(n->rc);
    }
    delete n;
}

template <typename T>
void AvlTree<T>::clear()
{

    if (!isEmpty())
        clear(root);
}


template <typename T>
inline
bool AvlTree<T>::isEmpty() const
{
    return root == 0;
}

template <typename T>
inline
int AvlTree<T>::height(node *n)
{
    return (n == 0) ? -1 : n->height;
}

template <typename T>
void AvlTree<T>::LL(node *&n)
{
    node *p = n;//暂存n
    n = n->lc;//左子树作为根节点
    p->lc = n->rc;//右子树作为原来根的左子树
    n->rc = p;//原来根节点作为新节点的右子树
    p->height = max(height(p->lc),height(p->rc)) + 1;//先做子树的高度
    n->height = max(height(n->lc),height(n->rc)) + 1;

}

template <typename T>
void AvlTree<T>::RR(node *&n)
{
    node *p = n;
    n = n->rc;
    p->rc = n->lc;
    n->lc = p;
    p->height = max(height(p->lc),height(p->rc)) + 1;
    n->height = max(height(n->lc),height(n->rc)) + 1;
}

template <typename T>
void AvlTree<T>::LR(node *&n)
{
    RR(n->lc);
    LL(n);
}

template <typename T>
void AvlTree<T>::RL(node *&n)
{
    LL(n->rc);
    RR(n);

}

template <typename T>
bool AvlTree<T>::find(const T &t) const
{
    node *p = root;
    while (p != 0 && p->data != t) {
        if (p->data < t) {
            p = p->rc;
        } else {
            p = p->lc;
        }
    }
    return ((p == 0) ? false:true);
}

template <typename T>
bool AvlTree<T>::insert(const T &t)
{
    return insert(t,root);
}

template <typename T>
bool AvlTree<T>::insert(const T &t, node *&n)
{
    bool re = false;
    if (n == 0) {
        n = new node(t);
        re = true;
    } else {
        if (t < n->data) {
            re = insert(t,n->lc);//插入到左子树
            if (height(n->lc) - height(n->rc) == 2) {//子树高度差超过1
                if (t < n->lc->data) {//插入的值小于左子树的值,说明还要插在左子树的左子树
                    LL(n);//做LL旋转
                } else {
                    LR(n);//做LR旋转
                }
            }
        } else {
            re = insert(t,n->rc);
            if (height(n->rc) - height(n->lc) == 2) {
                if (t < n->rc->data) {
                    RL(n);
                } else {
                    RR(n);
                }
            }
        }
    }
    n->height = max(height(n->lc),height(n->rc)) + 1;
    return re;
}

template <typename T>
void AvlTree<T>::remove(const T &t)
{
    remove(t,root);
}

template <typename T>
/**
 * @brief AvlTree<T>::remove
 * @param t
 * @param n
 * @return
 * 只讨论左子树,右子树情况对称,删除的节点都在P的左子树上
 * 1.P节点平衡因子为0,删除节点x,使其某棵子树变矮,p的平衡因子变为-1或1,树的高度不变,整棵树也不变
 * 2.P节点平衡因子为-1或1,删除P较高子树的节点,P平衡因子为0,树高发生了变化,需要继续向上规格
 * 3.P节点平衡因子为-1或1,删除P较矮子树的节点,P不平横,需要规格,树高如果变化,需要继续向上规格
 * 3.1P的右子树的平衡因子为0,做RR,子树高度不变,不许要规格
 * 3.2P的右子树的平衡因子与P相同,做一个RR,子树高度变化,需要继续规格
 * 3.2P的右子树的平衡因子与P相反,RL,子树高度变化,需要贵徐规格
 */
bool AvlTree<T>::remove(const T &t, node *&n)
{
    bool re = true;//是否需要规格
    TreeType flag;//标识是左子树还是右子树
    if (n == 0) {
        re = false;
    } else {
        if (t < n->data) {
            re = remove(t,n->lc);
            flag = LEFT;
        } else {
            if (t > n->data) {
                re = remove(t,n->rc);
                flag = RIGHT;
            } else {
                //t = n->data
                if (n->lc != 0 && n->rc != 0) {
                    node *p = n->rc;
                    while (p->lc != 0) p = p->lc;
                    n->data = p->data;
                    re = remove(p->data,n->rc);
                    flag = RIGHT;
                    } else {
                    node *p = n;
                    n = (n->rc == 0) ? n->lc : n->rc;
                    delete p;
                    re = false;
                }
            }
        }
    }
    if (re) {
        int t;
        switch (flag) {
        case LEFT://左子树
            t = height(n->lc) + 1 - height(n->rc);//左子树删除一个节点,现在的+1原来的
            if (t == 0) {//
                re = false;
            } else {
                if (re == 1) {//说明左子树较高
                    re = true;
                } else {
                    int t2 = height(n->rc->lc) - height(n->rc->rc);
                    switch (t2) {
                    case 0:
                        RR(n);
                        re = false;
                        break;
                    case -1://左子树矮,连个平衡因子相同,为-1
                        RR(n);
                        re = true;
                        break;
                    default:
                        RL(n);
                        re = true;
                        break;
                    }
                }

            }
            break;
        case RIGHT://右子树
            t = height(n->lc)  - (height(n->rc)+1);//右子树删除一个节点,现在的+1原来的
            if (t == 0) {//
                re = false;
            } else {
                if (re == -1) {//说明右子树较高
                    re = true;
                } else {//较矮的树
                    int t2 = height(n->lc->lc) - height(n->lc->rc);
                    switch (t2) {
                    case 0:
                        LL(n);
                        re = false;
                        break;
                    case 1://右子树矮,连个平衡因子相同,为1
                        LL(n);
                        re = true;
                        break;
                    default:
                        LR(n);
                        re = true;
                        break;
                    }
                }

            }
            break;
        default:
            break;
        }
    }

    return re;


}

template <typename T>
void AvlTree<T>::levelTraverse(std::ostream &os) const
{
    LinkQueue<node*> queue;
    queue.enqueue(root);
    while(!queue.isEmpty()) {
        node *t = queue.dequeue();
        if (t != NULL) {
            os << t->data << "  ";
            queue.enqueue(t->lc);
            queue.enqueue(t->rc);
        }
    }
}





#endif // AVLTREE_HPP


#include "avlTree.hpp"



int main()
{
    AvlTree<int> avlt;
    int arr[]={3,5,6};
    for(int i = 0;i < 3;++i) {
        avlt.insert(arr[i]);
    }
    avlt.levelTraverse();
    avlt.insert(2);
    std::cout << '\n';
    avlt.levelTraverse();
    avlt.insert(1);
    std::cout << '\n';
    avlt.levelTraverse();
    avlt.insert(4);
    std::cout << '\n';
    avlt.levelTraverse();
}





© 著作权归作者所有

上一篇: 平衡二叉树
下一篇: 平衡二叉树
首席吹牛官
粉丝 9
博文 368
码字总数 191938
作品 0
闵行
程序员
私信 提问
平衡二叉树

形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是: 一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。...

晨曦之光
2012/04/13
553
0
数据结构查找实验之平衡二叉树代码实例

数据结构查找实验之平衡二叉树代码实例 Problem Description 根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 Input 输入一组测试数据。数据的第1行给出一个正整数N(n...

动感超人_Crush
2017/12/21
0
0
[剑指offer] 平衡二叉树

本文首发于我的个人博客:尾尾部落 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路 定义:平衡二叉查找树,简称平衡二叉树。 可以是空树。 假如不是空树,任何一个结点的...

繁著
2018/08/08
0
0
小蚂蚁学习数据结构(34)——平衡二叉树的概念

平衡二叉树的作用 由于二叉排序树的结构可能不平衡,导致对树的运算的时间复杂度增加。 调整二叉排序树的结构,使其始终成为平衡的状态——平衡二叉树。 平衡二叉树的定义 若一个二叉树中每个...

嗜学如命的小蚂蚁
2016/02/09
213
0
数据结构实验之查找二:平衡二叉树

数据结构实验之查找二:平衡二叉树 Time Limit: 400MS Memory Limit: 65536KB Submit Statistic Problem Description 根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 ...

Horizonhui
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

消息中间件——RabbitMQ的高级特性

前言 前面我们介绍了RabbitMQ的安装、各大消息中间件的对比、AMQP核心概念、管控台的使用、快速入门RabbitMQ。本章将介绍RabbitMQ的高级特性。分两篇(上/下)进行介绍。 消息如何保障100%的...

Java架构师ya七
28分钟前
6
0
如何编写高质量的 JS 函数(1) -- 敲山震虎篇

本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/7lCK9cHmunvYlbm7Xi7JxQ 作者:杨昆 一千个读者,有一千个哈姆雷特。 此系列文章将会从函数的执行机制、鲁棒性、函...

vivo互联网技术
58分钟前
5
0
学会这5个Excel技巧,让你拒绝加班

在网上,随处都可以看到Excel技巧,估计已看腻了吧?但下面5个Excel技巧会让你相见恨晚。关键的是它们个个还很实用 图一 技巧1:快速删除边框 有时当我们处理数据需要去掉边框,按Ctrl+Shif...

干货趣分享
今天
11
0
JS基础-该如何理解原型、原型链?

JS的原型、原型链一直是比较难理解的内容,不少初学者甚至有一定经验的老鸟都不一定能完全说清楚,更多的"很可能"是一知半解,而这部分内容又是JS的核心内容,想要技术进阶的话肯定不能对这个...

OBKoro1
今天
10
0
高防CDN的出现是为了解决网站的哪些问题?

高防CDN是为了更好的服务网络而出现的,是通过高防DNS来实现的。高防CDN是通过智能化的系统判断来路,再反馈给用户,可以减轻用户使用过程的复杂程度。通过智能DNS解析,能让网站访问者连接到...

云漫网络Ruan
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部