平衡二叉树
：首先要求是一棵二叉排序树,然后要求每个结点的平衡因子（左子树高度减右子树高度）在1,0,-1之间.
给定二叉树根节点root, 编程判断一个二叉树是否为平衡二叉树
算法思路：按照某种遍历规则遍历二叉树,在遍历的过程中,检查根是不是大于左子树（不空时）的根而且小于右子树（不空时）的根,并计算左右子树高度之差是在在1,0,-1之间.如果所有结点都满足这两条件则为平衡二叉树
平均查找的时间复杂度为O(log n).
平衡树的查找过程和排序树的相同.在查找过程中和给定值进行比较关键字个数不超过树的深度.
如果二叉树的元素个数为n,那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了.它的时间复杂度相对于其他数据结构如数组等是最优的.
是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.常用算法有红黑树、AVL、Treap、伸展树等.
扩展资料：
二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树算法有五种基本形态：
(1)空二叉树——(a)
注意：尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形.
它或者是一棵空树,或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1..常用算法有：红黑树、AVL树、Treap等.平衡二叉树的调整方法平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树.具体步骤如下：⑴ 每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点；⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点；⑶ 判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整；⑷ 如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突；如果是LR型或LR型,则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突；
平衡二叉树通过一组平衡化旋转规则,使得各个子树的形态发生变化,从而使树高趋近于lg n.
常见的平衡二叉树有如下的几种
AVL树 其主要思想是维护树高,使之平衡
红黑树 其主要思想是对节点染色,对不同颜色的节点采用不同的判断,编程复杂度较高
AA树 是红黑树的一种特例
伸展树 有四种旋转规则
Treap 其主要思想是对每个节点附加随机权值,并根据权值维护为堆,所以呢被命名为Tree+Heap=Treap,其编程复杂度较低,性价比较高.
以上就是土嘎嘎小编为大家整理的php代码实现平衡二叉树详解相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！