Title Date Modified Category
searching 2019-07-09 12:00 2019-07-09 12:00 algorithm

1.1. 二叉排序树

有没有一种既可以使得插入和删除效率不错,又可以比较高效率的实现查找的算法呢?

也就是说,若我们现在需要对集合{62,88,58,47,35,73,51,99,37,93}做查找,在我们打算创建此集合时就考虑用二叉树结构,而且是排好序的二叉树来创建。

这样我们就得到了一棵二叉树,并且当我们对它进行中序遍历时,就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}, 所以我们通常称它为二叉排序树。

二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有节点的值均小于它的根结构的值
  • 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  • 它的左,右子树也分别为二叉排序树

1.1.1. 二叉排序树查找操作

1.1.2. 二叉排序树插入操作

1.1.3. 二叉排序树删除操作

1.1.4. 二叉排序树总结

总之,二叉排序树是以链接的方式存储,保持了链接存储结构在执行插入或删除操作时不用移动元素的优点,只要找到合适的插入和删除位置后,仅需修改链接指针即可。插入删除的时间性能比较好。

而对于二叉排序树的查找,走的就是从根节点到要查找的节点的路径,其比较次数等于给定值的节点在二叉排序树中的层数。

极端情况,最少为1次,即根节点就是要找的节点,最多也不会超过树的深度。

也就是说,二叉排序树的查找性能取决于二叉排序树的形状。

可问题就在于,二叉排序树的形状是不确定的。

也就是说,我们希望二叉排序树是比较平衡的,即其深度与完全二叉树相同,均为[log2n]+1,那么查找的时间复杂度也就为O(logn),近似于折半查找,事实上,图8-6-18的左图也不够平衡,明显的左重右轻。

不平衡的最坏情况就是像图8-6-18右图的斜树,查找时间复杂度为O(n), 这等同于顺序查找。

因此,如果我们希望对一个集合按二叉排序树查找,最好是把它构建成一颗平衡的二叉排序树。

这样我们就引申出另一个问题,如何让二叉排序树平衡的问题。

1.2. 平衡二叉树(AVL树)

1.3. 多路查找树(B树)

results matching ""

    No results matching ""