数据结构 平衡二叉树和B树.ppt

回顾二叉排序树的查找性能 若查找成功则走了一条从根结点到某结点的路径若查找失败则走到一棵空的子树时为止因此最坏情况下其平均查找长度不超过树的高度 具有n个结点的二叉树的高度取决于其形态 回顾二叉排序树的形态 关键字序列为(45,24,53,12,37,93)所构造的二叉排序树如图(a)所示 回顾二叉排序树的形态(续) 如果根据关键字的输入序列构造的二叉树为单枝树则其平均查找长度与顺序查找相同因此在