Go中秘而不宣的数据结构 Treap：平衡树不一定就用红黑树

文章预览

秘而不宣系列 Go中秘而不宣的数据结构 runq, 难怪运行时调度那么好 Go中秘而不宣的数据结构 spmc, 10倍性能于 channel treap 是一棵二叉树，它同时维护二叉搜索树 （BST） 和堆的属性, 所以由此得名 (tree + heap   ⇒  treap)。 从形式上讲，treap （tree + heap） 是一棵二叉树，其节点包含两个值，一个   key   和一个   priority ，这样 key 保持 BST 属性， priority 是一个保持 heap 属性的随机值（至于是最大堆还是最小堆并不重要）。相对于其他的平衡二叉搜索树，treap 的特点是实现简单，且能基本实现随机平衡的结构。属于弱平衡树。 treap 由 Raimund Siedel 和 Cecilia Aragon 于 1989 年提出。 treap 通常也被称为“笛卡尔树”，因为它很容易嵌入到笛卡尔平面中：  具体来说， treap 是一种在二叉树中存储键值对 (X,Y) 的数据结构，其特点是：按 X 值满足二叉搜索树 ………………………………