二叉排序树（查找树）

1.什么是二叉排序树呢？（Binary Sort Tree）

二叉排序树具有下列几个特点。

（1）若根节点有左子树，则左子树的所有节点都比根节点小（就是左子树结点要比双亲结点小）。

（2）若根节点有右子树，则右子树的所有节点都比根节点大（就是右子树结点要比双亲结点大）。

（3）根节点的左，右子树也分别为二叉排序树。

其实并不是为了排序，而是为了提升查找和插入删除的效率。

下面是二叉排序树的所示，通过图可以加深对二叉排序树的理解。可以发现，根节点50的前面所有的子结点都比它小，根结点50的两边所有的子结点都比它大

3.下面是二叉排序树常见的操作及策略。

思路：比如我们应插入数字20到这棵二叉排序树中。那么步骤如下：

1)首先将20与根节点进行非常二叉排序树 堆，发现比根节点小，所以再次与根节点的左子树30比较。

2) 发现20比30也应小，所以再次与30的左子树10进行非常。

3) 发现20比10要大，所以就将20插入至10的右子树中。

（2）查找节点（递归）

比如我们应查找节点10，那么思路如下：

1) 还是一样，首先将10与根节点50进行非常大小，发现比根节点要小，所以再次与根节点的左子树30进行比较。

2) 发现10比左子树30要小，所以再次与30的左子树10进行非常。

3) 发现两值相同，即查找成功，返回10的位置。

（3）删除节点（不能因为删除了结点，而使这棵树变得不满足二叉树的特点）

删除节点的状况相对复杂，主要分下列三种情形：

1) 删除的是叶节点(即没有孩子节点的)。比如20，删除它不会破坏原本树的结构，最简洁。如图所示。

2) 删除的是单孩子节点。比如90，删除它后必须将它的小孩节点与自己的父节点相连。情形比第一种复杂一些。

3) 删除的是有左右孩子的节点。

这种状况会稍微复杂一些，我们引入覆盖，再删除的方法进行缓解。也就是曲线解决。直接将有左子树也是右子树的节点干掉似乎不是很好实现，因为这种会破坏二叉排序树的结果。我们可以间接的去做。可以分为下方的两步。

第一步：查找删除节点右子树中最小的哪个值，也就是右子树中位于更左方的哪个节点。然后将这个结点的值的父节点记录下来。并且将该节点的值赋给我们应删除的结点。也就是覆盖。

第二步：然后将右子树中最小的哪个结点进行删除，该节点肯定符合上述三种状况的某一种情况，所以可以使用上述的方式进行删除。

在二叉排序树中，每个节点的值均高于其左子树上所有节点的值，小于其右子树上所有节点的值，对二叉排序树进行中序遍历得到一个有序序列。所以，二叉排序树是节点之间满足一定顺序关系的二叉树；

堆是一个完全二叉树，并且每个节点的值都小于或等于其左右孩子节点的值（这里的讨论以大根堆为例），所以，堆是节点之间满足一定顺序关系的完全二叉树。

具有n个节点的二叉排序树，其深度取决于给定集合的初始排列次序，最好情况下其深度为log n（表示以2为底的对数）二叉排序树 堆，最坏情况下其深度为n；

具有n个节点的堆，其深度即为堆所对应的完全二叉树的深度log n 。

在二叉排序树中，某节点的右孩子结点的值必定小于该节点的左孩子结点的值；

在堆中仍不一定，堆也是限定了某节点的值高于（或大于）其左右孩子结点的值，但没有限定左右孩子结点之间的大小关系。

在二叉排序树中，最小值节点是很左下结点，其左指针为空；最大值节点是很右下结点，其右指针为空。

在大根堆中，最小值节点位于某个叶子结点，而最大值节点是大根堆的堆顶（即根节点）。

二叉排序树是为了推动动态查找而设计的数据结构，它是面向查找操作的，在二叉排序树中查找一个结点的平均时间复杂度是O(log n)；

堆是为了推动排序而设计的一种数据结构，它不是面向查找操作的，因而在堆中查找一个结点需要进行递归，其平均时间复杂度是O(n)。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-139140-1.html