Mic*_*l G 2 algorithm tree big-o red-black-tree data-structures
我知道如何使用n个插入(每个都有O(log(n))效率)(n*log(n))整体构建它,我也知道2-3-4树的等效结构也可以用排序数组的线性时间.任何人都可以提供有关红黑版本的简单说明吗？
无论你打算建造什么样的BST.算法将是相同的.只需要构建平衡的二叉树.
这是O(N)算法.可以看出,结果树将是平衡的.
我们有平衡的树,所以根据定义:
长度(最长路径) - 长度(最短路径)<= 1
所以你需要将所有节点标记为黑色,除了树中最深的节点(将它们标记为红色).