数据结构学习笔记——查找算法中的树形查找（二叉排序树）_二叉排序树的平均查找长度

一、树形查找

查找算法中，基于树这种数据结构进行查找即为树形查找，可将其分为二叉排序树、平衡二叉树和B树三种树形查找方法：

二、二叉排序树的定义

二叉排序树也称为二叉查找树或二叉搜索树（注意：与二分查找的判定树不同），其中各结点值的大小关系是：左子树<根结点<右子树，且左、右子树也是一棵二叉排序树满足其条件，若对该树进行中序遍历，可得到一个递增的序列。例如以下都是二叉排序树：

二叉排序树的查找过程与折半查找（二分查找）相似，即折半查找的判定树本身就是一棵二叉排序树。

折半查找可通过一棵二叉树表示，且是一棵平衡二叉树，它的中序遍历序列是递增的，将当前查找的中间元素mid为根结点，左子表和右子表分别作为根结点的左子树和右子树（左<根<右）：

三、二叉排序树的插入和构造

对一棵空二叉排序树进行插入，则直接将结点依次插入即可，遵循二叉排序树各结点值的关系，若插入的结点小于根结点的值，则插入到左子树，否则插入到右子树。

例如，对于查找的关键字序列{53，17，12，66，58，70，87，25，56，60}构造二叉排序树。

1、从空树开始，依次插入元素，首先插入53，如下：

2、插入元素17，由于17<53，所以放在53的左子树：

3、插入元素12，由于12<17，放在17的左子树：

4、插入元素66，由于66>53，放在53的右子树：

5、插入元素58，由于58<66，放在66的左子树：

6、插入元素70，由于70>66，放在66的右子树：

7、插入元素87，由于87>70，放在70的右子树：

8、插入元素25，由于25>17，放在17的右子树：

9、插入元素56，由于56<58，放在58的左子树：

10、插入元素60，由于60>58，放在58的右子树：

可以看出，若将这棵树进行中序遍历，得到的中序遍历序列为：
{12、17、25、53、56、58、60、66、70、87}，它是一个递增序列。

四、二叉排序树的平均查找长度

（一）二叉排序树的查找

二叉排序树的查找是由根结点开始，然后沿着二叉树的分支依次向下查找，若要查找的元素与当前根结点相等，则查找成功；若小于根结点，则在当前根结点的左子树上继续查找，若大于，则在当前根结点的右子树上继续查找，依次递归。

• 二叉排序树的查找效率取决于树的高度，这里给出平衡二叉树的定义（若二叉排序树的左、右子树的高度之差的绝对值不超过1，则称为平衡二叉树），所以平均查找长度为O(log₂n)。
  
• 对n个结点构造二叉排序树，理想情况下，即为一棵满二叉树时的高度，类比于完全二叉树，即树的高度为h=⌈log₂(n+1)⌉，所以二叉排序树的最小深度为⌈log₂(n+1)⌉；而若二叉排序树只是一个单支树（左或右单支树），此时最坏情况，即树的高度为元素的个数，则其最大深度为n。
  

对于一棵含有n个结点的二叉树，当它为完全二叉树时，具有最小高度，最小高度为h=⌈log₂(n+1)⌉或⌊log₂n⌋+1（其中 ⌈ ⌉表示向上取整，取比自己大的最小整数，⌊ ⌋表示向下取整，取比自己小的最大整数）；当它为一棵单支树时具有最大高度，即为一个线性表。

（二）二叉排序树的比较次数

• 对n个结点的二叉排序树中，查找某个元素，最坏情况下是当构造的二叉树为单支树时，为n层，此时查找树中最后一个元素或不存在的元素时，需要进行n次比较。

例如，对于查找的关键字序列{52，26，14，32，71，60，93，58，24，41}构造二叉排序树，求在该树中查找元素60需要进行的比较次数和比较的结点。

构造二叉排序树如下：

对元素60进行查找，首先与根结点52进行比较，由于60>52，沿着右子树依次向下比较，60<71，向下元素71的左子树向下继续比较，60=60，查找成功，故比较次数为3，依次比较的元素为52、71、60。

（三）二叉排序树的平均查找长度计算

在等概率的情况下，二叉排序树查找成功的平均查找长度ASL_成功=每层层数乘以每层结点个数之和除以二叉排序树的结点总个数。

例如，下面这个二叉排序树，在等概率下计算其查找成功的平均查找长度：

元素总数为10，其中第一层元素个数为1，第二层为2，第三层为4，第四层为3，所以可得查找成功的平均查找长度：
$$AS{L}_{成功}=\frac{(1\times 1+2\times 2+3\times 4+4\times 3)}{10}=\frac{29}{10}$$

五、二叉排序树的删除

在二叉排序树中删除一个结点，不能直接删除，要确保删除后的二叉排序树的性质不变，删除结点分为以下三种情况：

（一）删除叶子结点

• 若删除的结点是二叉排序树的叶子结点，则可以直接删除，删除后并不影响二叉排序树的性质。

例如，删除下列二叉排序树中的87结点：

直接删除：

（二）删除结点存在左孩子或右孩子

• 若删除的结点存在左孩子或右孩子时，则让该结点的子树成为其父结点的子结点。

例如，删除下列二叉排序树中的70结点：

删除后，用该结点的子树（左/右孩子），即87代替它成为删除结点的父节点的子结点：

（三）删除结点存在左孩子和右孩子

• 若删除结点存在左孩子和右孩子，则令该结点的前驱/后继代替其本身（用中序遍历序列中该结点的前驱/后继代替），调整后的树仍是二叉排序树。

例如，删除下列二叉排序树中的66结点：

可得中序遍历序列{12，17，25，53，56，58，60，66，70，87}。

由于66结点左孩子和右孩子都存在，所以根据其中序遍历序列{12，17，25，53，56，58，60，66，70，87}，选择遍历序列中66的第一个子女代替，即70代替，如下：

或者也可以用遍历序列中66的前驱结点60代替，如下：

六、二叉排序树与二分查找对比

• 相同的关键字根据插入顺序的不同可以形成不同的二叉排序树，而二分查找的判定树是唯一的。

• 二叉排序树中插入和删除结点操作只需修改指针，平均时间复杂度为O(log₂n)，而二分查找中，由于表中的元素顺序是有序的，所以插入和删除结点操作的时间复杂度为O(n)。

当有序表是静态查找表时，采用顺序表作为存储结构较合适，且采用二分查找；而若有序表是动态查找表时，采用二叉排序树作为其存储结构。