红黑树是一种扩充的二叉搜索树（BST）。给定一颗结点个数为n的红黑树在最坏的情况下，红黑树的删除结点操作的时间复杂度是（）

A、左、右子树的高度均相同

B、左、右子树高度差的绝对值不超过1

C、左子树高度均大于右子树高度

D、左子树的高度均小于右子树的高度

为使二叉搜索树结构支持多个相等数据项的并存，需要增加一个BST::searchAll(e)接口，以查找出与指定目标e相等的所有节点(如果的确存在)。

a)试在BST模板类(教材185页代码7.2)的基础上，扩充接口BST::searchAll(e)。要求该接口的时间复杂度不超过o(k+h)，其中h为二叉搜索树的高度，k为命中节点的总数;

b)同时，改进原有的BST::search(e)接口，使之总是返回最早插入的节点e—即先进先出。

【Test-9-3】假设二叉树存放于二叉链表中，树中结点的关键字值互不相同。下面算法的功能是：判别给定的二叉树是否二叉排序树。请在空白处填入正确的语句。 void binSearchTree(BiTNode *t, BiTNode *&pr, int& bs) { //在以 t 为根的子树中判断该子树是否二叉排序树。是则引用参数 bs 为 1，否则 bs //为 0。引用参数 pr 是当前子树根结点 t 的前驱指针，在主调程序中应为各参数初 //始化： t 赋予根结点指针 root， pr 赋予 NULL， bs 赋予 1。 if(t != NULL && bs) { _______________①_________________; //递归到左子树判断 if(pr == NULL) { pr = t; //t 为中序第一个结点 bs = 1; } else { if(__________②___________) { pr = t; bs = 1; } else bs = 0; } if(bs) ____________③__________________; //递归到右子树判断 } }