7 1 待插入的数 4 5 8 7 set 查找为什么高效 • 刚刚的构建方法是平衡二叉树。而实际 set 中采用的是更为高效的红黑树。 • 区别就是每个节点上多挂了一个 bool 类型的 flag 变量，表示这个节点是红是黑。 • 总之这样三下五除二下来他的插入效率比平衡二叉树高出一个常数，但复杂度还是 O(logn) 。 • 红黑树的具体异同我会放到最后再细讲，一下子讲太深都睡着了，反正只有插入和删除的 ，红黑 flag 先忽略，就当他是普通的平衡二叉树好了。 • 注意看，这颗二叉树是有规律的。 • 首先看根节点 5 ，他的左子节点是 2 ，右子节点是 8 。 2 < 5 < 8 。 • 满足：左子节点 < 父节点 < 右子节点 2 set 查找为什么高效 1 4 5 8 7 2 set 查找为什么高效 • 注意看，这颗二叉树是有规律的。 • 再看看节点 2 ，他的左子节点是 ，他的左子节点是 1 ，右子节点是 4 。 1 < 2 < 4 。 • 满足：左子节点 < 父节点 < 右子节点 1 4 5 8 7 2 set 查找为什么高效 • 注意看，这颗二叉树是有规律的。 • 再看看节点 8 ，他的左子节点是 7 ，没有右子节点。 7 < 8 。 • 满足：左子节点 < 父节点 1 4 5 8 7 2 set 查找为什么高效 • 这就是二叉排序树的构建规则。