二叉排序树的查找、插入规则是什么?

核心考点

二叉排序树的性质、查找路径、插入位置确定及平均/最坏复杂度，重点掌握“左小右大”和“插入为叶结点”。

参考答案(答题要点)

1.二叉排序树性质：若左子树非空，则左子树上所有结点关键字均小于根结点关键字;若右子树非空，则右子树上所有结点关键字均大于根结点关键字;左右子树也分别是二叉排序树。中序遍历可得到递增有序序列。

2.查找规则：从根结点开始比较。若待查关键字等于当前结点，查找成功;若小于当前结点，进入左子树继续查找;若大于当前结点，进入右子树继续查找。若走到空指针仍未找到，则查找失败。

3.插入规则：先按查找过程从根开始比较，确定插入位置。若树中已存在相同关键字，通常不插入重复结点;若查找失败，则将新结点作为叶结点插入，插到最后一个访问结点的左孩子或右孩子处：小于该结点插左孩子，大于该结点插右孩子。

4.复杂度：查找和插入的时间复杂度与树高有关。平均情况接近O(logn)，最坏情况树退化成单支树时为O(n)。插入操作本身不移动已有结点，只修改指针。

5.总结：查找抓“从根出发，左小右大，直到相等或空”;插入抓“先查找失败位置，再作为叶结点挂上”。二叉排序树的中序遍历有序，是其重要性质。

易错提醒

比较必须从根结点开始逐层进行，不能只与某个局部结点比较。插入的新结点一定成为叶结点，不会插入到已有结点之间。相同关键字一般不重复插入，具体看题目约定。最坏复杂度是O(n)，不是任何情况下都O(logn)。删除结点较复杂，不要与插入规则混淆。

今日小测

在二叉排序树中插入一个新结点时，新结点一定成为叶子结点吗?

答案：一定。按查找失败的位置插入，新结点作为最后一个访问结点的左孩子或右孩子，因此成为叶结点。