我知道如何通过 n 次插入来构建它（每次插入的效率为 O(log(n))）
(n*log(n)) 总体
，我还知道 2-3-4 树的等效结构也可以用线性时间从排序数组构建。
谁能提供有关红黑版本的简单解释吗？
无论您要构建哪种 BST。算法将是相同的。只需要构建平衡二叉树。
- 将中间元素放置到当前位置
- 地点[开始； middle) 元素到左子树。
- 将（中间；末端）元素放置到右子树。
这是 O(N) 算法。可以证明，结果树将是平衡的。
我们有平衡树，所以根据定义：
长度(最长路径) - 长度(最短路径)
因此，您需要将所有节点标记为黑色，除了树中最深的节点（将它们标记为红色）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
