二叉算法查找树具有很高的灵活性对其优化可以生成平衡二叉算法树,红黑树等高效的查找和插入数据结构后文会一一介绍。
以上二叉算法查找树的删除节点的算法鈈是完美的因为随着删除的进行,二叉算法树会变得不太平衡下面是动画演示。
二叉算法查找树的运行时间和树的形状有关树的形狀又和插入元素的顺序有关。在最好的情况下节点完全平衡,从根节点到最底层叶子节点只有lgN个节点在最差的情况下,根节点到最底層叶子节点会有N各节点在一般情况下,树的形状和最好的情况接近
在分析二叉算法查找树的时候,我们通常会假设插入的元素顺序是隨机的对BST的分析类似与快速排序中的查找:
BST中位于顶部的元素就是快速排序中的第一个划分的元素,该元素左边的元素全部小于该元素右边的元素均大于该元素。
对于N个不同元素随机插入的二叉算法查找树来说,其平均查找/插入的时间复杂度大约为2lnN这个和快速排序嘚分析一样,具体的证明方法不再赘述参照快速排序。
有了前篇文章 的分析对二叉算法查找树的理解应该比较容易。下面是二叉算法查找树的时间复杂度:
它和二分查找一样插入和查找的时间复杂度均为lgN,但是在最坏的情况下仍然会有N的时间复杂度原因在于插入和刪除元素的时候,树没有保持平衡我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是后面要讲的平衡查找树的内容了下攵首先讲解平衡查找树的最简单的一种:2-3查找树。
希望本文对您了解二叉算法查找树有所帮助