朝花夕拾-树形结构区分

Treap

  • 每个结点有随机的优先级,使树满足优先级树(堆)的性质,其余是普通排序二叉树
  • 旋转:
    • 参数是子树根(引用子树根的儿子指针,否则要改一系列父子指针) ,旋转 即是 沉降,另一边的孩子上升,但该孩子可能丢失一个子树。
    • 引用原子树根可方便修改父亲指向自己的指针。
    • 总是因为查找才会引发旋转,所以旋转参数总是引用。
    • 没有返回值,因为新子树根就是父亲的儿子指针。
    • 记得维护其他数据域。
  • 插入:
    • 自带查找
    • 新结点分配随机优先级,像排序二叉树一样插到一个叶子上(每个结点有计数器,可节省插入相同结点),然后旋转维护优先级树。
    • 递归地写,insert()后判断一下是否需要leftRotate() / rightRotate()。
  • 删除:
    • 自带查找
    • 找到待删除结点,修改计数器(当且仅当计数器大于1!)。如果计数器就是1,就要将自己旋到外结点(没有儿子或有一个儿子),轻松自杀。
    • 引用root可以方便删掉父亲指向自己的指针。
    • 另一种删除方法:参考普通排序二叉树的删除,但优先级不能被拷贝。非递归地写能优化时间。
  • 查找:
    • 和一般的二叉排序树一样。
    • 返回值可以写成地址引用?
  • 分离:
    • 依赖于size,将树分离为两个指定大小的树。
    • 先找到割边,强行加入一个虚拟结点(优先级为无限大),旋转到根,这时左右子树已经被分离。
  • 合并:
    • 合并和分离相反。要求其中一棵treap的所有结点小于另一棵。
    • 强行加入一个虚拟结点作为根(优先级为无限小),连接两棵treap,然后删除虚拟结点。

Splay

  • 拥有将某一个结点旋转到根的操作Splay(&root, const x),并在大多数操作中主动调用splay()
  • 新建结点newNode(const v, const father = 0)
    • 返回地址
  • 旋转:
    • 因为splay()旋转涉及很多代结点,不能用引用简化代码,必须存父亲指针。对应的孩子指针、父亲指针必须成对修改。
    • 参数是被旋转子树根的孩子,先处理祖先的孩子指针,再处理孩子的父亲指针,最后处理被旋转的两个结点的指针。“上有老 下有小 求放过...”
    • 可能会导致splay树根的改变,但是只有splay()导致旋转,splay()中自带根的记录。
    • 没有返回值,因为地址对应的内容没有变。
  • Splay(&root, const x):
    • 参数root是splay树根,x是结点地址。root必须引用,因为splay操作会更改树根。
    • 所有包含splay()的函数都要引用root
    • 依赖于祖先两代。若x仅有父亲而没有祖父,相应地旋转就好了。如果x有祖父,而且三点“共线”,就要先旋转父亲,后旋转x;如果三点不“共线”,正常地做就好。
  • 插入(&root, const v)
    • 自带查找
    • 先判根,然后开始循环
    • 保存父亲y,引用孩子x,若x==0 则 x=newNode
    • 因为插入包含了splay(),所以要带引用root。
  • 删除(&root, const v):
    • 自带查找
    • 因为删除包含了splay(),所以要带引用root
    • 如果被删结点是外结点,轻松自杀,splay()替身或者splay()父亲。
    • 如果被删结点不是外结点,那么被删结点肯定有前驱和后继在子树上,任取一个代替自己,然后splay()自己
  • 前驱后继(&root const v) / (&root const x)
    • 将x旋到根,前驱就是左子树的最右结点,后继就是右子树的最左结点。
    • 因为包含了splay(),所以要带引用root
  • 有序合并join(&s1, s2):
    • 将s1的最大元素splay到根,然后将s2设为s1的右子树
    • 因为含有splay(),所以要带引用root
  • 无序合并Merge(s1, s2):
    • 依赖于额外数据域size
    • 遍历size小的splay树,逐个插入到另一颗splay树上
  • 划分split(&root, const v)
    • 自带查找
    • 将关键字为v的结点splay到根,左右子树分开即可。
    • 因为含有splay(),所以要带引用root
  • splay树应用区间操作
    • 关键字将是下标,或者没有关键字。在一些下标可能集体移动的场合,宜不设关键字。
    • 结点记录子树的总体信息,类似线段树,可包含延迟标记。
    • 对区间[a,b]操作:将a-1旋到根,切掉右子树(b+1在其中),再将b+1旋转到根,重新连接两棵树。这时b+1的左子树就是[a,b]
    • 在[a,a+1]中间插入一些数:将被插入的数构建成splay树。将a旋到根,a+1旋到根的右孩子。将新建的splay树挂成a+1的左孩子。
    • 重要的事情说n遍也不嫌多:小心root被更改。具体地说就是splay()要换根,只有splay()才能使用旋转。

普通排序二叉树

  • 重点是前驱和后继
  • 前驱(const v)
    • 必须自带查找
    • 在查找成功之前,记录最后一个往右走的结点,因为它可能是前驱
    • 查找成功之后,如果结点有左子树,那么左子树的最大结点一定是前驱
    • 如果一个结点是整棵树的最左(最小)结点,那么它没有前驱。
  • 后继(const v)
    • 同前驱