伸展树

✍ dations ◷ 2025-06-07 22:10:57 #树结构,数据结构,计算机科学中未解决的问题

伸展树(英语:Splay Tree)是一种能够自我平衡的二叉查找树,它能在均摊 O ( log n ) {\displaystyle O(\log n)} 被访问过后,伸展操作会将移动到根节点。为了进行伸展操作,我们会进行一系列的旋转,每次旋转会使离根节点更近。通过每次访问节点后的伸展操作,最近访问的节点都会离根节点更近,且伸展树也会大致平衡,这样我们就可以得到期望均摊时间复杂度的下界——均摊 O ( log n ) {\displaystyle O(\log n)} 的儿子为是很重要的。如果为空,那么显然就是根节点了。

共有三种旋转操作,每种都有左旋(Zig)和右旋(Zag)两种情况。为了简单起见,对每种旋转操作只展示一种情况。这些旋转操作是:

Zig:当为根节点时进行。Zig通常只在伸展操作的最后一步进行。

Zig-zig和Zag-zag:当不为根节点且和都为左儿子或都为右儿子时进行。下图为和都为左儿子时的情况(即Zig-zig),需先将右旋到的位置,再将右旋到的位置。

Zig-zag和Zag-zig:当不为根节点且为左儿子而为右儿子时进行,反之亦然。下图为前述情况(即Zig-zag),需先将左旋到到的位置,再将右旋到的位置。

给出两棵树S和T,且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树:

给出一棵树和一个元素,返回两棵树:一棵中所有的元素均小于等于x,另一棵中所有的元素大于。下面的步骤可以完成这个操作:

插入操作是一个比较复杂的过程,具体步骤如下:我们假定要插入的值为k。

如果当前树为空,则直接插入根。

如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行splay操作。

否则按照二叉查找树的性质向下找,找到空节点就插入即可,当然在最后还要进行一次splay操作。

如同一般的查找树的查找方式。

以下是伸展树的C++实现(用指针实现)

#include <functional>#ifndef SPLAY_TREE#define SPLAY_TREEtemplate< typename T, typename Comp = std::less< T > >class splay_tree {private:  Comp comp;  unsigned long p_size;    struct node {    node *left, *right;    node *parent;    T key;    node( const T& init = T( ) ) : left( 0 ), right( 0 ), parent( 0 ), key( init ) { }  } *root;    void left_rotate( node *x ) {    node *y = x->right;    x->right = y->left;    if( y->left ) y->left->parent = x;    y->parent = x->parent;    if( x->parent ) {        if( x == x->parent->left ) x->parent->left = y;        else x->parent->right = y;    }    y->left = x;    x->parent = y;  }    void right_rotate( node *x ) {    node *y = x->left;    x->left = y->right;    if( y->right ) y->right->parent = x;    y->parent = x->parent;    if( x->parent ) {        if( x == x->parent->left ) x->parent->left = y;        else x->parent->right = y;    }    y->right = x;    x->parent = y;  }    void splay( node *x ) {    while( x->parent ) {      if( !x->parent->parent ) {        if( x->parent->left == x ) right_rotate( x->parent );        else left_rotate( x->parent );      } else if( x->parent->left == x && x->parent->parent->left == x->parent ) {        right_rotate( x->parent->parent );        right_rotate( x->parent );      } else if( x->parent->right == x && x->parent->parent->right == x->parent ) {        left_rotate( x->parent->parent );        left_rotate( x->parent );      } else if( x->parent->left == x && x->parent->parent->right == x->parent ) {        right_rotate( x->parent );        left_rotate( x->parent );      } else {        left_rotate( x->parent );        right_rotate( x->parent );      }    }  }    void replace( node *u, node *v ) {    if( !u->parent ) root = v;    else if( u == u->parent->left ) u->parent->left = v;    else u->parent->right = v;    if( v ) v->parent = u->parent;  }    node* subtree_minimum( node *u ) {    while( u->left ) u = u->left;    return u;  }    node* subtree_maximum( node *u ) {    while( u->right ) u = u->right;    return u;  }public:  splay_tree( ) : root( 0 ), p_size( 0 ) { }    void insert( const T &key ) {    node *z = root;    node *p = 0;        while( z ) {      p = z;      if( comp( z->key, key ) ) z = z->right;      else z = z->left;    }        z = new node( key );    z->parent = p;        if( !p ) root = z;    else if( comp( p->key, z->key ) ) p->right = z;    else p->left = z;        splay( z );    p_size++;  }    node* find( const T &key ) {    node *z = root;    while( z ) {      if( comp( z->key, key ) ) z = z->right;      else if( comp( key, z->key ) ) z = z->left;      else return z;    }    return 0;  }          void erase( const T &key ) {    node *z = find( key );    if( !z ) return;        splay( z );        if( !z->left ) replace( z, z->right );    else if( !z->right ) replace( z, z->left );    else {      node *y = subtree_minimum( z->right );      if( y->parent != z ) {        replace( y, y->right );        y->right = z->right;        y->right->parent = y;      }      replace( z, y );      y->left = z->left;      y->left->parent = y;    }        p_size--;  }    const T& minimum( ) { return subtree_minimum( root )->key; }  const T& maximum( ) { return subtree_maximum( root )->key; }    bool empty( ) const { return root == 0; }  unsigned long size( ) const { return p_size; }};#endif // SPLAY_TREE

时间效率分析

m次伸展操作的均摊时间效率 T a m o r t i z e d ( m ) = O ( m log n ) {\displaystyle T_{\mathrm {amortized} }(m)=O(m\log n)}

实际时间效率 T a c t u a l ( m ) = O ( m log n + n log n ) {\displaystyle T_{\mathrm {actual} }(m)=O(m\log n+n\log n)}

相关

  • 风湿病学人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学风湿病学或称风湿病专科(英语:Rheumatol
  • 血凝素血球凝集素(hemagglutinin)(C53H67N9O17) (TYR-PRO-TYR-ASP-VAL-PRO-ASP-TYR-ALA),是指可使红血球凝集的抗体或其他物质。在流感病毒、痳疹病毒(以及许多其他细菌和病毒)表面等均
  • 自然疗法自然医学(英语:Naturopathy,或Naturopathic Medicine),又称自然疗法,起源于19世纪欧洲的非主流医疗方式,通常被归类在替代医学中。自然医学把人体视为一个整体,相信人体存在生命力,有
  • 特里亚农条约《特里亚农条约》是1920年一项制定匈牙利边界的条约。第一次世界大战结束前,奥匈帝国灭亡,奥地利帝国的伙伴匈牙利王国宣布独立。由于奥匈帝国包含数个不同种族,故此需要重新划
  • 骚沙萨尔萨音乐,亦称骚沙音乐,是相当多元及受欢迎的拉丁美洲加勒比海音乐,在波多黎各乐手的演绎下,在世界各地皆有知名度。“萨尔萨”为“Salsa”的英文发音音译,但其发源地古巴和波
  • 土木结构建筑土木结构建筑(civil structure construction)即以泥土和木材为建筑主要材料的建筑。其优点是用料较易采集,施工难度小。但缺点是承载能力低,且容易失火,耐久性差。中国古代建筑
  • 风狸风狸是中国与日本传说中妖怪。中国的《本草纲目》,日本鸟山石燕的《今昔百鬼拾遗》,根岸镇卫的《耳袋》、《和汉三才图会》有记载。风狸又称风生兽,形似貂,蓝色。会飞,不怕火烧刀
  • 帕沃尔·霍赫朔尔纳帕沃尔·霍亚朔尔纳(斯洛伐克语:Pavol Hochschorner,1979年9月7日-),生于布拉迪斯拉发,是一名斯洛伐克皮划艇运动员。他的双胞胎兄弟彼得·霍赫朔尔纳同样也是皮划艇选手,两人经常搭
  • 当归煎丸当归煎丸属于中医方剂的经产剂,来自严用和,由8味中药组成,是用以治疗虚热带下的常用方剂,症状常见赤白带下,腹中疼痛,不饮食,身体羸瘦。《医方集解》将本方归于足少阴厥阴药。本方
  • 中也关系中也关系(阿拉伯语:العلاقات اليمنية الصينية‎)是指中华人民共和国与也门共和国之间的的国家关系。中也自建交以来双方一直保持着友好的外交关系。受20