伸展树的基本实现和区间操作

#include <stdio.h> #include "lcl.h" //更新以 root 为根的树的 count 域 void refresh( Node root ) { root->count=1; root->turn = 0; //恢复turn int max = root->key ; if( root->lch ) { refresh( root->lch ); max = ( max > root->lch->max ) ? max : root->lch->max ; root->count += root->lch->count; } if( root->rch ) { refresh( root->rch ); max = ( max > root->rch->max ) ? max : root->rch->max ; root->count += root->rch->count; } root->max = max; } Node create_node(int key , Node parent) { Node node = ( Node ) malloc( sizeof( struct Node) ); node->add=0; node->max=0; node->turn=0; node->count=0; node->key = key; node->parent = parent; node ->lch = NULL; node->rch = NULL; return node; } //左偏树 Tree create_tree_01() { Node a = create_node( 1, NULL ); Node b = create_node( 2, a ); Node c = create_node( 3, a ); Node d = create_node( 4, b ); Node e = create_node( 5, b ); Node f = create_node( 6, d ); Node g = create_node( 7, d ); Node h = create_node( 8, f ); Node i = create_node( 9, f ); a->lch = b; a->rch = c; b->lch = d; b->rch = e; d->lch = f; d->rch = g; f->lch = h; f->rch = i; return a; } //右偏树 Tree create_tree_02() { Node a = create_node( 2, NULL ); Node b = create_node( 1, a ); Node c = create_node( 4, a ); Node d = create_node( 3, c ); Node e = create_node( 6, c ); Node f = create_node( 5, e ); Node g = create_node( 8, e ); Node h = create_node( 7, f ); Node i = create_node( 9, f); a->lch = b; a->rch = c; c->lch = d; c->rch = e; e->lch = f; e->rch = g; g->lch = h; g->rch = i; return a; } //zig_zag Tree create_tree_03() { Node a = create_node( 2, NULL ); Node b = create_node( 1, a ); Node c = create_node( 4, a ); Node d = create_node( 3, c ); Node e = create_node( 8, c ); Node f = create_node( 6, e ); Node g = create_node( 9, e ); Node h = create_node( 5, f ); Node i = create_node( 7, f); a->lch = b; a->rch = c; c->lch = d; c->rch = e; e->lch = f; e->rch = g; f->lch = h; f->rch = i; return a; } //join测试树1 Node create_tree_04() { Node a = create_node( 2, NULL ); Node b = create_node( 1, a ); Node c = create_node( 3, a ); a->lch = b; a->rch = c; refresh( a ); return a; } //join测试树2 Node create_tree_05() { Node a = create_node( 5, NULL ); Node b = create_node( 4, a ); Node c = create_node( 6, a ); a->lch = b; a->rch = c; refresh( a ); return a; } void print_node(Node node) { printf("Node: key=%d",node->key ); if( node->parent ){ printf(",p=%d", node->parent ->key ); }else{ printf(",p=NULL"); } if( node->lch ){ printf(",l=%d" , node->lch->key ); }else{ printf(",l=NULL"); } if( node->rch ){ printf(",r=%d", node->rch->key ); }else{ printf(",r=NULL"); } printf("\n"); } //先序遍历 void print_tree(Tree tree , Stack S) { Node node; //printf("%d(%d) ", tree ->key ,tree->count ); printf("%d ", tree ->key ); if( tree->rch ) { push(S , tree->rch ); } if( tree->lch ) { print_tree( tree->lch , S); }else if( !is_empty( S )){ node = pop( S ); print_tree( node , S ); } } //单次右旋以 root 节点 为根节点的树 Node zig( Tree tree , Node root) { Node lc = root->lch; Node parent = root->parent; // 处理翻转标志 tree->turn = 1; lc->turn = 1; root->turn = 1; //处理父节点关系 if( parent ) { if( root == parent->lch ) { parent->lch = lc; }else{ parent->rch = lc; } lc->parent = parent; }else{ lc->parent = NULL; } //翻转 if( lc != NULL ) { root->lch = lc->rch; if( lc->rch ) { lc->rch->parent = root; } lc->rch = root; root->parent = lc; if( parent ) { return tree; }else{ return lc; } } return tree; } //单次左旋以 root 节点 为根节点的树 Node zag( Tree tree , Node root) { Node rc = root->rch; Node parent = root->parent; // 处理翻转标志 tree->turn = 1; rc->turn = 1; root->turn = 1; //处理父节点关系 if( parent ) { if( root == parent->lch ) { parent->lch = rc; }else{ parent->rch = rc; } rc->parent = parent; }else{ rc->parent = NULL; } //翻转 if( rc != NULL ) { root->rch = rc->lch; if( rc->lch ) { rc->lch->parent = root; } rc->lch = root; root->parent = rc; if( parent ) { return tree; }else{ return rc; } } return tree; } //右双旋以 root 节点 为根节点的树 Node zig_zig( Tree tree , Node root) { Node lc = root->lch; Node node=zig( tree , root ); return zig( node , lc ); } //左双旋以 root 节点 为根节点的树 Node zag_zag( Tree tree , Node root) { Node rc = root->rch; Node node=zag( tree , root ); return zag( node , rc ); } Node zig_zag( Tree tree , Node root) { Node node=zig( tree , root->rch ); return zag( node , root ); } Node zag_zig( Tree tree , Node root) { Node node=zag( tree , root->lch ); return zig( node , root ); } //根据目标节点的结构选择相应的算法，策略模式 Node zig_zag_manager( Tree tree , Node node ) { Node parent = node->parent; if( parent == tree ) //1 { if( parent->lch == node ) { return zig( tree , parent ); }else{ return zag( tree , parent ); } }else if( parent->lch == node ){ //2 Node grand = parent->parent; if( grand->lch == parent ){ /*左左*/ return zig_zig( tree , grand ); }else{ /*右左*/ return zig_zag( tree , grand ); } }else if( parent->rch == node ){ //3 Node grand = parent->parent; if( grand->lch == parent ){ /*左右*/ return zag_zig( tree , grand ); }else{ /*右右*/ return zag_zag( tree , grand ); } } return tree; } //将目标节点调整到树的根部，并返回树根 Node splay(Tree tree , Node node) { while( node->parent!=NULL ) { zig_zag_manager( tree , node ); } return node; } //合并tree1 和 tree2 ,要求 tree1 所有元素小于 tree2 任一元素 Node join( Tree tree1, Tree tree2) { //找打 tree1 中最大的元素 Node temp = tree1; while( temp->rch != NULL ) { temp = temp->rch; } //将 temp调至 tree1的根部 splay( tree1 ,temp ); //将 tree2 作为 temp的右子树 temp->rch = tree2; tree2->parent = temp; return temp; } //以 node 为届，分离 tree 的左子树 ,返回剩余部分 Node spilt( Tree tree , Node node ) { tree = splay( tree , node ); //将 node 调至根部 Node lc = tree->lch; tree->lch = NULL; if( lc ) { lc->parent = NULL; } return tree; } //以 node 为届，分离 tree 的右子树 Node spilt_rch( Tree tree , Node node ) { tree = splay( tree , node ); //将 node 调至根部 Node rc = tree->rch; tree->rch = NULL; if( rc ) { rc->parent = NULL; } return tree; } //寻找key节点 Node find( Tree tree , int key ) { Node curr = tree; while( curr != NULL ) { if( curr->key == key ){ splay( tree , curr ); return curr; } else if( curr->key > key ){ curr = curr->lch; }else{ curr = curr->rch; } } return NULL; } //获得以 root 为根的树的节点总数 int get_count( Node root ) { if( root->turn !=0 ) //节点被翻转过 { refresh( root ); } return root->count; } //获得以 root 为根的树的最大值 int get_max( Node root ) { if( root->turn !=0 ) //节点被翻转过 { refresh( root ); } return root->max; } //获得第 i 大的元素 Node get_max_i( Tree tree , int i) { Node curr = tree ,lc = tree->lch , rc = tree->rch; int new_count = 0 ,rcount=0,lcount=0 ,count=0 ; if( rc ) { rcount = get_count( rc ); if( rcount == i-1 ) { return curr ; } if( rcount > i-1 ) { return get_max_i( curr ->rch ,i ); } if( rcount < i-1 ) { new_count = i - rcount -1 ; return get_max_i( lc , new_count ); } }else if( curr->lch ){