1. 数据结构,建立平衡二叉排序树
首先插入503、087、512、061、908、124如下图,树平衡
503
/ \
087 512
/ \ \
061 124 908
插入897之后,512节点不平衡,做RL型调整,先围着908右旋,然后围着897右旋
503 503 503
/ \ / \ / \
087 512 -> 087 512 -> 087 897
/ \ \ / \ \ / \ / \
061 124 908 061 124 897 061 124 512 908
/ \
897 908
指针变化就是897右子树变为908这个节点,左子树变为512这个节点,503右子树为897,908,左子树为NULL,512右子树为NULL
然后插入275,653,依旧平衡
503
/ \
087 897
/ \ / \
061 124 512 908
\ \
275 653
然后插入426,087、124节点不平衡,做RR型调整
503 503
/ \ / \
087 897 124 897
/ \ / \ / \ / \
061 124 512 908 -> 087 275 512 908
\ \ / \ \
275 653 061 426 653
\
426
指针变化是087右子树为NULL,503左子树为124,124左子树为087。
2. 二叉排序树的建立的过程中是如何实现平衡
它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1.。
常用算法有:红黑树、AVL树、Treap等。
平衡二叉树的调整方法
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。具体步骤如下:
⑴ 每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点;
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点;
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;
⑷ 如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;如果是LR型或LR型,则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
3. 二叉排序树的建立的过程中是如何实现平衡
它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1.。
常用算法有:红黑树、AVL树、Treap等。
平衡二叉树的调整方法
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。具体步骤如下:
⑴ 每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点;
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点;
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;
⑷ 如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;如果是LR型或LR型,则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
4. 二叉排序树的建立的过程中是如何实现平衡
它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1.。
常用算法有:红黑树、AVL树、Treap等。
平衡二叉树的调整方法
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。具体步骤如下:
⑴
每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点;
⑵
若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点;
⑶
判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;
⑷
如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;如果是LR型或LR型,则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;
5. 平衡二叉树是不是二叉排序树?
平衡树:平衡二叉树
6. 构造一个二叉排序树
二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树:
1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
3. 它的左、右子树也分别为二叉排序树。
7. 平衡二叉树是二叉排序树吗?
平衡二叉树不一定是二叉排序树,平衡二叉树是为了避免二叉排序树高度增长过快,降低二叉排序树性能而设的树,二叉排序树当然不可能都是平衡二叉树。
首先平衡二叉树是特殊的二叉排序树,他的结点元素间存在着偏序关系;其次相对于一般的二叉排序树,平衡二叉树的左右子树的深度差也有不超过1层的约束,这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树,这可以减少二叉树元素查找的深度,从而提升平均查找效率。
应用
平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低,在完成集合的一系列操作中始终保持平衡,为大型数据库的组织、索引提供了一条新的途径。
二叉排序树或者是一颗空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根节点的值。
(2)若右子树不空,则右子树所有结点的值均大于或等于它的根结点的值。
(3)左、右子树也分别为二叉排序树。
8. 平衡二叉树是二叉排序树吗?
是的。
衡二叉树(balanced binary tree)是一种特殊的二叉排序树,它或者为空树,或者每个结点的左右子树都是平衡二叉树,也就是每个结点的左右子树的高度之差只能是-1,0,1三种情况。
平衡二叉树又称AVL树,是由苏联的Georgy Adelson-Velsky和E.M.Landis发明的,并以他们的名字命名。
平衡二叉树的平衡状况由平衡因子(Balance Factor,BF)来衡量。平衡因子定义为当前结点的左子树高度减去右子树的高度之差,其可能取值只有-1,0,1。叶结点的BF都是0。
平衡二叉树的应用价值:
如果能维持平衡二叉树的结构,检索操作就能在O(log n)时间内完成,实现高效检索。
最小不平衡子树:
距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树。(指BF超出合法值)。
最小非平衡子树:
包含插入结点位置,其根结点的BF是1或-1的最小子树。(指BF非0,但BF在合法值范围内)。
以上内容参考:百度百科-平衡二叉查找树