掌握顺序查找、折半查找；二叉排序树的创建、查找、插入、删除。

一、顺序查找

顺序查找，也称为线性查找，是一种简单的查找方法。其基本思想是从表的一端开始，逐个比较关键字，直到找到为止，或查找到最后一个记录为止。

顺序查找的时间复杂度为O(n)。

二、折半查找

折半查找，也称为二分查找，是一种高效的查找方法。其基本思想是在有序表中，将待查找的关键字与中间位置的关键字进行比较，如果相等，则查找成功；否则根据比较结果确定继续查找左半部分还是右半部分，直至查找成功或查找失败为止。

折半查找的时间复杂度为O(log2n)。

三、二叉排序树

二叉排序树，也称为二叉查找树，是一种特殊的二叉树。其特点是左子树上的所有节点的关键字小于根节点的关键字，右子树上的所有节点的关键字大于根节点的关键字。因此，对于每个节点，它的左子树和右子树也都是二叉排序树。

二叉排序树的基本操作包括创建、查找、插入和删除。

（1）创建二叉排序树

创建二叉排序树的方法是依次插入节点。对于每个节点，如果根节点为空，则将该节点作为根节点；否则，将该节点插入到左子树或右子树中。

（2）查找节点

查找节点的方法与折半查找相似，即从根节点开始，比较待查找节点的关键字与当前节点的关键字的大小关系，如果相等则查找成功；否则，根据比较结果确定继续查找左子树还是右子树，直至查找成功或查找失败为止。

（3）插入节点

插入节点的方法与创建二叉排序树相似，即从根节点开始，比较待插入节点的关键字与当前节点的关键字的大小关系，如果待插入节点的关键字小于当前节点的关键字，则将该节点插入到左子树中；否则，将该节点插入到右子树中。

（4）删除节点

删除节点分为三种情况：

① 待删除节点没有子节点

直接删除该节点即可。

② 待删除节点只有一个子节点

将该节点的子节点与该节点的父节点相连，然后删除该节点。

③ 待删除节点有两个子节点

将该节点的前驱节点（或后继节点）的值赋给该节点，然后删除该前驱节点（或后继节点）。

二叉排序树的时间复杂度与树的深度相关，最坏情况下的时间复杂度为O(n)，但在平均情况下时间复杂度为O(log2n)，因此它是一种高效的查找方法。