精华内容
下载资源
问答
  • 我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)。这四种树都具备下面几个优势: (1) 都是动态结构。在删除,插入操作的时候,都不需要彻底重建原始...

    http://www.iteye.com/topic/614070

    此少侠总结的特棒,直接收藏了。

    我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)。这四种树都具备下面几个优势:

    (1) 都是动态结构。在删除,插入操作的时候,都不需要彻底重建原始的索引树。最多就是执行一定量的旋转,变色操作来有限的改变树的形态。而这些操作所付出的代价都远远小于重建一棵树。这一优势在《查找结构专题(1):静态查找结构概论 》中讲到过。

    (2) 查找的时间复杂度大体维持在O(log(N))数量级上。可能有些结构在最差的情况下效率将会下降很快,比如BST。这个会在下面的对比中详细阐述。

    下面我们开始概括性描述这四种树,并相互比较一下优劣。

    1. 二叉查找树 (Binary Search Tree) 详细见《查找结构专题(2):二叉查找树 [BST] 》

    很显然,二叉查找树的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。

    BST 的操作代价分析:

    (1) 查找代价: 任何一个数据的查找过程都需要从根结点出发,沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。

    当树中每个结点左右子树高度大致相同时,树高为logN。则平均查找长度与logN成正比,查找的平均时间复杂度在O(logN)数量级上。

    当先后插入的关键字有序时,BST退化成单支树结构。此时树高n。平均查找长度为(n+1)/2,查找的平均时间复杂度在O(N)数量级上。

    (2) 插入代价: 新结点插入到树的叶子上,完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。

    (3) 删除代价: 当删除一个结点P,首先需要定位到这个结点P,这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在,则改变形态的代价仅为O(1)。如果被删除结点的左、右子树均存在,只需要将当P的左孩子的右孩子的右孩子的...的右叶子结点与P互换,在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过O(logN)。

    BST效率总结 查找最好时间复杂度O(logN),最坏时间复杂度O(N)。

    插入删除操作算法简单,时间复杂度与查找差不多

    2. 平衡二叉查找树 ( Balanced Binary Search Tree ) 详细见《查找结构专题(3):平衡二叉查找树 [AVL] 

    二叉查找树在最差情况下竟然和顺序查找效率相当,这是无法仍受的。事实也证明,当存储数据足够大的时候,树的结构对某些关键字的查找效率影响很大。当然,造成这种情况的主要原因就是BST不够平衡(左右子树高度差太大)。

    既然如此,那么我们就需要通过一定的算法,将不平衡树改变成平衡树。因此,AVL树就诞生了。

    AVL 的操作代价分析:

    (1) 查找代价: AVL是严格平衡的BST(平衡因子不超过1)。那么查找过程与BST一样,只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好,最坏情况都是O(logN)数量级的。

    (2) 插入代价: AVL必须要保证严格平衡(|bf|<=1),那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上,AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此,总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。

    (3) 删除代价:AVL删除结点的算法可以参见BST的删除结点,但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此,删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)

    AVL 效率总结 查找的时间复杂度维持在O(logN),不会出现最差情况

    AVL树在执行每个插入操作时最多需要1次旋转,其时间复杂度在O(logN)左右。

    AVL树在执行删除时代价稍大,执行每个删除操作的时间复杂度需要O(2logN)。

    3. 红黑树 (Red-Black Tree ) 详细见《查找结构专题(4):红黑树 [RBT] 》

    二叉平衡树的严格平衡策略以牺牲建立查找结构(插入,删除操作)的代价,换来了稳定的O(logN) 的查找时间复杂度。但是这样做是否值得呢?

    能不能找一种折中策略,即不牺牲太大的建立查找结构的代价,也能保证稳定高效的查找效率呢? 答案就是:红黑树。

    RBT 的操作代价分析:

    (1) 查找代价:由于红黑树的性质(最长路径长度不超过最短路径长度的2倍),可以说明红黑树虽然不像AVL一样是严格平衡的,但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比AVL要略逊色一点。

    (2) 插入代价:RBT插入结点时,需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转,这一点和AVL的插入操作一样。虽然变色操作需要O(logN),但是变色操作十分简单,代价很小。

    (3) 删除代价:RBT的删除操作代价要比AVL要好的多,删除一个结点最多只需要3次旋转操作。

    RBT 效率总结 查找 效率最好情况下时间复杂度为O(logN),但在最坏情况下比AVL要差一些,但也远远好于BST。

    插入和删除操作改变树的平衡性的概率要远远小于AVL(RBT不是高度平衡的)。因此需要的旋转操作的可能性要小,而且一旦需要旋转,插入一个结点最多只需要旋转2次,删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN),但是实际上,这种操作由于简单所需要的代价很小。

    4. B~树/B+树 (B-Tree ) 详细见《查找结构专题(5):B~树/B+树 》

    对于在内存中的查找结构而言,红黑树的效率已经非常好了(实际上很多实际应用还对RBT进行了优化)。但是如果是数据量非常大的查找呢?将这些数据全部放入内存组织成RBT结构显然是不实际的。实际上,像OS中的文件目录存储,数据库中的文件索引结构的存储.... 都不可能在内存中建立查找结构。必须在磁盘中建立好这个结构。那么在这个背景下,RBT还是一种好的选择吗?

    在磁盘中组织查找结构,从任何一个结点指向其他结点都有可能读取一次磁盘数据,再将数据写入内存进行比较。大家都知道,频繁的磁盘IO操作,效率是很低下的(机械运动比电子运动要慢不知道多少)。显而易见,所有的二叉树的查找结构在磁盘中都是低效的。因此,B树很好的解决了这一个问题。

    B-Tree的操作代价分析:

    (1) 查找代价: B-Tree作为一个平衡多路查找树(m-叉)。B树的查找分成两种:一种是从一个结点查找另一结点的地址的时候,需要定位磁盘地址(查找地址),查找代价极高。另一种是将结点中的有序关键字序列放入内存,进行优化查找(可以用折半),相比查找代价极低。而B树的高度很小,因此在这一背景下,B树比任何二叉结构查找树的效率都要高很多。而且B+树作为B树的变种,其查找效率更高。

    (2)插入代价: B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时,磁盘访问的次数为h(读取搜索路径上的节点)+2s(回写两个分裂出的新节点)+1(回写新的根节点或插入后没有导致分裂的节点)。因此,所需要的磁盘访问次数是h+2s+1,最多可达到3h+1。因此插入的代价是很大的。

    (3)删除代价:B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h=(找到包含被删除元素需要h次
    读访问)+(获取第2至h层的最相邻兄弟需要h-1次读访问)+(在第3至h层的合并需要h-2次写
    访问)+(对修改过的根节点和第2层的两个节点进行3次写访问)

    B-Tree效率总结: 由于考虑磁盘储存结构,B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。

    动态查找树结构的对比:

    (1) 平衡二叉树和红黑树 [AVL PK RBT]

    AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势,其应用上也有不同。

    结构对比: AVL的结构高度平衡,RBT的结构基本平衡。平衡度AVL > RBT.

    查找对比: AVL 查找时间复杂度最好,最坏情况都是O(logN)。

    RBT 查找时间复杂度最好为O(logN),最坏情况下比AVL略差。

    插入删除对比: 1. AVL的插入和删除结点很容易造成树结构的不平衡,而RBT的平衡度要求较低。因此在大量数据插入的情况下,RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。

    2. 如果需要平衡处理时,RBT比AVL多一种变色操作,而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。

    3. 当插入一个结点都引起了树的不平衡,AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后,AVL最多需要logN 次旋转操作,而RBT最多只需要3次。因此两者插入一个结点的代价差不多,但删除一个结点的代价RBT要低一些。

    4. AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。

    总体评价:大量数据实践证明,RBT的总体统计性能要好于平衡二叉树。

    (2) B~树和B+树 [ B~Tree PK B+Tree]

    B+树是B~树的一种变体,在磁盘查找结构中,B+树更适合文件系统的磁盘存储结构。

    结构对比: B~树是平衡多路查找树,所有结点中都包含了待查关键字的有效信息(比如文件磁盘指针)。每个结点若有n个关键字,则有n+1个指向其他结点的指针。

    B+树严格意义上说已经不是树,它的叶子结点之间也有指针链接。B+树的非终结点中并不含有关键字的信息,需要查找的关键字的全部信息都包含在叶子结点上。非终结点中只作为叶子结点关键字的索引而存在。

    查找对比:1. 在相同数量的待查数据下,B+树查找过程中需要调用的磁盘IO操作要少于普通B~树。由于B树所在的磁盘存储背景下,因此B+树的查找性能要好于B~树。

    2. B+树的查找效率更加稳定,因为所有叶子结点都处于同一层中,而且查找所有关键字都必须走完从根结点到叶子结点的全部历程。因此同一颗B+树中,任何关键字的查找比较次数都是一样的。而B树就不一定了,可能查找到某一个非终结点就结束了。

    插入删除对比: B+树与B~树在插入删除操作中的效率是差不多的。

    总体评价:在应用背景下,特别是文件结构存储中。B+树的应用要更多,其效率也要比B~树好。

    字符串查找结构

    这次专题所讲的BST、AVL、BRT、B~Tree等可以胜任对任何关键字数据进行查找。但对字符串的查找(字符串匹配)结构,有专门的结构和算法。详见:《KMP算法 》,《Trie Tree 》

    展开全文
  • 为什么直接采用红黑树 因为红黑树需要进行左旋,右旋操作, 而单链表不... 红黑树平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换.
    1. 为什么直接采用红黑树
      因为红黑树需要进行左旋,右旋操作, 而单链表不需要,
      主要考察链表和红黑树对比:
      1)如果元素小于8个,查询成本高,新增成本低
      2)如果元素大于8个,查询成本低,新增成本高

    2. HashMap在jdk1.8之后引入了红黑树的概念,为什么采用6和8进行红黑树和链表转化

      表示若桶中链表元素超过8时,会自动转化成红黑树若桶中元素小于等于6时,树结构还原成链表形式
      1)原因:
        红黑树的平均查找长度是log(n),长度为8,查找长度为log(8)=3链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。

      2)选择6和8的原因是:
        中间有个差值7可以防止链表和树之间频繁的转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。

    展开全文
  •  红黑树平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化...

    HashMap在jdk1.8之后引入了红黑树的概念,表示若桶中链表元素超过8时,会自动转化成红黑树;若桶中元素小于等于6时,树结构还原成链表形式。

    原因:

      红黑树的平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。

    还有选择6和8的原因是:

      中间有个差值7可以防止链表和树之间频繁的转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。

    HashMap计算添加元素的位置时,使用的位运算,这是特别高效的运算;另外,HashMap的初始容量是2的n次幂,扩容也是2倍的形式进行扩容,是因为容量是2的n次幂,可以使得添加的元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!

    展开全文
  • 平衡查找树之红黑树

    2018-08-23 15:33:38
    红黑树的主要是想对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来...

    红黑树(Red-Black Tree)

    定义

    红黑树的主要是想对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2-nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。

    Red black tree

    根据以上描述,红黑树定义如下:

    红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

    • 红色节点向左倾斜
    • 一个节点不可能有两个红色链接
    • 整个书完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

    下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

    1-1 correspondence between 2-3 and LLRB

    表示

    我们可以在二叉查找树的每一个节点上增加一个新的表示颜色的标记。该标记指示该节点指向其父节点的颜色。

    private const bool RED = true;
    private const bool BLACK = false;
    
    private Node root;
    
    class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }
        public TKey Key { get; set; }
        public TValue Value { get; set; }
        public int Number { get; set; }
        public bool Color { get; set; }
    
        public Node(TKey key, TValue value,int number, bool color)
        {
            this.Key = key;
            this.Value = value;
            this.Number = number;
            this.Color = color;
        }
    }
    
    private bool IsRed(Node node)
    {
        if (node == null) return false;
        return node.Color == RED;
    }

     Red black tree representation

    实现

    查找

    红黑树是一种特殊的二叉查找树,他的查找方法也和二叉查找树一样,不需要做太多更改。

    但是由于红黑树比一般的二叉查找树具有更好的平衡,所以查找起来更快。

    //查找获取指定的值
    public override TValue Get(TKey key)
    {
        return GetValue(root, key);
    }
    
    private TValue GetValue(Node node, TKey key)
    {
        if (node == null) return default(TValue);
        int cmp = key.CompareTo(node.Key);
        if (cmp == 0) return node.Value;
        else if (cmp > 0) return GetValue(node.Right, key);
        else return GetValue(node.Left, key);
    }

    平衡化

    在介绍插入之前,我们先介绍如何让红黑树保持平衡,因为一般的,我们插入完成之后,需要对树进行平衡化操作以使其满足平衡化。

    旋转

    旋转又分为左旋右旋。通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。对比操作前后,可以看出,该操作实际上是将红线链接的两个节点中的一个较大的节点移动到根节点上。

    左旋操作如下图:

    before left rotation after left rotation

    //左旋转
    private Node RotateLeft(Node h)
    {
        Node x = h.Right;
        //将x的左节点复制给h右节点
        h.Right = x.Left;
        //将h复制给x右节点
        x.Left = h;
        x.Color = h.Color;
        h.Color = RED;
        return x;
    }

    左旋的动画效果如下:

    rotate left in red black tree

    右旋是左旋的逆操作,过程如下:

    before right rotation after right rotation

    代码如下:

    //右旋转
    private Node RotateRight(Node h)
    {
        Node x = h.Left;
        h.Left = x.Right;
        x.Right = h;
    
        x.Color = h.Color;
        h.Color = RED;
        return x;
    }

    右旋的动画效果如下:

    rotate right the red black tree

    颜色反转

    当出现一个临时的4-node的时候,即一个节点的两个子节点均为红色,如下图:

    before flip colors after flip colors

    这其实是个A,E,S 4-node连接,我们需要将E提升至父节点,操作方法很简单,就是把E对子节点的连线设置为黑色,自己的颜色设置为红色。

    有了以上基本操作方法之后,我们现在对应之前对2-3树的平衡操作来对红黑树进行平衡操作,这两者是可以一一对应的,如下图:

    RB tree 1-1 correspondence with 2-3 tree

    现在来讨论各种情况:

    Case 1 往一个2-node节点底部插入新的节点

    先热身一下,首先我们看对于只有一个节点的红黑树,插入一个新的节点的操作:

    Insert into a tree with only 1 node

    这种情况很简单,只需要:

    • 标准的二叉查找树遍历即可。新插入的节点标记为红色
    • 如果新插入的节点在父节点的右子节点,则需要进行左旋操作

    Case 2往一个3-node节点底部插入新的节点

    先热身一下,假设我们往一个只有两个节点的树中插入元素,如下图,根据待插入元素与已有元素的大小,又可以分为如下三种情况:

    Insert into a tree with only 2 nodes

    • 如果带插入的节点比现有的两个节点都大,这种情况最简单。我们只需要将新插入的节点连接到右边子树上即可,然后将中间的元素提升至根节点。这样根节点的左右子树都是红色的节点了,我们只需要调研FlipColor方法即可。其他情况经过反转操作后都会和这一样。
    • 如果插入的节点比最小的元素要小,那么将新节点添加到最左侧,这样就有两个连接红色的节点了,这是对中间节点进行右旋操作,使中间结点成为根节点。这是就转换到了第一种情况,这时候只需要再进行一次FlipColor操作即可。
    • 如果插入的节点的值位于两个节点之间,那么将新节点插入到左侧节点的右子节点。因为该节点的右子节点是红色的,所以需要进行左旋操作。操作完之后就变成第二种情况了,再进行一次右旋,然后再调用FlipColor操作即可完成平衡操作。

    有了以上基础,我们现在来总结一下往一个3-node节点底部插入新的节点的操作步骤,下面是一个典型的操作过程图:

    Insert into 3-node at the bottom

    可以看出,操作步骤如下:

    1. 执行标准的二叉查找树插入操作,新插入的节点元素用红色标识。
    2. 如果需要对4-node节点进行旋转操作
    3. 如果需要,调用FlipColor方法将红色节点提升
    4. 如果需要,左旋操作使红色节点左倾。
    5. 在有些情况下,需要递归调用Case1 Case2,来进行递归操作。如下:

    Insert into 3-node at the bottom case 2

    代码实现

    经过上面的平衡化讨论,现在就来实现插入操作,一般地插入操作就是先执行标准的二叉查找树插入,然后再进行平衡化。对照2-3树,我们可以通过前面讨论的,左旋,右旋,FlipColor这三种操作来完成平衡化。

    Passing a red link up a red-black BST

    具体操作方式如下:

    • 如果节点的右子节点为红色,且左子节点位黑色,则进行左旋操作
    • 如果节点的左子节点为红色,并且左子节点的左子节点也为红色,则进行右旋操作
    • 如果节点的左右子节点均为红色,则执行FlipColor操作,提升中间结点。

    根据这一逻辑,我们就可以实现插入的Put方法了。

    public override void Put(TKey key, TValue value)
    {
        root = Put(root, key, value);
        root.Color = BLACK;
    }
    
    private Node Put(Node h, TKey key, TValue value)
    {
        if (h == null) return new Node(key, value, 1, RED);
        int cmp = key.CompareTo(h.Key);
        if (cmp < 0) h.Left = Put(h.Left, key, value);
        else if (cmp > 0) h.Right = Put(h.Right, key, value);
        else h.Value = value;
    
        //平衡化操作
        if (IsRed(h.Right) && !IsRed(h.Left)) h = RotateLeft(h);
        if (IsRed(h.Right) && IsRed(h.Left.Left)) h = RotateRight(h);
        if (IsRed(h.Left) && IsRed(h.Right)) h = FlipColor(h);
    
        h.Number = Size(h.Left) + Size(h.Right) + 1;
        return h;
    }
    
    private int Size(Node node)
    {
        if (node == null) return 0;
        return node.Number;
    }

    分析

    对红黑树的分析其实就是对2-3查找树的分析,红黑树能够保证符号表的所有操作即使在最坏的情况下都能保证对数的时间复杂度,也就是树的高度。

    在分析之前,为了更加直观,下面是以升序,降序和随机构建一颗红黑树的动画:

    • 以升序插入构建红黑树:

    insert in ascending order rb tree

    • 以降序插入构建红黑树:

    insert in descend order rb tree

    • 随机插入构建红黑树

    insert in random order rb tree

    从上面三张动画效果中,可以很直观的看出,红黑树在各种情况下都能维护良好的平衡性,从而能够保证最差情况下的查找,插入效率。

    下面来详细分析下红黑树的效率:

    1. 在最坏的情况下,红黑树的高度不超过2lgN

    最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2

    下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

    a typic red black tree

    2. 红黑树的平均高度大约为lgN

    下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,他能保证最坏情况下仍然具有对数的时间复杂度。

    下图是红黑树各种操作的时间复杂度。

    analysis of red black tree

    应用

    红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:

    • Java中的java.util.TreeMap,java.util.TreeSet
    • C++ STL中的:map,multimap,multiset
    • .NET中的:SortedDictionary,SortedSet 等

    下面以.NET中为例,通过Reflector工具,我们可以看到SortedDictionary的Add方法如下:

    public void Add(T item)
    {
        if (this.root == null)
        {
            this.root = new Node<T>(item, false);
            this.count = 1;
        }
        else
        {
            Node<T> root = this.root;
            Node<T> node = null;
            Node<T> grandParent = null;
            Node<T> greatGrandParent = null;
            int num = 0;
            while (root != null)
            {
                num = this.comparer.Compare(item, root.Item);
                if (num == 0)
                {
                    this.root.IsRed = false;
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                }
                if (TreeSet<T>.Is4Node(root))
                {
                    TreeSet<T>.Split4Node(root);
                    if (TreeSet<T>.IsRed(node))
                    {
                        this.InsertionBalance(root, ref node, grandParent, greatGrandParent);
                    }
                }
                greatGrandParent = grandParent;
                grandParent = node;
                node = root;
                root = (num < 0) ? root.Left : root.Right;
            }
            Node<T> current = new Node<T>(item);
            if (num > 0)
            {
                node.Right = current;
            }
            else
            {
                node.Left = current;
            }
            if (node.IsRed)
            {
                this.InsertionBalance(current, ref node, grandParent, greatGrandParent);
            }
            this.root.IsRed = false;
            this.count++;
            this.version++;
        }
    }

    可以看到,内部实现也是一个红黑树,其操作方法和本文将的大同小异,感兴趣的话,您可以使用Reflector工具跟进去查看源代码。

    总结

    前文讲解了自平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。

    希望本文对您了解红黑树有所帮助,下文将介绍在文件系统以及数据库系统中应用非常广泛的另外一种平衡树结构:B树。

    展开全文
  • 因为红黑树平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果继续使用链表,平均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成...
  • 根据百度百科给出的定义,它们之间的关系可以用下图表示,平衡二叉树(平衡二叉查找树,AVL)和红黑树都是二叉查找树的一种,区别就是平衡二叉树严格平衡,红黑树是弱平衡。 而AVL树由于实现比较复杂,而且插入和...
  • 参考:自平衡二叉查找树,红黑树, 算法:理解红黑树 (英文pdf:红黑树) 目录 自平衡二叉树介绍 avl树 2-3树 LLRBT(Left-leaning red-black tree左倾红黑树 (代码见git) 2-3-4树和红黑树 avl和红黑树...
  • HashMap在jdk1.8之后引入了红黑树的概念,表示若桶中链表元素超过8时,会自动转化成红黑树;若桶中元素小于等于6时,树... 红黑树平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/...
  • 总结这篇的原因是今天实验室的好几个同学都被问到红黑树的相关问题 于是慌的一批Orz 首先复习一些概念 查找算法分类:  1)静态查找和动态查找;  静态或者动态都是针对查找...平均查找长度(Average Search Leng...
  • 数据结构 平衡查找红黑树(Red-Black Tree) 二叉查找树(BinarySearch Tree,也叫二叉搜索树,或称二叉排序树Binary Sort Tree)或者是一棵空树,或者是具有下列性质的二叉树: 1、若任意节点的左子树不空,则...
  • 1、二叉查找(Binary Search Tree) 很显然,二叉查找的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要...则平均查找长度与logN成正比,查找的平均时间复杂度在O(logN)数量级上。 ...
  • 前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为...红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-node
  • 红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来...
  • 为什么HashMap桶长度超过8才会转换成红黑树

    万次阅读 热门讨论 2019-04-20 22:17:39
    为什么HashMap桶(链表)的长度超过8会转换成红黑树
  • 平衡之查找红黑树

    2017-05-25 01:18:03
    红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来...
  • 红黑树

    千次阅读 2018-01-19 19:33:06
     提到红黑树,我们首先得知道二叉查找树(Binary Search Tree),也称二叉搜索树,有序二叉树,排序二叉树,是指一颗空树,或者具有以下性质的二叉树:  (1)若任意节点的左子树不空,则左子树上所有节点的值均...
  • 算法-查找红黑树

    千次阅读 2018-06-16 11:37:56
    查找 符号表 最主要的目的是将一个键合一个值联系起来。用例能够将一个键值对插入符号表并希望在之后能够从符号表的所有键值对中按照键直接找到对应的值,即以键值对为单元的数据结构。 无序链表顺序查找 ...
  • 因为红黑树平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果继续使用链表,平均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成...
  • 原文链接https://blog.csdn.net/yang_yulei/article/details/26066409我们会用三种经典的数据类型来实现高效的符号表:二叉查找数、红黑树、散列表。二分查找我们使用有序数组存储键,经典的二分查找能够根据数组的...
  • 二叉查找树又称二叉搜索,二叉排序,特点如下: 1. 左子树上所有结点值均小于根结点 2. 右子上所有结点值均大于根结点 3. 结点的左右子树本身又是一颗二叉查找树 4. 二叉查找树中序遍...
  • 前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持的平衡状态,最坏情况下即所有的子节点都是2-node,的高度为lgN,从而保证了最坏情况下的时间复杂度。但是2-3实现起来比较复杂,...
  • 聊聊红黑树

    2018-02-27 10:21:25
    java8库中的HashMap中变引入了红黑树:当散列桶中的链表长度大于等于8,就是用红黑树构建该链表。 红黑树的主要目的是实现高效的查找,所以需要从查找算法说起。我们最熟悉的快速查找算法便是二分查找,算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,140
精华内容 3,256
热门标签
关键字:

红黑树的平均查找长度