SGI STL的关联容器（map、set、multimap、multiset）底层都是基于红黑树（Red Black Tree，RBT）来实现的，红黑树是一种被广泛使用的二叉查找树（Binary Search Tree，BST），有比较良好的操作效率。

    一谈到二叉树，相信很多人一定会有一个疑问： 这玩意儿有什么用？ (当然这么多人里面肯定包括大学时候的我- -) 其实，我个人觉得这并不怪我们，是教科书写的有点问题，开始的时候没有给到大家明确的学习意义，开始就去讲如何遍历，如何从树变森林，如何做树的前序中序后序遍历。但这样的学习会让整个过程很无聊，太容易让人放弃了。所以在今天，请允许我用另外的方式来重新讲解一下吧~

    二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题，基于递归的二叉树遍历算法更是递归的经典应用。

    几日前在微博上和清华一博士讨论起一道数据结构选择题，我非常信心满满地给出了答案并且以为是对的，却发现和他给的标准答案相去甚远，去wiki和NIST网站查了一下才知道，原来中国大陆教材中的定义和美国以及我国港澳台地区是完全不同的.本科时用的数据结构教材虽然也是国外的，但是由于当时学习没有注意这些概念，之后就受考研时国内教材和考试的荼毒太深了.

    treap 是一个很有意思的数据结构，从名字也能看得出来，它是 tree 和 heap 的混合产物。为什么会有这么一个数据结构还得从二叉树(BST)说起。 我们都知道，普通的二叉树是不平衡的，在某些情况下进行插入删除操作可以导致时间复杂度从 O(logN) 下降到 O(N)。为了解决平衡的问题，有很多新的二叉树被引入，比如大家熟知的一些：Linux 内核中 CFS 使用到的红黑树(Red-black tree)，数据结构课上都会讲到的 AVL 树。这些树都因为要进行复杂的旋转操作而不容易实现。 那么有没有一个实现容易的平衡二叉树呢？Treap 就是一个。普通的二叉树节点只有 key，而 treap 又多了一个 priority，这里的 priority 就是 heap (优先队列)中的 priority。这样， treap 既可以利用二叉树的特性，又可以利用 heap 的特性了。