详解平衡二叉树

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

常见的符合平衡二叉树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。很显然，平衡二叉树是在二叉排序树(BST)上引入的，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降，那么AVL就保持住了(BST)的最好时间复杂度O(logn)，所以每次的插入和删除都要确保二叉树的平衡，那么怎么保持平衡呢？

一、B树（多路平衡搜索树）

多路平衡搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。在此二叉搜索树中查找元素 6 需要查找 6 次。

二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列 A，将其改为图 1.2 的方式存储，查找元素 6 时只需比较 3 次，查找效率提升一倍。可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。

二、AVL树（二叉平衡搜索树）

AVL树是高度平衡的二叉树，具有如下几个性质：

1.可以是空树。

2.假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

三、平衡因子

定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。

四、节点结构

定义平衡二叉树的节点结构：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡

    Tree parent; //该结点的父节点

    ElementType val; //结点值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {

        parent = NULL;

        depth = 0;

        lchild = rchild = NULL;

        this->val=val;

    }

};

五、二叉平衡树的应用

智能电网中，与传统路由协议不同，突发性拥塞不再是数据采集的主要风险，风险的新来源是数据流过度集中在网络的关键节点而导致的拥塞。为此,提出了一种能够实现数据平衡的数据采集路由机制用以克服网络拥塞。设计了基于平衡树的路由算法(基于DBMM的路由算法,RA-DBMM)。有效地改善数据拥塞问题,提高系统可靠性和吞吐量。

平衡二叉树大部分操作和二叉查找树类似，这些树形数据结构之间其实都有想通之处，包括各种树的算法也有异曲同工之妙。想学习更多的神奇的算法和数据结构，本站的数据结构和算法教程是你的不二选择。