基本算法之平衡二叉树

平衡二叉树

摘自百度:

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 $F(n)=F(n-1)+F(n-2)+1$ 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量

AVL树

还是摘自百度

AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

根据AVL树的定义，AVL树中的任意结点的平衡因子只可能是-1（右子树高于左子树）、0或者1（左子树高于右子树），在某些图中也会表示为绝对高度差，即0，1，2这种形式，请注意理解。

BalanceFactor = height(left-sutree) − height(right-sutree)

![AVL树][2]

AVL平衡二叉树结构定义

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;
    }
};

AVL平衡二叉树操作

平衡的调整共有四种情况：分别为LL,LR,RR,RL。
当父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，就要对树进行操作

例子

我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图
中我们认为树的高度为h=2。

![AVL][3]

AVL树的插入时的失衡与调整

• 失衡与调整方向

  平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。(然后你要问啥是最小失衡子树 了？🤷‍ 😶 。。。 )

• 最小失衡子树

  在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的，如下。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

例子1 在图A中。2结点（左子树树高-右子树树高）的绝对值=2。同理，3结点的平衡因子也为2.此时同时存在了两棵不平衡子树，而以3为根的树是最小的不平衡子树。我们只要将其以3为中心，将最小不平衡树向左旋转，即可得到平衡二叉树，如图B。

![val balance][4]

例子2

红黑树

又摘自百度

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为”对称二叉B树”，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

特点

1. 所有节点的颜色是红色或者黑色；(很有道理的样子，🙄🙄🙄🙄🙄🙄)
2. 根节点是黑色；
3. 所有的叶子节点是黑色（叶子节点包含NULL）；
4. 每个红色的节点都有两个黑色的子节点(即红节点的儿子和父亲都必须为黑)；
5. 从任意节点出发，其到叶子节点树尾NULL结点的每一条路径上都包含相同数目的黑色节点

![rbT][5]

树的旋转知识

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些节点的颜色及指针结构，以达到对红黑树进行插入、删除节点等操作时，红黑树依然能保持它特有的性质（如上文所述的，五点性质）。

• 左旋

  当在某个节点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为树内任意左孩子而不是NIL[T]的节点。
  左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树新的根，而y的左孩子b则成为pivot的右孩子。

![rgTl][6]

• 右旋

![rgTr][7]

参考

• https://blog.csdn.net/u014634338/article/details/42465089
• https://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html
• https://blog.csdn.net/Sun_TTTT/article/details/65445754
• https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md