什么是树堆

树堆(Treap) 就是用一堆树堆起来的 (不过好像也没什么不对
就是既有二叉搜索树的性质, 又有的性质的一种平衡树
这种平衡树只需要用到两种旋转, 适合像本小姐这种菜到不知道哪里去的大菜菜用来入门平衡树

树堆

树堆是一种平衡树, 它的节点除了记录值以外, 还记录一个额外的数值 —- 优先级
树堆的思想, 其实就是将值随机插入, 以做到基本平衡的效果 (但对于非洲人来说永远都是一条直链)
但在很多时候, 是被迫顺序插入的
于是便记录一个额外的数值 优先级
各个节点的优先级需要满足堆的性质, 即优先级小(或大)的在上层(本文中所用的树堆均为小顶堆, 即根节点的优先级小于其他节点的优先级)
这样子就实现了随机插入的目的
一个树堆看起来大概是这样子的(方括号内是优先级)

插入

讲了这么多 (哪里多了)
终于要到正题了:
如何向一个树堆插入一个元素
插入方式自然是想二叉搜索树那样插入
但插入完后, 还要做另外一件事
那就是 根据堆的性质和节点的优先级, 旋转树
如果父节点的优先级比插入的节点的优先级大, 就旋转
那么应该怎样选择旋转的方向呢
如果插入的节点是父节点的右节点, 则左旋
反之右旋

例如, 向开头的那个树堆, 插入一个 12(17) 节点
按照二叉树的插入, 会变成这个样子
但会发现, 这个节点的优先级比它父节点的 15(21) 优先级要小
并且还是父节点的左孩子
那么右旋

发现父节点的优先级小, 结束旋转
继续插入 11(12)

比父节点的优先级小, 并且是左孩子, 右旋
发现父节点仍然是优先级小, 现在是父节点的右孩子, 左旋
没有父节点了, 停止旋转

最后

树堆大概就是一个这样子的平衡树
它能保证树大致是平衡的 (只针对欧洲人而言)
除了一些极端情况, 才会变成一条似直链 (对于非洲人而言)
什。。什么。。。
删。。删除节点。。。
这个。。这么简单的东西, 本小姐当然会啦
能找到本小姐的博客, 肯定也是像本小姐一样聪明的人
所以, 就给你们自己去摸索吧

Source Code