平衡树数据结构中的二叉树

AVL树(平衡二叉树)定义AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,并且拥有自平衡机制。 构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下F(n)=F(n-1)+F(n-2)+1这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

中文名

平衡树

外文名

Balanced Binary Tree

定义

平衡二叉树

构造

用算法有红黑树

简介

平衡树，即平衡二叉树（BalancedBinaryTree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、SBT等。

动机

对一棵查找树（searchtree）进行查询/新增/删除等动作,所花的时间与树的高度h成比例,并不与树的容量n成比例。 如果可以让树维持矮矮胖胖的好身材,也就是让h维持在O(lgn)左右,完成上述工作就很省时间。 能够一直维持好身材,不因新增删除而长歪的搜寻树,叫做balancedsearchtree（平衡树）。

旋转Rotate——不破坏左小右大特性的小手术

左旋

一棵二叉平衡树的子树，根是Root，左子树是x，右子树的根为RootR，右子树的两个孩子树分别为RLeftChild和RRightChild。 则左旋后，该子树的根为RootR，右子树为RRightChild，左子树的根为Root，Root的两个孩子树分别为x（左）和RLeftChild（右）。

右旋

一棵二叉平衡树的子树，根是Root，右子树是x，左子树的根为RootL，左子树的两个孩子树分别为LLeftChild和LRightChild。 则右旋后，该子树的根为RootL，左子树为LLeftChild，右子树的根为Root，Root的两个孩子树分别为LRightChild（左）和x（右）。

数一下旧的parent左subtree有多少ndoes?右subtree有多少nodes?旋转后新的parent左右subtrees又各有多少nodes?发现右旋的效果会让树的重心往右移;而左旋的效果则是让树的重心往左移。 如果你的树经历过许多insert/remove等等岁月的沧桑,越长越歪,在适当的时候对它进行一下旋转手术,不就可以将它变回矮矮胖胖四平八稳的美丽模样吗?所以左旋与右旋是几种平衡树共同采用的基本手术;只不过不同的平衡树,选择不同的时机/条件来动手术而已。

左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。

非平衡树会影响树中数据的查询，插入和删除的效率。 比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。 数据的排列是一维的，而不是二维的。 在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。 为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的）。 这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。

参考资料

1.Java数据结构之树和二叉树·bbsmax

下一篇：民国四大家族(民国四大家族现在如何)
上一篇：迟子建(迟子建额尔古纳河右岸)