问答题
在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树的结点数加1。试写一时间复杂度为D(10gn)的算法，确定树中第尼个结点的位置。【大连理工大学2005三、2 (45／3分)】
【正确答案】正确答案：设平衡二叉排序树根结点的指针是pbst， (1)若pbst一>lsize=k，则根结点即为所求； (2)按根结点的位序与k的关系，k小到左(大到右)子树去查找：根结点的左右子女分别是第pbst一>lchild一>lsize和pbst->lsize+pbst一>rchild->lsize个结点。
【答案解析】