扩充的二叉树 第4章讨论过扩充的二叉树的概念。扩充的二叉树是满 二叉树,新增加的空树叶(以下称为外部结点)的个数 等于原来二叉树的结点(以下称为内部结点个数加1 在扩充的二叉搜索树里,关键码值最小的内部结点的 左子女(外部结点代表了值小于该内部结点的可能关 键码的集合;关键码值最大的内部结点的右子女(外部 结点)代表了值大于该内部结点的可能关键码的集合 除此之外,每个外部结点代表其值处于原来二叉搜索 树的两个相邻结点的关键码值之间的可能关键码的集 北京大学信息学院 版权所有,转载或翻印必究 Page 31
北京大学信息学院 ©版权所有，转载或翻印必究 Page 31 扩充的二叉树 ◼ 第4章讨论过扩充的二叉树的概念。扩充的二叉树是满 二叉树，新增加的空树叶(以下称为外部结点)的个数 等于原来二叉树的结点(以下称为内部结点)个数加1 ◼ 在扩充的二叉搜索树里，关键码值最小的内部结点的 左子女(外部结点)代表了值小于该内部结点的可能关 键码的集合；关键码值最大的内部结点的右子女(外部 结点)代表了值大于该内部结点的可能关键码的集合 ◼ 除此之外，每个外部结点代表其值处于原来二叉搜索 树的两个相邻结点的关键码值之间的可能关键码的集 合
路径长度 外部路径长度E定义为从扩充的 叉树的根到每个外部结点的路 径长度之和。 内部路径长度I定义为扩充的二 叉树里从根到每个内部结点的路 径长度之和 北京大学信息学院 版权所有,转载或翻印必究 Page 32
北京大学信息学院 ©版权所有，转载或翻印必究 Page 32 路径长度 ◼ 外部路径长度E定义为从扩充的 二叉树的根到每个外部结点的路 径长度之和。 ◼ 内部路径长度I定义为扩充的二 叉树里从根到每个内部结点的路 径长度之和
二叉搜索树里检索算法 ■在二叉搜索树里检索算法十分简单:首先用待 査的关键码与二叉搜索树的根结点进行比较, 若比较相等,则找到了要检索的关键码; ■若比较不等,具待查关键码值小于根结点的关 键码值,则下一次与根的左子树的根比较;否 则与根的右子树的根比较。 如此递归地进行下去,直到某一次比较相等, 检索成功;或一直比较到树叶都不相等,检索 失败。 北京大学信息学院 版权所有,转载或翻印必究 Page 33
北京大学信息学院 ©版权所有，转载或翻印必究 Page 33 二叉搜索树里检索算法 ◼ 在二叉搜索树里检索算法十分简单：首先用待 查的关键码与二叉搜索树的根结点进行比较， 若比较相等，则找到了要检索的关键码； ◼ 若比较不等，具待查关键码值小于根结点的关 键码值，则下一次与根的左子树的根比较；否 则与根的右子树的根比较。 ◼ 如此递归地进行下去，直到某一次比较相等， 检索成功；或一直比较到树叶都不相等，检索 失败
检索一个关键码的比较次数 在检索过程中,每进行一次比较,就进入下面 一层。因此,对于成功的检索,比较的次数就是 关键码所在的层数加1。对于不成功的检索,被 检索的关键码属于哪个外部结点代表的可能关键 码集合,比较次数就等于此外部结点的层数 ■在二叉搜索树里,检索一个关键码的平均比较 次数为 AsL(n) ∑(1+1)+∑q WI 北京大学信息学院 版权所有,转载或翻印必究 Page 34
北京大学信息学院 ©版权所有，转载或翻印必究 Page 34 检索一个关键码的比较次数 ◼在检索过程中，每进行一次比较，就进入下面 一层。因此，对于成功的检索，比较的次数就是 关键码所在的层数加1。对于不成功的检索，被 检索的关键码属于哪个外部结点代表的可能关键 码集合，比较次数就等于此外部结点的层数 ◼在二叉搜索树里，检索一个关键码的平均比较 次数为 1 1 0 1 ( ) (1 1) n n i i i i i ASL n p q l W = = = + +
参数意义 其中1,是第个内部结点的层数,是第个外部 结点的层数, p1是检索第个内部结点所代表的关键码的频率 q;是被检索的关键码属于第个外部结点代表的 可能关键码集合(即处于第个和第计1个内部结 点之间)的频率。p,q也叫做结点的权 W=∑p1+∑q 0 北京大学信息学院 版权所有,转载或翻印必究 Page 35
北京大学信息学院 ©版权所有，转载或翻印必究 Page 35 参数意义 ◼ 其中1i，是第i个内部结点的层数，是第i个外部 结点的层数， ◼ pi是检索第i个内部结点所代表的关键码的频率 ◼ qi是被检索的关键码属于第i个外部结点代表的 可能关键码集合(即处于第i个和第i+1个内部结 点之间)的频率。pi，qi也叫做结点的权 ◼ = = = + n i 1 n i 0 W pi qi