在线性时间内从排序数组构建红黑树 [英] Building Red-Black Tree from sorted array in linear time

问题描述

我知道如何用n个插入来构建它（每个插入具有O（log（n））效率）
（n * log（n））总体
，我也知道还可以使用线性时间从排序数组构建2-3-4树。
谁能提供有关红黑版本的简单说明？

i know how to build it with n insertions ( each with O(log(n)) efficiency ) (n*log(n)) overall ,i also know that the equivalent structure of 2-3-4 tree can also be build with linear time from sorted array. can anyone please provide a simple explanation about the red-black version?

推荐答案

无论您要构建哪种BST。算法将是相同的。只需构建平衡的二叉树。

No matter what kind of BST you are going to build. The algorithm will be the same. Only need to build balanced binary tree.

1. 将中间元素放置到当前位置


2. 放置[开始;


3. 将元素（居中；结束）放置在右侧子树中。

这是O（N）算法。可以证明结果树将是平衡的。

This is O(N) algorithm. It can be shown, that the result tree will be balanced.

我们有平衡的树，因此根据定义：

We have balanced tree, so by definition:

length（最长路径）-length（最短路径）< = 1

length(longest path) - length(shortest path) <= 1

因此，您需要将所有节点标记为黑色，除了树中最深的节点（将其标记为红色）。

So you need to mark all nodes as black, except the deepest nodes in the tree (mark them as red).

这篇关于在线性时间内从排序数组构建红黑树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！