如何实现将AVL树着色为黑节点数量最大化的红黑树的算法？

如何实现一种将AVL树着色为红黑树，同时使黑节点数量最大化（或红节点数量最小化）的算法？

我在作业中遇到了将AVL树节点着色以生成有效红黑树的问题，这引发了我的思考：当尝试编写相关算法时，我希望让尽可能多的节点被着色为黑色（例如，对于完美二叉搜索树，所有节点都设为黑色），而现有简单解法生成的红黑树黑深度通常最小或接近最小（例如，完美二叉搜索树的层会红黑交替）。让最多节点为黑色的问题难度更高，我写出了一个类Java语言的部分解决方案，但它并不正确。

// 辅助方法，递归为节点的两个子节点着色；colorAVLChildren的调用本身不计入递归深度，
// 只有其内部调用colorAVL的操作才会增加递归深度。
void colorAVLChildren(Node root) {
    if (root != nil) {
        colorAVL(root.left);
        colorAVL(root.right);
    }
}

void colorAVL(Node root) {
    if (root == nil) {
        return;
    }

    root.color = BLACK;

    // 所有空节点默认已为黑色，因此无论条件判断结果如何，对树的着色效果整体一致。
    if (root.left != nil) {
        root.left.color = BLACK;
    }
    if (root.right != nil) {
        root.right.color = BLACK;
    }

    if (root.isBalanced()) {
        colorAVLChildren(root.left);
        colorAVLChildren(root.right);
    } else {
        if (root.tallestChild().tallestChild() == nil) {
            root.tallestChild().color = RED;

            return;
        }

        // 至少最高子节点的较高子节点对于下一层递归来说过高（即会比该层级的其他树更高，
        // 从而违反不变式）；但它的黑深度是符合要求的。因此，必须将其设为红色，
        // 使其子节点的黑深度符合要求，但不能将其作为参数传入colorAVL。
        root.tallestChild().tallestChild().color = RED;

        // 若root.tallestChild().tallestChild()不平衡，此部分逻辑有误
        colorAVLChildren(root.tallestChild().tallestChild());

        // 若最高子节点是平衡的，则对其两个子节点做相同处理；否则，不在当前递归层级为
        // 其较矮子节点着色，留到下一层级处理，以保持树高与递归层级的一一对应关系。
        if (root.tallestChild().isBalanced()) {
            root.tallestChild().shortestChild().color = RED;
            // 若root.tallestChild().shortestChild()不平衡，此部分逻辑有误
            colorAVLChildren(root.tallestChild().shortestChild());
        } else {
            colorAVL(root.tallestChild().shortestChild());
        }

        // 下一层递归的层级对应两个子节点中较矮子节点的层级（这是两个子节点都确保拥有的唯一层级）；
        // 因此，必须在下一层递归中为这个较矮子节点着色。
        colorAVL(root.shortestChild());
    }
}

内容的提问来源于stack exchange，提问作者Morgan H