Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-preview· OpenAIAi2 WildChat-4.8M (AI2)

#include <iostream> struct Node { long data; long height; Node* left; Node* right; };…

  1. User

    #include

    struct Node { long data; long height; Node* left; Node* right; };

    struct AVL { Node* top = nullptr;

    long height(Node* root) { if (root == nullptr) return 0; return root->height; }

    Node* newNode(long value) { Node* root = new Node(); root->data = value; root->left = nullptr; root->right = nullptr; root->height = 1; return(root); }

    Node* RightRotation(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; y->height = std::max(height(y->left), height(y->right)) + 1; x->height = std::max(height(x->left), height(x->right)) + 1; return x; }

    Node* LeftRotation(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; x->height = std::max(height(x->left), height(x->right)) + 1; y->height = std::max(height(y->left), height(y->right)) + 1; return y; }

    long Balance(Node* N) { if (N == nullptr) return 0; return height(N->right) - height(N->left); }

    Node* Insert(Node* root, int key) { if (root == nullptr) { Node* node = new Node; node->data = key; node->height = 1; node->left = nullptr; node->right = nullptr; return node; }

    if (key < root->data) { root->left = Insert(root->left, key); } else if (key > root->data) { root->right = Insert(root->right, key); } else { return root; }

    root->height = std::max(height(root->left), height(root->right)) + 1;

    int balance = Balance(root);

    if (balance < -1 && key < root->right->data) { return LeftRotation(root); }

    if (balance > 1 && key > root->left->data) { return RightRotation(root); }

    if (balance < -1 && key > root->right->data) { root->right = RightRotation(root->right); return LeftRotation(root); }

    if (balance > 1 && key < root->left->data) { root->left = LeftRotation(root->left); return RightRotation(root); }

    return root; }

    Node* Delete(Node* root, int key) { if (root == nullptr) return root;

    if ( key < root->data ) {
      root->left = Delete(root->left, key); 
    }else if( key > root->data ) {
        root->right = Delete(root->right, key); 
    } else { 
        if((root->left == nullptr) || (root->right == nullptr)) { 
            Node* temp = root->left ? root->left : root->right; 
    
            if (temp == nullptr) 
            { 
                temp = root; 
                root = nullptr; 
            } 
            else {
            *root = *temp; 
            }
        } else { 
            Node* temp = minValueNode(root->right); 
            root->data = temp->data; 
            root->right = Delete(root->right, temp->data); 
        } 
    } 
    
    if (root == nullptr) 
    return root; 
    
    root->height = 1 + std::max(height(root->left), height(root->right)); 
    
    int balance = Balance(root); 
    
    if (balance < -1 && 
        Balance(root->right) >= 0) 
        return LeftRotation(root); 
    
    if (balance < -1 && 
        Balance(root->right) < 0) { 
        root->right = RightRotation(root->right); 
        return LeftRotation(root); 
    } 
    
    if (balance > 1 && 
        Balance(root->left) <= 0) 
        return RightRotation(root); 
    
    if (balance > 1 && 
        Balance(root->left) > 0) { 
        root->left = LeftRotation(root->left); 
        return RightRotation(root); 
    }
    
    return root; 
    

    }

    bool Exists(Node* root, long key) { if (root == nullptr) return false; if (root->data == key) return true; else if (root->data > key) return Exists(root->left, key); else return Exists(root->right, key); }

    Node* minValueNode(Node* node) { Node* current = node; while (current->left != nullptr) current = current->left; return current; } };

    int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); char cmd; AVL tree; long n; std::cin >> n; for (long i = 0; i < n; ++i) { std::cin >> cmd; if (cmd == 'A') { long x; std::cin >> x; tree.top = tree.Insert(tree.top, x); std::cout << (tree.top == nullptr? 0 : -tree.Balance(tree.top)); if (i < n - 1) { std::cout << '\n'; } } else if (cmd == 'D') { long x; std::cin >> x; tree.top = tree.Delete(tree.top, x); std::cout << (tree.top == nullptr? 0 : -tree.Balance(tree.top)); if (i < n - 1) { std::cout << '\n'; } } else if (cmd == 'C') { long x; std::cin >> x; tree.Exists(tree.top, x) ? std::cout << 'Y' : std::cout << 'N'; if (i < n - 1) { std::cout << '\n'; } } } }

    6 A 3 0 A 4 -1 A 5 [1] 66082 segmentation fault ./main

    ошибка в insert исправь

  2. Assistant

    I've reviewed your Insert method, and I noticed that there are some incorrect rotations' conditions which can lead to an unbalanced tree or an invalid tree structure, eventually leading to a segmentation fault.

    The Insert method has the following rotations that seem incorrect:

    // No need to flip the conditions for right-heavy and left-heavy.
    
    // This seems incorrect because if the tree is left-heavy, which means balance > 1,
    // And the key to insert is greater than the key of left child of the current root,
    // We should do a Left-Right Rotation (first LeftRotation on root->left and then RightRotation on root).
    if (balance < -1 && key < root->right->data) {
      return LeftRotation(root);
    }
    
    // Similarly, if the tree is right-heavy, which means balance < -1,
    // And the key to insert is smaller than the key of right child of the current root,
    // We should do a Right-Left Rotation (first RightRotation on root->right and then LeftRotation on root).
    if (balance > 1 && key > root->left->data) {
      return RightRotation(root);
    }
    

    Let’s correct them as follows:

    // For balance > 1 and key < root->left->data, we just do a simple RightRotation
    if (balance > 1 && key < root->left->data) {
      return RightRotation(root);
    }
    
    // For balance < -1 and key > root->right->data, we just do a simple LeftRotation
    if (balance < -1 && key > root->right->data) {
      return LeftRotation(root);
    }
    
    // The next condition should be for Left-Right case:
    // balance > 1 and key > root->left->data
    if (balance > 1 && key > root->left->data) {
      root->left = LeftRotation(root->left);
      return RightRotation(root);
    }
    
    // And this one should be for Right-Left case:
    // balance < -1 and key < root->right->data
    if (balance < -1 && key < root->right->data) {
      root->right = RightRotation(root->right);
      return LeftRotation(root);
    }
    

    The correct AVL insertion rotations consider these 4 scenarios:

    1. Left-Left (LL) case: balance > 1 and key < root->left->data
    2. Right-Right (RR) case: balance < -1 and key > root->right->data
    3. Left-Right (LR) case: balance > 1 and key > root->left->data
    4. Right-Left (RL) case: balance < -1 and key < root->right->data

    The conditions must precisely handle these cases for the AVL tree algorithm to work correctly and avoid segmentation faults.

    Once you apply the proper conditions, your Insert method should work without causing a segmentation fault.

    Note that I have not fully reviewed your Delete method for similar issues, so make sure you also verify that the rotations in the Delete method follow the correct AVL deletion rotations as well.