伸展树与跳表

第3章伸展树与跳表字典：词条的集合，一种数据结构，主要包括搜索、插入和删除等根本运算。伸展树和跳表：是表示字典的高级数据结构。3.1伸展树3.1.1二叉搜索树根的左子树的所有节点的值都小于根节点，右子树的所有节点的值都大于根节点子树也是二叉搜索树用于表示动态集实现动态集上定义的根本运算搜索操作ResultCodeSearch(Kkey,T&x)const在集合中搜索关键字为key的元素，假设存在，将其值赋值给x,函数返回Success，否那么返回NotPresent。enumResultCode{Underflow,Overflow,Success,Duplicate,Fail,NotPresent};

插入操作ResultCodeInsert(Tx)在集合中搜索关键字为x.key的元素，假设存在返回Duplicate。否那么，假设集合已满，返回Overflow,假设未满，插入x,返回Success。删除操作ResultCodeRemove(Kkey)在集合中搜索关键字值为key的元素，假设存删除并返回Success，否那么，返回NotPresent。二叉平衡树每次插入或删除后，重新平衡树形，使之始终保持平衡。能保证性能，但增加了实现难度。伸展树自调节搜索树。在伸展树上，执行一个m次运算〔搜索、插入、删除〕，总的时间为O(mlogn)具有良好的平均分摊代价。是平衡搜索树的很好替代结构。3.1.2自调节树和伸展树伸展树:一颗二叉搜索树,要求每访问一个元素后,将最新访问的元素移至二叉搜索树的根部,以保证经常被访问的元素靠近根节点.将一个元素移至根部的操作称为一次伸展.一般情况下,一个元素被访问后,下一次还要访问它的时机比较大.是自调整搜索树3.1.3伸展操作一棵伸展树是一棵二叉搜索树,其搜索,插入等操作与二叉搜索树相同,只是每次操作后都紧跟一次伸展操作伸展操作的目的是将节点x移至根节点,被移动的节点为伸展节点.3.1.3伸展操作伸展节点确实定1.搜索成功的节点2.新插入的节点3.被删除节点的双亲4.假设上述运算失败,那么搜索过程中遇到的最后一个节点为伸展节点.3.1.3伸展操作一次伸展操作由一组旋转动作组成单一旋转3.1.3伸展操作单一旋转(zig右旋转)规那么伸展节点的右子树作为其父节点的左子树伸展节点与其父节点交换位置左旋转(zag)规那么伸展节点的左子树作为其父节点的右子树伸展节点与其父节点交换位置3.1.3伸展操作一次伸展操作由一组旋转动作组成双重旋转双重旋转1.zigzig旋转12p的右子树做g的左子树,然后g做p的右子树;第1步:将p右旋转(zig)到g,即pg两节点换位;q的右子树做p的左子树,然后p做q的右子树;第2步:接着将q右旋转到p双重旋转2.zigzag旋转q的左子树做p的右子树,然后p做q的右子树;第1步:将q左旋转(zag)到p,即pq两节点换位;第2步:q的右子树做g的左子树,然后g做q的右子树;12伸展操作既可以自底向上,也可以自顶向下进行.2112作业:描述以下伸展过程3.1.4伸展树类伸展树类旋转的实现插入的实现分摊分析(略)复习：类的定义classStack{public: Stack(ints);//构造函数 virtual~Stack();//析构函数 intpop(int&num);//函数原型，函数的声明 intpush(intnum);private: int*data;//栈数据存储 intmemNum;//栈元素个数 intsize;//栈大小};类中成员函数的实现#include"Stack.h"Stack::Stack(ints){ data=newint[s]; size=s; memNum=0;}Stack::~Stack(){ delete[]data;}intStack::pop(int&num){ if(memNum==0) return0; num=data[--memNum]; return1;}intStack::push(intmem){ if(memNum==size) return0; data[memNum++]=mem; return1;}类的使用－－定义对象StackoneStack;StackarrayOfStack[10];Stack*pStack;//指针Stack&s=oneStack;//引用－为变量指定别名注意：声明一个类就是声明了一种数据类型，它并不接收和存储具体的值，只能作为生产具体对象的样板，定义对象后才能为对象并且只能为对象分配存储空间。类的定义与实现一般分别放在.h和.cpp文件中。对象的引用格式对象名.数据成员名对象名.成员函数名－－必须是公有属性几点注意：类的数据成员在类定义中声明，但不能在类中赋值。数据成员的初始化只能在构造函数中进行，或通过成员函数进行读写。创立对象时自动调用构造函数。析构函数用来释放对象所占用的存储空间。在撤销对象时自动调用。new--分配存储空间delete--释放空间例:在定义了类Stack之后Stackone;Stackarray[10];Stack*ptr=&one;Stack&s=one;Stack*pone,*pten;pone=newStack;pten=newStack[10];构造函数1构造函数的作用实现对数据成员的内存分配和初始化.2构造函数执行的时机在创立对象时自动调用,与声明对象的方式有关全局对象(定义在所有函数外面的对象)在所有程序执行之前被创立.即在main函数第一条语句执行之前,全局对象的构造函数已经被调用.4.4.2构造函数执行的时机局部动态对象(定义在程序块内),程序执行到声明对象的语句时被创立.局部静态对象(在程序块内用static声明),在执行到声明对象的语句时被创立.动态创立的对象(用new创立),在执行到该new语句时被创立.3.1.4伸展树类结点类

template<classT>

struct

BTNode

{//二叉树结点类

Telement;

BTNode*lChild,*rChild;

BTNode(constT&x) { element=x;lChild=rChild=NULL; }};构造函数lChildelementrChild伸展树类

template<classT,classK>classSPTree

{//伸展树类

public:

SPTree(){root=NULL;}

ResultCode

Insert(Tx);

protected:

BTNode<T>*root;private:

ResultCode

Insert(BTNode<T>*&p,Tx); voidLRot(BTNode<T>*&p); voidRRot(BTNode<T>*&p);

};旋转函数〔左旋转〕

template<classT>voidSPTree<T>::LRot(BTNode<T>*&p){//前置条件：p有右孩子，实现向左旋转

BTNode<T>*r=p->rChild; p->rChild=r->lChild; r->lChild=p;p=r;//p的右孩子成为子树根

}4350pr指针p指向根节点另设指针r指向p的右孩子r的左子树作为p的右子树p作为r的左孩子r作为p4350pr旋转函数〔左旋转〕旋转函数〔右旋转〕template<classT>voidSPTree<T>::RRot(BTNode<T>*&p){//前置条件：p有左孩子，实现向右旋转

BTNode<T>*r=p->lChild; p->lChild=r->rChild; r->rChild=p;p=r;//p的左孩子成为子树根}4330pr旋转函数〔右旋转〕指针变量p指向根设指针r指向p的左孩子r的右子树作p的左子树p作r的右子树r作p4330pr问题：要插入节点30树为空树的根节点就等于3030小于根节点时：根节点左孩子为空等于根节点的左孩子小于根节点的左孩子大于根节点的左孩子4.30大于根节点时：根节点右孩子为空等于根节点的右孩子小于根节点的右孩子大于根节点的右孩子3.1.6插入运算的实现插入30433250304343305043350空树三二一四五六233502333023325四五六问题：要插入节点30树为空－－新建节点，值为30，作为根树的根节点就等于30，直接返回duplicate30小于根节点时：如果根节点左孩子为空，那么：新建节点，值为30，与根节点互换位置，返回success。如果等于根节点的左孩子那么左旋转以互换根节点与其左孩子，返回duplicate如果小于根节点的左孩子那么以左孩子的左孩子为新的根节点，递归调用，之后右旋转如果大于根节点的左孩子，那么以根的左孩子的右孩子为根，递归，之后左旋转，右旋转