从 BST 树创建红黑树 - 最快的方法？
Creating a Red-Black tree from BST tree - the fastest way?
我必须为我的大学课程创建并描述一种算法，该算法获取 BST 树 T 并创建满足属性（并且尽可能快）的新 BST 树 T'：
1) T' 与 T
具有完全相同的键值
2) T' 是红黑树
到目前为止我只有一个想法：随机化0或1。如果为0，则从T的左子树中获取最大关键节点并将其插入到T'中，否则从右子树中获取最小关键节点T 的子树并将其插入到 T' 中。这是为了确保红黑树至少在某种程度上是平衡的。插入将是任何标准 RB 插入。
获得 min/max 的复杂度为 O(h)，并且由于需要对 T 中的每个节点重复此操作，因此这会变得非常高。我也可以在左子树的最大节点和右子树的最小节点保留一个指针，这样就解决了每次遍历树的整个高度的问题。
您如何看待这个解决方案？我很确定它可以做得更好。抱歉，如果有明显更好的解决方案，但我在互联网上找不到答案，而且这只是我在大学的第二个学期，我没有太多编程经验。
除非你有一些其他的约束或信息，否则最快的方法是忘记原始 BST 的形状。
只需将键放在一个有序列表中，然后从中构建一个完整的二叉树，所有这些都在 O(N) 时间内完成。
然后，如果有部分填充的叶级别，则将这些节点涂成红色。其余为黑色。
我必须为我的大学课程创建并描述一种算法，该算法获取 BST 树 T 并创建满足属性（并且尽可能快）的新 BST 树 T'：
1) T' 与 T
具有完全相同的键值
2) T' 是红黑树
到目前为止我只有一个想法：随机化0或1。如果为0，则从T的左子树中获取最大关键节点并将其插入到T'中，否则从右子树中获取最小关键节点T 的子树并将其插入到 T' 中。这是为了确保红黑树至少在某种程度上是平衡的。插入将是任何标准 RB 插入。
获得 min/max 的复杂度为 O(h)，并且由于需要对 T 中的每个节点重复此操作，因此这会变得非常高。我也可以在左子树的最大节点和右子树的最小节点保留一个指针，这样就解决了每次遍历树的整个高度的问题。
您如何看待这个解决方案？我很确定它可以做得更好。抱歉，如果有明显更好的解决方案，但我在互联网上找不到答案，而且这只是我在大学的第二个学期，我没有太多编程经验。
除非你有一些其他的约束或信息，否则最快的方法是忘记原始 BST 的形状。
只需将键放在一个有序列表中，然后从中构建一个完整的二叉树，所有这些都在 O(N) 时间内完成。
然后，如果有部分填充的叶级别，则将这些节点涂成红色。其余为黑色。