c++ - 实现 AVL 树

Question

我正在尝试按照 here 中的指南实现 AVL 树.我在让它工作时遇到了一些问题。目前我在插入的“右右案例”中收到此错误。具体在这一行:

// Right Right Case
if (balance < -1 && theData > root->right->data)
    leftRotate(root);

我得到的错误是:

Exception thrown: read access violation.
root._Mypair._Myval2->right._Mypair._Myval2 was nullptr.

如果有人能帮我解决这个问题，我将不胜感激。

这是我的代码:

#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <stack>
#include <queue>

struct Node {
    int data;
    int height;
    std::unique_ptr<Node> left = nullptr;
    std::unique_ptr<Node> right = nullptr;

    Node(const int& x, const int& y, std::unique_ptr<Node>&& p = nullptr, std::unique_ptr<Node>&& q = nullptr) :
        data(x),
        height(y),
        left(std::move(p)),
        right(std::move(q)) {}

    Node(const int& data) : data(data), height(1) {}

};
std::unique_ptr<Node> root = nullptr;

int height(std::unique_ptr<Node>& root) {
    if (!root) return 0;
    return root->height;
}

void rightRotate(std::unique_ptr<Node>& y) {
    std::unique_ptr<Node> x = std::move(y->left);
    std::unique_ptr<Node> T2 = std::move(x->right);

    // Perform rotation
    x->right = std::move(y);
    x->right->left = std::move(T2);

    // Update heights
    x->right->height = std::max(height(x->right->left), height(x->right->right)) + 1;
    x->height = std::max(height(x->left), height(x->right)) + 1;
}

void leftRotate(std::unique_ptr<Node>& x) {
    std::unique_ptr<Node> y = std::move(x->right);
    std::unique_ptr<Node> T2 = std::move(y->left);

    // Perform rotation
    y->left = std::move(x);
    y->left->right = std::move(T2);

    // Update heights
    y->left->height = std::max(height(y->left->left), height(y->left->right)) + 1;
    y->height = std::max(height(y->left), height(y->right)) + 1;

}

int heightDiff(std::unique_ptr<Node>& root) {
    if (!root) return 0;

    return height(root->left) - height(root->right);
}

void insert(std::unique_ptr<Node>& root, const int& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    // Perform normal BST insertion
    if (root == nullptr) {
        root = std::move(newNode);
        return;
    }

    else if (theData < root->data) {
        insert(root->left, theData);
    }

    else {
        insert(root->right, theData);
    }

    // Update height of this ancestor node
    root->height = 1 + std::max(height(root->left), height(root->right));

    // Get the balance factor of this ancestor node to check whether this node became unbalanced
    int balance = heightDiff(root);

    // If this node become unbalaced, then we have 4 cases

    // Left Left Case
    if (balance > 1 && root->left && theData < root->left->data)
        rightRotate(root);

    // Right Right Case
    if (balance < -1 && root->right && theData > root->right->data)
        leftRotate(root);

    // Left Right Case
    if (balance > 1 && root->left && theData > root->left->data) {
        leftRotate(root->left);
        rightRotate(root);
    }

    // Right Left Case
    if (balance < -1 && root->right && theData < root->right->data) {
        rightRotate(root->right);
        leftRotate(root);
    }
}

auto findMin(std::unique_ptr<Node>& root) {
    while (root->left != nullptr) root = std::move(root->left);
    return root.get();
}

void deleteNode(std::unique_ptr<Node>& root, const int& theData) {
    // Step 1: Perform regular deletion for BST
    if (!root) return;
    else if (theData < root->data) deleteNode(root->left, theData);
    else if (theData > root->data) deleteNode(root->right, theData);

    else {
        // Case 1: No child
        if (root->left == nullptr && root->right == nullptr) {
            root = nullptr;
        }

        // Case 2: One child
        else if (root->left == nullptr) {
            root = std::move(root->left);
        }

        else if (root->right == nullptr) {
            root = std::move(root->right);
        }

        // Case 3: Two children
        else {
            auto temp = findMin(root->right);
            temp->data = root->data;
            deleteNode(root->right, temp->data);
        }
    }


    // Step 2: Update height of the current node
    root->height = 1 + std::max(height(root->left), height(root->right));

    // Step 3: Get the balalce factor of the this node (to 
    // check whether this node became unbalanced)
    int balance = heightDiff(root);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && heightDiff(root->left) >= 0)
        rightRotate(root);

    // Left Right Case
    if (balance > 1 && heightDiff(root->left) < 0) {
        leftRotate(root->left);
        rightRotate(root);
    }

    // Right Right Case
    if (balance < -1 && heightDiff(root->right) <= 0)
        leftRotate(root);

    // Right Left Case
    if (balance < -1 && heightDiff(root->right) > 0) {
        rightRotate(root->right);
        leftRotate(root);
    }
}

void inorderTraversal(std::unique_ptr<Node>& root) {
    if (!root) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

void preorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        std::cout << root->data << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void postorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

void DFS(std::unique_ptr<Node>& root) {
    if (!root) return;

    std::stack<Node const *> s;
    s.push(root.get());

    while (!s.empty()) {
        auto p = s.top();
        s.pop();

        if (p->right != nullptr) s.push(p->right.get());
        if (p->left != nullptr) s.push(p->left.get());

        std::cout << p->data << " ";
    }
}

void BFS(std::unique_ptr<Node>& root) {
    if (!root) return;

    std::queue<Node const *> q;
    q.push(root.get());

    while (!q.empty()) {
        auto p = q.front();
        q.pop();

        if (p->left != nullptr) q.push(p->left.get());
        if (p->right != nullptr) q.push(p->right.get());

        std::cout << p->data << " ";
    }
}

bool exists(int d) {
    auto temp = root.get();
    while (temp != nullptr) {
        if (temp->data == d) {
            return true;
        }
        else {
            if (d > temp->data) {
                temp = temp->right.get();
            }
            else {
                temp = temp->left.get();
            }
        }
    }
    return false;
}

int main() {

    //        8
    //      /    \
    //    4       10
    //   / \     /  \
    //  2   6   9    12

    //insert(root, 8);
    //insert(root, 10);
    //insert(root, 4);
    //insert(root, 2);
    //insert(root, 6);
    //insert(root, 12);
    //insert(root, 9);


  /* Constructing tree given in the above figure */
    insert(root, 9);
    insert(root, 5);
    insert(root, 10);
    insert(root, 0);
    insert(root, 6);
    insert(root, 11);
    insert(root, -1);
    insert(root, 1);
    insert(root, 2);

    /* The constructed AVL Tree would be
            9
           /  \
          1    10
        /  \     \
       0    5     11
      /    /  \
     -1   2    6
    */

    printf("Preorder traversal of the constructed AVL "
        "tree is \n");
    preorderTraversal(root);

    //deleteNode(root, 10);

    /* The AVL Tree after deletion of 10
            1
           /  \
          0    9
        /     /  \
       -1    5     11
           /  \
          2    6
    */

    //printf("\nPreorder traversal after deletion of 10 \n");
    //preorderTraversal(root);

    /*inorderTraversal(root);
    std::cout << "\n";

    preorderTraversal(root);
    std::cout << "\n";

    postorderTraversal(root);
    std::cout << "\n";

    DFS(root);
    std::cout << "\n";

    BFS(root);
    std::cout << "\n";

    exists(4) ? std::cout << "Yes" << std::endl : std::cout << "No" << std::endl;*/


    std::cin.get();
}

Answer 1

我注意到您已经修复了 std::move() 问题。但您可能需要将以下几行添加到您的程序中。

void rightRotate(std::unique_ptr<Node>& y) {
    ....
    x->height = std::max(height(x->left), height(x->right)) + 1;
    y = std::move(x);
}

void leftRotate(std::unique_ptr<Node>& x) {
    ...
    y->height = std::max(height(y->left), height(y->right)) + 1;
    x = std::move(y);
}