伸展树

作者: NoFacePeace | 来源:发表于2017-10-25 21:07 被阅读0次

概念

伸展树是一种二叉查找树,它能在O(logn)内完成插入、查找和删除操作。
伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。

优点

  • 可靠的性能-它的平均效率不输于其他平衡树
  • 存储所需的内存少-伸展树无需记录额外的什么值来维护树的信息,相对于其他平衡树,内存占用要小

缺点

伸展树最明显的缺点是它有可能会变成一条链表。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的O(logn)

基本操作

伸展树主要有三种旋转操作,分别为单旋转,一字形旋转和之字形旋转。为了便于解释,我们假设当前被访问节点为X,X的父亲节点为Y(如果X的父亲节点存在),X的祖父节点为Z(如果X的祖父节点存在)。

  • 单旋转
    节点X的父节点Y是根节点。这时,如果X是Y的左孩子,我们进行一次右旋操作;如果X是Y的右孩子,则我们进行一次左旋操作。经过旋转,X成为二叉查找树T的根节点,调整结束。
单旋转
  • 一字型旋转
    节点X的父节点Y不是根节点,Y的父节点为Z,且X与Y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时,我们进行一次左左旋转操作或者右右旋转操作。
一字型旋转
  • 之字形旋转
    节点X的父节点Y不是根节点,Y的父节点为Z,X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时,我们进行一次左右旋转操作或者右左旋转操作。
之字形旋转

相关文章

  • 伸展树

    概念 伸展树是一种二叉查找树,它能在O(logn)内完成插入、查找和删除操作。伸展树是一种自调整形式的二叉查找树,...

  • 8.1 伸展树

    局部性(Locality):刚被访问过的数据,极有可能很快再次被访问逐层伸展:节点v一旦被访问,随即转移至根自上而...

  • 伸展树的实现

    伸展树的引入: 我们知道AVL树为了保持严格的平衡,所以在数据插入上会呈现过多的旋转,影响了插入和删除的性能。从访...

  • 数据结构:伸展树

    伸展树简介 伸展树是二叉查找树,满足左子树的key<=根节点的<=右子树的key的特点。不保证树是平衡的,但各种操...

  • 5.AVL树和伸展树

    0.背景 二叉搜索树在删除操作会选区右子树的最小元素节点代替删除的节点,会使得左子树比右子树深度深,虽然可以通过随...

  • 2017-05-21

    今日体式练习,山式,树式,三角伸展式,侧角伸展式,站二,站一,半月,加强侧伸展,双角式,门栓。

  • 【译】Swift算法俱乐部-伸展树

    本文是对 Swift Algorithm Club 翻译的一篇文章。Swift Algorithm Club是 r...

  • 爱的礼赞(诗一首)

    爱的礼赞 一送给Z&M 树 傲然伸展 花 嫣然绽放 ...

  • 雨水催发 一树树嫩绿清寒 别处枯枝正茂盛 似欲伸展向长空 终不得 这也是春天

  • 赞树(十一)伸展诗三首

    赞树(十一)伸展诗三首 文/付朝兰 一 展开双臂欢迎你 根基如布宽松地 仿佛围栏有依靠 世界景观也称奇 ...

网友评论

      本文标题:伸展树

      本文链接:https://www.haomeiwen.com/subject/joscpxtx.html