(b) 高度为7(a) 高度为41×1+2×2+3×3+1×4ASLa=2.5771×1+1×2+1×3+1×4+1×5+1×6+1×7ASLb4716/81
1 2 3 4 5 6 7 （b）高度为7 5 2 6 1 4 3 7 （a）高度为4 16/81
那么如何分析二叉排序树的查找性能呢？有如下两种分析方法。给定含n个关键字的集合，假设所有关键字不相同，对应有n！个关键字序列，每个关键字序列构造一棵二叉排序树，所有这些二叉排序树中查找每个关键字的平均时间为o(1og2n)。给定含n个关键字的关键字序列构造一棵二叉排序树。其中查找性能最好的是高度最小的二叉排序树，最好查找性能为0(1og2n)。查找性能最坏的是高度为n的二叉排序树（单支树），最坏查找性能为o(n)。平均情况由具体的关键字序列来确定。所以常说二叉排序树的时间复杂度在o(log,n)和o(n)之间，就是指这种分析方法。17/81
那么如何分析二叉排序树的查找性能呢？有如下两种分析方法。 给定含n个关键字的集合，假设所有关键字不相同，对应有n!个 关键字序列，每个关键字序列构造一棵二叉排序树，所有这些二 叉排序树中查找每个关键字的平均时间为O(log2n)。 给定含n个关键字的关键字序列构造一棵二叉排序树。其中查找 性能最好的是高度最小的二叉排序树，最好查找性能为O(log2n)。 查找性能最坏的是高度为n的二叉排序树（单支树），最坏查找 性能为O(n)。平均情况由具体的关键字序列来确定。所以常说二 叉排序树的时间复杂度在O(log2n)和O(n)之间，就是指这种分析 方法。 17/81
【例9.9】在含有27个结点的二叉排序树上，查找关键字为35的结点，以下4个选项中哪些是可能的关键字比较序列？A.28,36,18,46,35B.18,36,28,46,35C.46, 28,18, 36, 35D.46,36, 18,28,35查找序列（k1，k2，，kn）的查找树画法是，每一层只有一个结点，首先k,为根结点，再依次画出其他结点，若kit1<ki，则ki+的结点作为k,结点的左孩子，否则作为右孩子。查找树是原来二叉排序树的一部分，也一定构成一棵二叉排序树。18/81
【例9.9】在含有27个结点的二叉排序树上，查找关键字为35的结点，以下 4个选项中哪些是可能的关键字比较序列？ A.28，36，18，46，35 B.18，36，28，46，35 C.46，28，18，36，35 D.46，36，18，28，35 查找序列（k1，k2，.，kn）的查找树画法是，每一层只有一个结 点，首先k1为根结点，再依次画出其他结点，若ki+1<ki，则ki+1的结 点作为ki结点的左孩子，否则作为右孩子。 查找树是原来二叉排序树的一部分，也一定构成一棵二叉排序树。 18/81
1828A.28,36,18,46,353636B.18,36,28,46,3528XXC.46,28,18,36,351846D.46,36,18,28,3546463628X是一棵二叉排序V18182636人19/81
A.28,36,18,46,35 B.18,36,28,46,35 C.46,28,18,36,35 D.46,36,18,28,35 28 36 18 18 36 28 46 46 28 18 36 46 36 18 26 35 是一棵二叉排序√ Ⅹ Ⅹ Ⅹ 19/81
4.二叉排序树的册删除删除关键字与删除结点是一回事。删除一个结点时不能简单地把以该结点为根的子树都删去，只能删除该结点本身，并且还要保证删除后的二叉树仍然满足BST性质。也就是说，在二叉排序树中删除一个结点就相当于删除有序序列（即该树的中序序列）中的一个结点。20/81
4. 二叉排序树的删除 删除关键字与删除结点是一回事。 删除一个结点时不能简单地把以该结点为根的子树都删去，只能删除该 结点本身，并且还要保证删除后的二叉树仍然满足BST性质。也就是说， 在二叉排序树中删除一个结点就相当于删除有序序列（即该树的中序序 列）中的一个结点。 20/81