问题
问答题
设一组记录的关键字按以下次序进行插入:4、5、7、2、1、3、6,构造生成一棵平衡二叉树的过程。
答案
参考答案: 平衡二叉树的特点为:左、右子树深度之差的绝对值不大于1。
构造二叉平衡(查找)树的方法是:在插入过程中,采用平衡旋转技术。基本思想是:在构造二叉排序树的过程中,每当插入一个结点时,首先检查是否因插入而破坏了树的平衡性,如果是因插入结点而破坏了树的平衡性,则找出其中最小不平衡子树,在保持排序树特性的前提下,调整最小不平衡子树中各结点之间的连接关系,以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树。所谓最小不平衡子树,是指以离插入结点最近、且平衡因子绝对值大于1的结点作根结点的子树。因此,平衡二叉树上所有结点的平衡因子可能是-1,0,1。
采用平衡旋转技术生成平衡二叉树的过程如下所示:
此题构造过程如下: