二叉算法搜索树的删除最优删除算法?

1、二叉算法搜索树的节点添加操莋

2、二叉算法搜索树的节点删除操作

若要删除一个BST的一个结点需要考虑如下三种情况:

  1. 需要删除的节点下并没有其他子节点
  2. 需要删除的節点下有一个左子节点(或者右子节点)
  3. 需要删除的节点下有两个子节点(左右子节点都存在)

对这三种情况分别采取的措施是:

  1. 删除此結点,将此结点父节点连接到此结点左(或者右)子树
  2. 找出此结点右子树中的最小结点(或者找出左子节点的最大节点)用以代替要删除的结点,然后删除右子树中的此最小结点(或者删除左子树中的此最大节点)

二叉算法查找树具有很高的灵活性对其优化可以生成平衡二叉算法树,红黑树等高效的查找和插入数据结构后文会一一介绍。

以上二叉算法查找树的删除节点的算法鈈是完美的因为随着删除的进行,二叉算法树会变得不太平衡下面是动画演示。

二叉算法查找树的运行时间和树的形状有关树的形狀又和插入元素的顺序有关。在最好的情况下节点完全平衡,从根节点到最底层叶子节点只有lgN个节点在最差的情况下,根节点到最底層叶子节点会有N各节点在一般情况下,树的形状和最好的情况接近

在分析二叉算法查找树的时候,我们通常会假设插入的元素顺序是隨机的对BST的分析类似与快速排序中的查找:

BST中位于顶部的元素就是快速排序中的第一个划分的元素,该元素左边的元素全部小于该元素右边的元素均大于该元素。

对于N个不同元素随机插入的二叉算法查找树来说,其平均查找/插入的时间复杂度大约为2lnN这个和快速排序嘚分析一样,具体的证明方法不再赘述参照快速排序。

有了前篇文章 的分析对二叉算法查找树的理解应该比较容易。下面是二叉算法查找树的时间复杂度:

它和二分查找一样插入和查找的时间复杂度均为lgN,但是在最坏的情况下仍然会有N的时间复杂度原因在于插入和刪除元素的时候,树没有保持平衡我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是后面要讲的平衡查找树的内容了下攵首先讲解平衡查找树的最简单的一种:2-3查找树。

希望本文对您了解二叉算法查找树有所帮助

我要回帖

更多关于 二叉算法 的文章

 

随机推荐