【动画可视化讲解】二叉排序树（二叉搜索树、二叉查找树） 代码讲解，数据结构与算法
Hello 大家好
在这一小节中，我们将一起学习二叉排序树
首先我们会学习为什么要使用二叉排序树，以及它对比数组和链表的优势是什么
然后我们会分析它的时间复杂度
后面我们还会学习查找、插入以及删除的代码实现
在前面的课程中，我们已经学习了数组的数据结构
数组非常简单，但是他的并不高
这里我们有一个数组，如果我们要查找元素80
我们必须从第一个节点开始，然后遍历每个元素
并比较key值来判断是否查找到
其时间复杂度为O(N)
插入和删除操作也同样
如果我们需要删除80，我们需要遍历整个数组，先找到80，然后再删除它
因此，删除的时间复杂度也是O(N)
而且，数组是静态的，一旦定义后 数组能存储多少个元素就是固定的，无法动态的按需增长或收缩
所以数组的效率并不高
对于数组存储空间大小不能动态更改的问题，我们可以使用链表来解决
它可以根据需要动态新增或者减少链表的元素
如果我们需要访问50，则还是需要遍历整个链表
因此，链表的查找时间复杂度仍然为O(N)
不过上面这些问题，均可以通过二叉排序树来解决
在二叉排序树中，每个节点都有自己的排序顺序
左孩子节点的值始终小于其父节点的值，所以B一定小于A
而父节点的值又始终小于右孩子的值，所以A一定小于C
因此二叉树中任意一个子树的顺序都是 左孩子<父节点<右孩子
现在让我们用这些元素构建一个二叉排序树
首先插入100，目前二叉排序树为空，所以它将成为根节点
现在插入50
正如我们刚刚讨论的，所有小于100的元素都将存放在它的左子树中
所有大于100的元素都存放在它的右子树中
50小于100，所以它将成为100的左孩子
接下来是200，因为200大于100，它将成为100的右孩子
接下来是10，10小于100，所以应该放在左子树中，我们这里已经有50了，只能继续向下查找它的位置
将10和50做对比，要小于50，所以将10放在50的左孩子节点中
接下来是60，60小于100，它应该在左子树中
左子树有50，而60大于50，所以60成为50的右孩子
接下来是150，150大于100
所以它应该在100的右子树中
这里已经有200了，而150小于200，所以150成为200的左孩子
接下来是300，300大于100和200，所以300将被放置为右孩子200的子节点
接下来是500，500大于100，大于200，大于300，所以它成为300的右子节点
这就是我们二叉排序树的建立过程
可以看到最小值10，在树中的最左边节点
最大值500是最右边的节点
现在我们来讨论如何查找一个元素
例如，让我们查找元素60
首先将60与根节点的数据进行比较
60小于100，因此60如果存在的话只会在100的左子树中
因此，我们忽略右子树
现在将60与左子树的50进行比较，60要大于50
所以60只会出现在50的右子树中，我们可以忽略50的左子树
到这里我们就查找到了60
现在我们从新查找150
150大于100，所以忽略左子树，直接和右子树的200进行比较
150小于200，所以它只能出现在200的左子树中
与200左子树进行比较，结果相等，因此找到了key值
可以发现，当我们搜索时每次都会忽略掉一半的元素
查找的时间复杂度一下就降低了很多
假设树的高度是平衡的，也就是左右子树的规模近似时
如果我们有N个节点，那么第一次查找后总的可搜索范围将会被缩减为n/2
因为我们知道了它在左边或者右边，所以另外一半就被丢弃了
然后是N/4，最后是N/8
最后可以归结为 即n/2^0，n/2^1，n/2^2, n/2^3...
即n/2^k=1, 其中k=1,2,3...，k可以看作是第几层，所以在一个N个节点的排序树中，最多只需要k次就可以找到任意节点，需要注意的是当树的高度是平衡时
我们简化下就可以得到 n = 2^k
现在我们对两边同时取以2为底的对数
Log2以2为底，值为1 将k移出来，也就是k乘1
最后得到k=log n，以2为底
所以如果我们需要在二叉排序树中查找一个元素，平均时间复杂度为log n
这里我们将的是比较理想的情况下
现在我们来看下在极端情况下会是怎么样的
如果我们构建数字顺序本身就是有序的情况下，看看会怎么样？
首先我们还是按照二叉排序树的创建方法，先插入10
然后插入20，20比10大，插入在10的右子树中
插入30，30比10大，也比20大，插入在20的右子树中
按照该顺序继续插入剩下的元素
可以发现在极端情况下则变成了一个和链表差不多的形状
如果我们要查找60，则需要从头到尾都访问一遍，则最坏的时间复杂度为O(N)
立即观看
0