我必须为我的大学课程创建和描述一个算法，该算法获得BST树T并创建新的BST树T'，以满足属性（并且尽可能快）：
1）T'具有与T相同的精确键值
2）T'是红黑树
到目前为止我've had only one idea: randomize 0 or 1. In case of 0, get the max key node from left subtree of T and insert it into T'，否则从T的右子树获取min键节点并将其插入T' . 这是为了确保红黑树至少在某种程度上是 balancer 的 . 插入将是任何标准RB插入 .
获得最小值/最大值的复杂度是O（h），并且因为需要对T中的每个节点重复这一点，所以这将变得非常高 . 我还可以将指针保留在左子树的最大节点和右子树的最小节点上，这样就可以解决每次遍历树的整个高度的问题 .
您对此解决方案有何看法？我在互联网上找到答案，也有很多编程经验 .
1 回答
除非您有其他一些约束或信息，否则最快的方法是忘记原始BST的形状 .
只需将密钥放在有序列表中，然后在O（N）时间内从中构建完整的二叉树 .
然后，如果存在部分填充的叶级别，则将这些节点着色为红色 . 其余的都是黑色的 .