0

所以我从这里（GeeksForGeeks）获取了一个插入红黑树的代码并稍微修改了它。

特别是BSTInsert功能：

  Node* BSTInsert(Node* root, Node *pt)
{  
/* If the tree is empty, return a new node */
if (root == NULL)
   return pt;

/* Otherwise, recur down the tree */
if (pt->data < root->data)
{
    root->left  = BSTInsert(root->left, pt);
    root->left->parent = root;
}
else if (pt->data > root->data)
{
    root->right = BSTInsert(root->right, pt);
    root->right->parent = root;
}

/* return the (unchanged) node pointer */
return root;
}

我认为root->left->parent = root;当我插入一个新节点时，上面的函数正在为每个节点执行。因此，我希望它只将新父节点分配给新节点，而不是执行前一个节点的行。因此我将代码修改为：

    Node* BSTInsert(Node* root, Node*& pt)
{

if (root == NULL){
    if(root->parent==NULL){

    return pt;
    
    }else{
        
            pt->parent = root->parent;
            return pt;
    }
}

if (pt->data < root->data)
{
    root->left  = BSTInsert(root->left, pt);
    
}
else if (pt->data > root->data)
{
    root->right = BSTInsert(root->right, pt);

}


return root;
}

基本上，它将新指针 pt 的父级设置为空根的父级，如果空根没有父级（主树的根），那么它将 pt 设置为根。

这是我的全部修改代码，有更多（次要）更改：

#include <iostream>
#include<queue>
using namespace std;

enum Color : bool {
    RED,BLACK
    };

struct Node
{
    int data;
    bool color;
    Node *left, *right, *parent;
    Node(int val):
        data(val),
        left(NULL),
        right(NULL),
        parent(NULL),
        color(RED)
    {}
};

struct RBTree
{

    Node *root;

    void rotateLeft(Node *&, Node *&);
    void rotateRight(Node *&, Node *&);
    void fixViolation(Node *&, Node *&);

    // Constructor
    RBTree() { root = NULL; }
    void insert(const int &n);
    void inorder();
    void levelOrder();
};

void inorderHelper(Node *y)
{
    if (y == NULL)
        return;
 
    inorderHelper(y->left);
    cout << y->data << "  ";
    inorderHelper(y->right);
}
 
/* A utility function to insert
    a new node with given key
   in BST */
Node* BSTInsert(Node* root, Node*& pt)
{
    
    if (root == NULL){
        if(root->parent==NULL){

        return pt;
        
        }else{
            
                pt->parent = root->parent;
                return pt;
        }
    }
    
    if (pt->data < root->data)
    {
        root->left  = BSTInsert(root->left, pt);
        
    }
    else if (pt->data > root->data)
    {
        root->right = BSTInsert(root->right, pt);

    }
 
    
    return root;
}
 
// Utility function to do level order traversal
void levelOrderHelper(Node *root)
{
    if (root == NULL)
        return;
 
    std::queue<Node *> q;
    q.push(root);
 
    while (!q.empty())
    {
        Node *temp = q.front();
        cout << temp->data << "  ";
        q.pop();
 
        if (temp->left != NULL)
            q.push(temp->left);
 
        if (temp->right != NULL)
            q.push(temp->right);
    }
}
 
void RBTree::rotateLeft(Node *&root, Node *&pt)
{
    Node *pt_right = pt->right;
 
    pt->right = pt_right->left;
 
    if (pt->right != NULL)
        pt->right->parent = pt;
 
    pt_right->parent = pt->parent;
 
    if (pt->parent == NULL)
        root = pt_right;
 
    else if (pt == pt->parent->left)
        pt->parent->left = pt_right;
 
    else
        pt->parent->right = pt_right;
 
    pt_right->left = pt;
    pt->parent = pt_right;
}
 
void RBTree::rotateRight(Node *&root, Node *&pt)
{
    Node *pt_left = pt->left;
 
    pt->left = pt_left->right;
 
    if (pt->left != NULL)
        pt->left->parent = pt;
 
    pt_left->parent = pt->parent;
 
    if (pt->parent == NULL)
        root = pt_left;
 
    else if (pt == pt->parent->left)
        pt->parent->left = pt_left;
 
    else
        pt->parent->right = pt_left;
 
    pt_left->right = pt;
    pt->parent = pt_left;
}
 
// This function fixes violations
// caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
    Node *parent_pt = NULL;
    Node *grand_parent_pt = NULL;
 
    while ((pt != root) && (pt->color != BLACK) &&
           (pt->parent->color == RED))
    {
 
        parent_pt = pt->parent;
        grand_parent_pt = pt->parent->parent;
 
        /*  Case : A
            Parent of pt is left child
            of Grand-parent of pt */
        if (parent_pt == grand_parent_pt->left)
        {
 
            Node *uncle_pt = grand_parent_pt->right;
 
            /* Case : 1
               The uncle of pt is also red
               Only Recoloring required */
            if (uncle_pt != NULL && uncle_pt->color ==
                                                   RED)
            {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
 
            else
            {
                /* Case : 2
                   pt is right child of its parent
                   Left-rotation required */
                if (pt == parent_pt->right)
                {
                    rotateLeft(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }
 
                /* Case : 3
                   pt is left child of its parent
                   Right-rotation required */
                rotateRight(root, grand_parent_pt);
                swap(parent_pt->color,
                           grand_parent_pt->color);
                pt = parent_pt;
            }
        }
 
        /* Case : B
           Parent of pt is right child
           of Grand-parent of pt */
        else
        {
            Node *uncle_pt = grand_parent_pt->left;
 
            /*  Case : 1
                The uncle of pt is also red
                Only Recoloring required */
            if ((uncle_pt != NULL) && (uncle_pt->color ==
                                                    RED))
            {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
            else
            {
                /* Case : 2
                   pt is left child of its parent
                   Right-rotation required */
                if (pt == parent_pt->left)
                {
                    rotateRight(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }
 
                /* Case : 3
                   pt is right child of its parent
                   Left-rotation required */
                rotateLeft(root, grand_parent_pt);
                swap(parent_pt->color,
                         grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }
 
    root->color = BLACK;
}
 
// Function to insert a new node with given data
void RBTree::insert(const int &data)
{
    Node *pt = new Node(data);
 
    // Do a normal BST insert
    root = BSTInsert(root, pt);
 
    // fix Red Black Tree violations
    fixViolation(root, pt);
}
 
// Function to do inorder and level order traversals
void RBTree::inorder()     {  inorderHelper(root);}
void RBTree::levelOrder()  {  levelOrderHelper(root); }
 
// Driver Code
int main()
{
    RBTree tree;
 
    tree.insert(7);
    tree.insert(6);
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(2);
    tree.insert(1);
 
    cout << "Inorder Traversal of Created Tree\n";
    tree.inorder();
 
    cout << "\n\nLevel Order Traversal of Created Tree\n";
    tree.levelOrder();
 
    return 0;
}

现在我的问题是，为什么它会抛出错误？我想不出我做错了什么，我在这里错过了什么吗？如果是这样，那么正确的修改方法是什么BSTInsert ，它不会引发错误，也不会一遍又一遍地重新分配父母。

4

0 回答 0