伸展树——自顶向下-阿里云开发者社区

开发者社区> 指尖的舞曲> 正文

伸展树——自顶向下

简介: 三种旋转    当我们沿着树向下搜索某个节点X的时候,我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。 没有被移走的节点构成的树称作中树。在伸展操作的过程中: 1、当前节点X是中树的根。
+关注继续查看

三种旋转

   当我们沿着树向下搜索某个节点X的时候,我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。

没有被移走的节点构成的树称作中树。在伸展操作的过程中:

1、当前节点X是中树的根。
2、左树L保存小于X的节点。
3、右树R保存大于X的节点。
开始时候,X是树T的根,左右树L和R都是空的。
1、zig:
 
                                
    如上图,在搜索到X的时候,所查找的节点比X小,将Y旋转到中树的树根。旋转之后,X及其右子树被移动到右树上。很显然,右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置,也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点,其值越大。
2、zig-zig:
 
                                
    在这种情况下,所查找的节点在Z的子树中,也就是,所查找的节点比X和Y都小。所以要将X,Y及其右子树都移动到右树中。首先是Y绕X右旋,然后Z绕Y右旋,最后将Z的右子树(此时Z的右子节点为Y)移动到右树中。注意右树中挂载点的位置。
3、zig-zag:
 
                            
    在这种情况中,首先将Y右旋到根。这和Zig的情况是一样的。然后变成上图右边所示的形状。接着,对Z进行左旋,将Y及其左子树移动到左树上。这样,这种情况就被分成了两个Zig情况。这样,在编程的时候就会简化,但是操作的数目增加(相当于两次Zig情况)。
    最后,在查找到节点后,将三棵树合并。如图:
 
                                

    将中树的左右子树分别连接到左树的右子树和右树的左子树上。将左右树作为X的左右子树。重新最成了一所查找的节点为根的树。

  右连接:将当前根及其右子树连接到右树上。左子结点作为新根。
  左连接:将当前根及其左子树连接到左树上。右子结点作为新根。

越是在路径前面被移动到右树的节点,其值越大;越是在路径前面移动到左树的节点,其值越小。

 这很显然,右连接,将当前根以及右子树全部连接到右树,即把整课树中值大的一部分移走(大于等于当前根),

 后面,在进行右连接,其值肯定小于之前的,所以,要加在右树的左边。

 

伸展树伪代码

 右连接:将当前根及其右子树连接到右树上。左子结点作为新根。
 左连接:将当前根及其左子树连接到左树上。右子结点作为新根。
  T : 当前的根节点。
  Function Top-Down-Splay
     Do
          If X 小于 T Then
               If X 等于 T 的左子结点 Then           //zig
                 右连接
               ElseIf X 小于 T 的左子结点 Then       //zig-zig
                 T的左子节点绕T右旋
                 右连接
               Else X大于 T 的左子结点 Then          //zig-zag
                 右连接
                 左连接
               EndIf    
           ElseIf X大于 T Then
               IF X 等于 T 的右子结点 Then
                 左连接
               ElseIf X 大于 T 的右子结点 Then
                 T的右子节点绕T左旋
                 左连接
               Else X小于 T 的右子结点 Then
                 左连接
                 右连接
               EndIf
          EndIf
     While  !(找到 X或遇到空节点)
      组合左中右树
  EndFunction

 

zig-zag这种情形,可以先按zig处理。第二次循环在进行一次处理。简化代码如下:

  Function Top-Down-Splay
      Do
          If X 小于 T Then
               If X 小于 T 的左孩子 Then
                  T的左子节点绕T右旋
               EndIf    
               右连接
              Else If X大于 T Then
                If X 大于 T 的右孩子 Then
                    T的右子节点绕T左旋
                EndIf
                左连接
              EndIf
      While  !(找到 X或遇到空节点)
      组合左中右树
  EndFuntion

例子

下面是一个查找节点19的例子:
    在例子中,树中并没有节点19,最后,距离节点最近的节点18被旋转到了根作为新的根。节点20也是距离节点19最近的节点,但是节点20没有成为新根,这和节点20在原来树中的位置有关系。
 
  如果查找的元素不在树中,则寻找过程中出现空的上一个节点即为根节点。

CPP代码

 .h

struct SplayNode
{
    int element;
    SplayNode *left;
    SplayNode *right;
};

class SplayTree
{
    public:
        SplayTree();
        ~SplayTree();
        
        void Insert(int data);
        void Remove(int data);
        SplayNode *Find(int data);

        
    private:
        SplayNode *_tree;
        
        SplayNode *_Insert(SplayNode *T, int item);
        SplayNode *_Remove(SplayNode *T, int item);
        SplayNode *_Splay(SplayNode *X, int Item);
        
        SplayNode *_SingleToRight(SplayNode *K2);  
                SplayNode *_SingleToLeft(SplayNode *K2); 
  
                void  _MakeEmpty(SplayNode *root);
            
};

.cpp

SplayTree::SplayTree()
{
    _tree = NULL;
}


SplayTree::~SplayTree()
{
    _MakeEmpty(_tree);
}

void SplayTree::Insert(int data)
{
    _tree = _Insert(_tree, data);
}

void SplayTree::Remove(int data)
{
    _tree = _Remove(_tree, data);
}

SplayNode *SplayTree::_SingleToRight(SplayNode *K2)  
{  
    SplayNode *K1 = K2->left;  
    K2->left = K1->right;  
    K1->right = K2;  
        
    return K1;  
}  
  
          
SplayNode *SplayTree::_SingleToLeft(SplayNode *K2)  
{  
    SplayNode *K1 = K2->right;  
    K2->right = K1->left;  
    K1->left  = K2;  
          
    return K1;  
} 
        
SplayNode *SplayTree::_Splay(SplayNode *X, int item)
{
    static struct SplayNode Header;
    SplayNode *leftTreeMax, *rightTreeMin;
    
    Header.left = Header.right = NULL;
    leftTreeMax = rightTreeMin = &Header;
    
    while( X != NULL && item != X->element)
    {

        if(item < X->element)
        {
            if(X->left == NULL)
                break;
            if(item < X->left->element)
            {
                X = _SingleToRight(X); 
            } 
            if( X->left == NULL)
                break;
                        //右连接
                       &nbsp;rightTreeMin->left = X;
            rightTreeMin       = X;
            X                  = X->left;
        }
        else
        {
            if(X->right == NULL)
                break;
            if(item > X->right->element)
            {
                X = _SingleToLeft(X);
            }
            if(X->right == NULL)
                break;
                        //左连接
            &nbsp;           leftTreeMax->right = X;
            leftTreeMax        = X;
            X                  = X->right;
        }
    }
    leftTreeMax->right = X->left;
    rightTreeMin->left = X->right;
    X->left = Header.right;
    X->right = Header.left;
    
    return X;
}


SplayNode *SplayTree::_Insert(SplayNode *T, int item)
{
    static SplayNode* newNode = NULL;
    
    if(newNode == NULL)
    {
        newNode = new SplayNode;
    }
    newNode->element = item;
    
    if(T == NULL)
    {
        newNode->left = newNode->right = NULL;
        T = newNode;
    }
    else
    {
        T = _Splay(T, item);
        if(item < T->element)
        {
            newNode->left = T->left;
            newNode->right = T;
            T->left = NULL;
            T = newNode;
        }
        else if(T->element < item)
        {
            newNode->right = T->right;
            newNode->left = T;
            T->right = NULL;
            T = newNode;
        }
        else
        {
            delete newNode;
        }
    }
    newNode = NULL;
    return T;
}

SplayNode *SplayTree::_Remove(SplayNode *T, int item)
{
    SplayNode *newTree;
    
    if(T != NULL)
    {
        T = _Splay(T, item);
        if(item == T->element)
        {
            if(T->left == NULL)
            {
                newTree = T->right;
            }
            else
            {
                newTree = T->left;
                newTree = _Splay(newTree, item);
                newTree->right = T->right;
            }
            delete T;
            T = newTree;
        }
    }
    return T;
}

void SplayTree::_MakeEmpty(SplayNode *T)  
{  
    if(T != NULL)  
    {  
        _MakeEmpty(T->left);  
        _MakeEmpty(T->right);  
        delete T;  
    }  
}


SplayNode *SplayTree::Find(int data)
{
    _tree = _Splay(_tree, data);
    if(_tree->element == data)
        return _tree;
    else
        return NULL;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9489 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12035 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9050 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13172 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4619 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4009 0
+关注
指尖的舞曲
目前在阿里巴巴搬砖
916
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载