红黑树实现

Question

我实现了一个红黑树，然后在其中插入了1,2,3,4,5,6,7,8,9,10。但似乎我的树不平衡，因为前序遍历看起来像这样：4,2,1,3,6,5,8,7,9,10 和中序遍历：1,2,3,4,5,6,7,8,9,10。这意味着根是 4 并且树不平衡！这是我的代码。

void RedBlackTree::leftRotate(RedBlackTreeNode * x){
    RedBlackTreeNode *y = x->right; //set y
    y = x->right;
    x->right = y->left;
    if (y->left != nilLeaf)
        y->left->p = x;
    y->p = x->p;
    if (x->p == nilLeaf)
        root = y;
    else if (x == x->p->left)
        x->p->left = y;
    else x->p->right = y;
    y->left = x;
    x->p = y;
}

void RedBlackTree::rightRotate(RedBlackTreeNode * x){
    RedBlackTreeNode *y = x->left; //set y
    y = x->left;
    x->left = y->right;
    if (y->right != nilLeaf)
        y->right->p = x;
    y->p = x->p;
    if (x->p == nilLeaf)
        root = y;
    else if (x == x->p->right)
        x->p->right = y;
    else x->p->left = y;
    y->right = x;
    x->p = y;
}

void RedBlackTree::insert(const Point &newItem){
    size++;
    if (empty){
        root->key = newItem;
        empty = false;
        return;
    }

    RedBlackTreeNode * z = new RedBlackTreeNode; 
    z->key = newItem;
    z->right = z->left = z->p = nilLeaf;

    RedBlackTreeNode *y = nilLeaf;// = new RedBlackTreeNode;
    RedBlackTreeNode *x = root;// = new RedBlackTreeNode;

    while (x != nilLeaf)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->p = y;
    if (y == nilLeaf)
        root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    z->left = nilLeaf;
    z->right = nilLeaf;
    z->color = RedBlackTreeNode::Red;

    insertFixUp(z);
}

void RedBlackTree::insertFixUp(RedBlackTreeNode* z){
    while (z->p->color == RedBlackTreeNode::Red)
    {
        if (z->p == z->p->p->left)
        {
            RedBlackTreeNode* y = z->p->p->right;
            if (y->color == RedBlackTreeNode::Red)
            {
                z->p->color = RedBlackTreeNode::Black;
                y->color = RedBlackTreeNode::Black;
                z->p->p->color = RedBlackTreeNode::Red;
                z = z->p->p;
            }
            else if (z == z->p->right)
            {
                z = z->p;
                leftRotate(z);
            }
            else{
                z->p->color = RedBlackTreeNode::Black;
                z->p->p->color = RedBlackTreeNode::Red;
                rightRotate(z->p->p);
            }
        }
        else if (z->p == z->p->p->right)
        {
            RedBlackTreeNode* y = z->p->p->left;
            if (y->color == RedBlackTreeNode::Red)
            {
                z->p->color = RedBlackTreeNode::Black;
                y->color = RedBlackTreeNode::Black;
                z->p->p->color = RedBlackTreeNode::Red;
                z = z->p->p;
            }
            else if (z == z->p->left)
            {
                z = z->p;
                rightRotate(z);                             //**
            }
            else{
                z->p->color = RedBlackTreeNode::Black;
                z->p->p->color = RedBlackTreeNode::Red;
                leftRotate(z->p->p);                        //**
            }
        }
    }
    root->color = RedBlackTreeNode::Black;
}

但我很确定 insertFixUp 有问题。因为此代码对大多数示例都适用，但对于某些情况（如上面的示例），节点高度之间的差异将大于二。

编辑：如果我在其中插入一些随机数，这段代码就可以正常工作，当我在其中插入排序后的数字时就会出现问题。

Answer 1

这段代码没有任何问题。根据wikipedia:

'These constraints enforce a critical property of red–black trees: that the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that the tree is roughly height-balanced'

所以4为根没有错。尝试在您的树中插入更多数字，您会看到，根会发生变化，并且提到的属性将始终有效。

红黑树实现

RedBlack Tree Implementation

c++

algorithm

tree

data-structures