6天通吃树结构3—— 第三天 Treap树

6 天通吃树结构 第三天 Treap 树 我们知道 二叉查找树相对来说比较容易形成最坏的链表情况 所以前辈们想 尽了各种优化策略 包括 AVL 红黑 以及今天 要讲的 Treap 树 Treap 树算是一种简单的优化策略 这名字大家也能猜到 树和堆的合体 其 实原理比较简单 在树中维护一个 优先级 优先级 采用随机数的方法 但是 优先级 必须满足根堆的性质 当然是 大根堆 或者 小根堆 都无所谓 比如下面的一棵树 从树中我们可以看到 节点中的 key 满足 二叉查找树 节点中的 优先级 满足小根堆 一 基本操作 1 定义 1 region Treap 树节点 2 3 Treap 树 4 5 6 7 public class TreapNode 8 9 10 节点元素 11 12 public K key 13 14 15 优先级 采用随机数 16 17 public int priority 18 19 20 节点中的附加值 21 22 public HashSet attach new HashSet 23 24 25 左节点 26 27 public TreapNode left 28 29 30 右节点 31 32 public TreapNode right 33 34 public TreapNode 35 36 public TreapNode K key V value TreapNode left TreapNode right 37 38 KV 键值对 39 this key key 40 this priority new Random DateTime Now Millisecond Next 0 int MaxValue 41 this attach Add value 42 43 this left left 44 this right right 45 46 47 endregion 节点里面定义了一个 priority 作为 堆定义 的旋转因子 因子采用 随机数 2 添加 首先我们知道各个节点的 优先级 是采用随机数的方法 那么就存在一个问题 当 我们插入一个节点后 优先级不满足 堆定义 的 时候我们该怎么办 前辈说此时需要旋转 直到满足堆定义为止 旋转有两种方式 如果大家玩转了 AVL 那么对 Treap 中的旋转的理解轻而易举 左左情况旋转 从图中可以看出 当我们插入 节点 12 的时候 此时 堆性质 遭到破坏 必须进行旋 转 我们发现优先级是 6 9 所以就要进行 左左情况旋转 最终也就形成了我们需要的结果 右右情况旋转 既然理解了 左左情况旋转 右右情况也是同样的道理 优先级中发现 6 9 进行 右右旋转 最终达到我们要的效果 1 region 添加操作 2 3 添加操作 4 5 6 7 public void Add K key V value 8 9 node Add key value node 10 11 endregion 12 13 region 添加操作 14 15 添加操作 16 17 18 19 20 21 public TreapNode Add K key V value TreapNode tree 22 23 if tree null 24 tree new TreapNode key value null null 25 26 左子树 27 if key CompareTo tree key 0 28 29 tree left Add key value tree left 30 31 根据小根堆性质 需要 左左情况旋转 32 if tree left priority 0 40 41 tree right Add key value tree right 42 43 根据小根堆性质 需要 右右情况旋转 44 if tree right priority tree priority 45 46 tree RotateRR tree 47 48 49 50 将 value 追加到附加值中 也可对应重复元素 51 if key CompareTo tree key 0 52 tree attach Add value 53 54 return tree 55 56 endregion 3 删除 跟普通的二叉查找树一样 删除结点存在三种情况 叶子结点 跟普通查找树一样 直接释放本节点即可 单孩子结点 跟普通查找树一样操作 满孩子结点 其实在 treap 中删除满孩子结点有两种方式 第一种 跟普通的二叉查找树一样 找到 右子树 的最左结点 15 拷贝元素的值 但不拷贝元素的优先级 然后在右子树中 删除 结点 15 即可 最终效果如下图 第二种 将 结点下旋 直到该节点不是 满孩子的情况 该赋 null 的赋 null 该将 孩子结点顶上的就顶上 如下图 当然从理论上来说 第二种删除方法更合理 这里我写的就是第二种情况的代码 1 region 删除当前树中的节点 2 3 删除当前树中的节点 4 5 6 7 public void Remove K key V value 8 9 node Remove key value node 10 11 endregion 12 13 region 删除当前树中的节点 14 15 删除当前树中的节点 16 17 18 19 20 public TreapNode Remove K key V value TreapNode tree 21 22 if tree null 23 return null 24 25 左子树 26 if key CompareTo tree key 0 32 33 tree right Remove key value tree right 34 35 相等的情况 36 if key CompareTo tree key 0 37 38 判断里面的 HashSet 是否有多值 39 if tree attach Count 1 40 41 实现惰性删除 42 tree attach Remove value 43 44 else 45 46 有两个孩子的情况 47 if tree left null 53 54 else 55 56 否则 右旋 57 tree RotateRR tree 58 59 60 继续旋转 61 tree Remove key value tree 62 63 else 64 65 如果旋转后已经变成了叶子节点则直接删除 66 if tree null 67 return null 68 69 最后就是单支树 70 tree tree left null tree right tree left 71 72 73 74 75 return tree 76 77 endregion 4 总结 treap 树在 CURD 中是期望的 logN 由于我们加了 优先级 所以会出现 链表 的情 况几乎不存在 但是他的 Add 和 Remove 相比严格的 平衡二叉树有更少的旋转