第一百三六章 随机取样（上） (第1/1页)

    “你看这颗满二叉树”。

    “假设它的高度为K，那么它就有2的K次方减去1个节点数”。

    杨成边走边向科勒文介绍。

    随着一行人深入二叉树森林，越来越多奇形怪状的树出现在他们眼前。

    有一种树，它的节点要么是红色，要么是黑色的。

    但它的叶子却都是黑色的。

    如果你仔细地观察每个叶子到树根的路径，就会发现一个惊人的规律：

    节点间不会出现连续的红色节点，而是红色与黑色交替出现。

    “红黑树”，杨成很快就认出了。

    这种树最早的学名其实是叫“对称二**树”，后来才提出的“红黑树”这个概念。

    它应用很广，常常用来实现关联数组。