b2科目四模拟试题多少题驾考考爆了怎么补救
b2科目四模拟试题多少题 驾考考爆了怎么补救

二叉排序树_二叉排序树的创建过程_二叉树的遍历算法

电脑杂谈  发布时间:2016-11-26 10:03:21  来源:网络整理

二叉排序树_二叉排序树的创建过程_二叉树的遍历算法

二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree)。

L树:在计算机科学中,L树是最先发明的自平衡二叉查找树。在L树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。L树在节点增删后不再满足L树条件,则需要“旋转”以重新构造自身。

红黑树:RB树。每个节点都带有颜色属性的二叉查找树。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

节点是红色或黑色。

根节点是黑色。

每个叶节点(NIL节点,空节点)是黑色的。

每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

二叉排序树的创建过程_二叉排序树_二叉树的遍历算法

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图就是一棵红黑树:

L是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;

红黑是弱平衡的,用非严格的平衡来换取增删节点时候旋转次数的降低;

所以简单说,搜索的次数远远大于插入和删除,那么选择L树,如果搜索,插入删除次数几乎差不多,应该选择RB树。二叉排序树

可以看到,这三者查找的时间复杂度O(log2N)与树的深度相关,那么降低树的深度自然会提高查找效率 。

但是在数据存储中,使用二叉查找树实现索引查询,元素数量是非常大的,这样就导致二叉查找树结构树的深度过大,进而造成磁盘I/O读写过于频繁,导致查询效率低下,那么如何减少树的深度,一个基本的想法就是:采用多叉树结构。这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发,自然就想到平衡多路查找树结构。

B-tree:一种平衡多路搜索树(并不是二叉的)。B-tree树即B树, B即Balanced ,平衡的意思。

B+-tree:B+的搜索与B-树也基本相同,区别是B+树所有关键字都在叶子结点出现,因此只有达到叶子结点才命中(B-树可以在非叶子结点命中)。B+树叶子节点链表中的关键字是有序的,且所有叶子结点都有一个链指针指向下一个叶子节点,这个特性使得B+树对范围查找的效率比B树高的多,比如对已经建立索引的记录,查找10<=id<=20,那么只要通过根节点搜索到id=10的叶节点,之后只要根据叶节点的链表找到第一个大于20的就行了,比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。二叉排序树

B*-tree:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3。

Huffman tree:又称最优树。对应的有哈夫曼编码,其主要应用在数据压缩,加密解密等场合。

上述只是常见但很小一部分树,最后附图一幅:


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

    相关阅读
      发表评论  请自觉遵守互联网相关的政策法规,严禁发布、暴力、反动的言论

      • 曾国藩
        曾国藩

        #吴亦凡1106生日快乐##吴亦凡##吴亦凡BadGirl#吴亦凡生日快乐

      热点图片
      拼命载入中...