Question

二叉树是另一个基本的数据结构。它是一个树，但是每个节点最多包含两个指向其他节点的指针。每个节点包含键和/或值。 二叉树在键值字典的实现中是常用数据结构。 二叉树至少包含三个重要的属性： 所有的键的存储是排序的。 任何类型的键都容易存储。二叉树并不知道键的类型，因此需要键比较算法。 查找键的速度相比于链表和数组要快。 下面是一个非常简单的例子，我们在二叉树中存储下面这些数据 0，1，2，3，5，6，9，10，11，12，20，99，100，101，107，1001，1010.

所有小于根节点键的键存储在树的左侧，所有大于根节点键的键存储在树的右侧。 因此，查找算法就很直接，当要查找的值小于当前节点的键的值，则查找左侧；如果大于当前节点的键的值，则查找右侧；当值相等时，则停止查找。这就是为什么通过键比较函数，算法可以查找数值、文本串等。 所有键的值都是唯一的。 如果这样，为了在 n 个键的平衡二叉树中查找一个键将需要 log2 n 步。1000 个键需要 10 步，10000 个键需要 13 步。但是这要求树总是平衡的，即键应该均匀的分布在树的不同层里。插入和删除操作需要保持树的平衡状态。 有一些流行的平衡算法可用，包括 AVL 树和红黑树。红黑树通过给节点增加一个 color 值来简化平衡过程，因此每个节点可能是红或者黑。 GCC 和 MSVC 中的 std::map 和 std::set 模板的实现均采用了红黑树。 std::set 只包含键。std::map 是 set 的扩展，它在每个节点中包含一个值。