朝花夕拾-树形结构区分

Posted on Edited on

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)
    • 同前驱