c++ - 当我使用 1000 个键值的数据集时出现分段错误，并且由于某种原因，AVL 旋转不会发生在节点周围

Question

#include "BST.h"
#include "AVL.h"
#include <iostream>

AVLTree::AVLTree() {

}

int AVLTree::max(int a, int b) {
  return (a > b)? a : b;
}

int AVLTree::height(std::shared_ptr<BSTNode>N) const {
  if (N == nullptr){
    return 0;
  }
  return N->height_;
}

void AVLTree::fixHeight(std::shared_ptr<BSTNode>& N) {
  auto h1 = height(N->left_);
  auto h2 = height(N->right_);
  N->height_ = (h1 > h2 ? h1 : h2) + 1;
}



int AVLTree::getBalance(std::shared_ptr<BSTNode> N) {
  if (N == nullptr)
    return 0;
  return height(N->left_) - height(N->right_);
}

std::shared_ptr<BSTNode> AVLTree::rightRotate(std::shared_ptr<BSTNode>n){

  std::shared_ptr<BSTNode>x = n->left_;
  std::shared_ptr<BSTNode>T2 = x->right_;
  std::weak_ptr<BSTNode>tempParent = n->parent_;
  // Perform rotation
  x->right_ = n;
  n->left_ = T2;

  // Update heights
  n->height_ = max(height(n->left_), height(n->right_)) + 1;
  x->height_ = max(height(x->left_), height(x->right_)) + 1;

  tempParent = x;
  // Return new root
  return x;

}
std::shared_ptr<BSTNode> AVLTree::leftRotate(std::shared_ptr<BSTNode>n){

  std::shared_ptr<BSTNode>y = n->right_;
  std::shared_ptr<BSTNode>T2 = y->left_;
  std::weak_ptr<BSTNode>tempParent = n->parent_;

  // Perform rotation
  y->left_ = n;
  n->right_ = T2;

  // Update heights
  n->height_ = max(height(n->left_), height(n->right_)) + 1;
  y->height_ = max(height(y->left_), height(y->right_)) + 1;

  tempParent = y;

  // Return new root
  return y;
}

void AVLTree::balance(std::shared_ptr<BSTNode> N) {
  if(N != root_){
    if(getBalance(N) >= -1 && getBalance(N) <= 1){
      if(N != root_){
        balance(N->parent_.lock());
      }
    }
    if(getBalance(N) == 2){
      if(N->key_ < N->left_->key_){
        rightRotate(N);
      }
      if(N->key_ < N->left_->key_){
        N->left_ = leftRotate(N->left_);
        rightRotate(N);
      }
    }
    if(getBalance(N) == -2){
      if(N->key_ > N->right_->key_){
        leftRotate(N);
      }
      if(N->key_ < N->right_->key_){
        N->right_ = rightRotate(N->right_);
        leftRotate(N);
      }
    }
  }
  N->height_= max( height( N->left_ ), height( N->right_ ) ) + 1;
}

void AVLTree::AVLInsert(int key) {
  std::shared_ptr<BSTNode>lastNode;
  lastNode = BST::Insert(key);

  balance(lastNode);
}

所以我应该实现一个带有 JSON 文件输入的 AVL 树。因此，出于这个原因，我创建了一个 AVLTree 类。这个类的问题是，当我使用 1000 的数据集时，它不起作用，但它适用于 10 的数据集。我的 AVL 旋转似乎也不起作用，因此树永远不会平衡在根周围，但除此之外，它工作得很好。

The BST::Insert(key)返回最后一个节点，也就是刚刚插入的节点。

我使用智能指针指向每个值并在 BST 中移动它们。我的 BST 类使用智能指针，所以如果有人可以帮助我使用智能指针，我会很高兴。

是的，这是一项任务，但这只是我无法弄清楚的一个小错误。

BSTNode::BSTNode(int key) :
    key_(key),
    parent_(std::weak_ptr<BSTNode>()),
    left_(nullptr),
    right_(nullptr) {}

BSTNode::BSTNode(int key, std::weak_ptr<BSTNode> parent) :
    key_(key),
    parent_(parent),
    left_(nullptr),
    right_(nullptr) {}

bool BSTNode::IsLeaf() const {
    return left_ == nullptr && right_ == nullptr;
}

bool BSTNode::HasLeftChild() const {
    return left_ != nullptr;
}

bool BSTNode::HasRightChild() const {
    return right_ != nullptr;
}

void BSTNode::DeleteChild(std::shared_ptr<BSTNode> v) {
    if (left_ == v) {
        left_ = nullptr;
    } else if (right_ == v) {
        right_ = nullptr;
    } else {
        std::cerr << "BSTNode::DeleteChild Error: non-child passed as argument\n";
        exit(EXIT_FAILURE);
    }
}

void BSTNode::ReplaceChild(std::shared_ptr<BSTNode> v, std::shared_ptr<BSTNode> u) {
    if (left_ == u || right_ == u) {
        std::cerr << "BSTNode::ReplaceChild Error: child passed as replacement\n";
    }
    if (left_ == v) {
        left_ = u;
        u->parent_ = v->parent_;
    } else if (right_ == v) {
        right_ = u;
        u->parent_ = v->parent_;
    } else {
        std::cerr << "BSTNode::ReplaceChild Error: non-child passed as argument\n";
        exit(EXIT_FAILURE);
    }
}
int BSTNode::height() {
    if (this == nullptr){
      return -1;
    }
    return this->height_;
}
int BSTNode::balanceFactor() {
  if (this == nullptr){
    return 0;
  }
  return this->right_->height() - this->left_->height();
}

BST::BST() : root_(nullptr), size_(0) {}

std::shared_ptr<BSTNode> BST::Insert(int key) {
    if (root_ == nullptr) {
        root_ = std::make_shared<BSTNode>(key);
        size_++;
        return root_;
    }
    std::shared_ptr<BSTNode> currentNode = root_, lastNode = nullptr;
    while (currentNode != nullptr) {
        lastNode = currentNode;
      if (key < currentNode->key_) {
        currentNode = currentNode->left_;
      } else {
        currentNode = currentNode->right_;
      }
    }
    if (key < lastNode->key_) {
        lastNode->left_ = std::make_shared<BSTNode>(key, lastNode);
    } else {
        lastNode->right_ = std::make_shared<BSTNode>(key, lastNode);
    }
    size_++;
    return lastNode;
}

bool BST::Delete(int key) {
    std::shared_ptr<BSTNode> currentNode = root_;
    while (currentNode != nullptr) {
        if (currentNode->key_ == key) {
            if (currentNode->IsLeaf()) {
                DeleteLeaf(currentNode);
            } else if (currentNode->left_ == nullptr) {
                assert(currentNode->right_ != nullptr);
                std::shared_ptr<BSTNode> parent = currentNode->parent_.lock();
                parent->ReplaceChild(currentNode, currentNode->right_);
                size_--; assert(size_ >= 0);
            } else if (currentNode->right_ == nullptr) {
                assert(currentNode->left_ != nullptr);
                std::shared_ptr<BSTNode> parent = currentNode->parent_.lock();
                parent->ReplaceChild(currentNode, currentNode->left_);
                size_--; assert(size_ >= 0);
            } else {
                currentNode->key_ = DeleteMin(currentNode);
            }
        }
        currentNode = (key < currentNode->key_) ?
            currentNode->left_ : currentNode->right_;
    }
    return false;
}

int BST::DeleteMin() {
    return DeleteMin(root_);
}


void BST::DeleteLeaf(std::shared_ptr<BSTNode> currentNode) {
    std::shared_ptr<BSTNode> parent = currentNode->parent_.lock();
    if (parent == nullptr) {
        // Delete root
        root_ = nullptr;
        size_--; assert(size_ == 0);
    } else {
        if (parent->right_ == currentNode) {
            parent->right_ = nullptr;
        } else if (parent->left_ == currentNode) {
            parent->left_ = nullptr;
        } else {
            std::cerr << "BST::DeleteLeaf Error: inconsistent state\n";
        }
        size_--; assert(size_ >= 0);
    }

}

int BST::DeleteMin(std::shared_ptr<BSTNode> currentNode) {
    std::shared_ptr<BSTNode> lastNode = nullptr;
    while (currentNode != nullptr) {
        lastNode = currentNode;
        currentNode = currentNode->left_;
    }
    int result = lastNode->key_;
    std::shared_ptr<BSTNode> parent = lastNode->parent_.lock();
    if (parent == nullptr) {
        // lastNode is root
        if (lastNode->right_ != nullptr) {
            root_ = lastNode->right_;
            lastNode->right_->parent_.reset();
        } else {
            root_ = nullptr;
        }
    } else {
        // lastNode under the root
        if (lastNode->right_ != nullptr) {
            parent->left_ = lastNode->right_;
            lastNode->right_->parent_ = parent;
        } else {
            parent->left_ = nullptr;
        }
  }
    size_--; assert(size_ >= 0);
    return result;
}

size_t BST::size() const {
    return size_;
}

bool BST::empty() const {
    return size_ == 0;
}

bool BST::Find(int key) const {
    std::shared_ptr<BSTNode> currentNode = root_;
    while (currentNode != nullptr) {
        if (currentNode->key_ == key) {
            return true;
        }
        currentNode = (key < currentNode->key_) ?
            currentNode->left_ : currentNode->right_;
    }
    return false;
}

std::string BST::JSON() const {
  nlohmann::json result;
  std::queue< std::shared_ptr<BSTNode> > nodes;
  if (root_ != nullptr) {
    result["root"] = root_->key_;
    nodes.push(root_);
    while (!nodes.empty()) {
      auto v = nodes.front();
      nodes.pop();
      std::string key = std::to_string(v->key_);
      if (v->left_ != nullptr) {
        result[key]["left"] = v->left_->key_;
        nodes.push(v->left_);
      }
      if (v->right_ != nullptr) {
        result[key]["right"] = v->right_->key_;
        nodes.push(v->right_);
      }
      if (v->parent_.lock() != nullptr) {
        result[key]["parent"] = v->parent_.lock()->key_;
      } else {
        result[key]["root"] = true;
      }
      result[key]["height"] = v->height();
      result[key]["balance factor"] = v->balanceFactor();
    }
  }
  result["height"] = root_->height();
  result["size"] = size_;
  return result.dump(2) + "\n";
}

这是 AVLCommands.cxx

#include <string>
#include "json.hpp"
#include <iostream>
#include <fstream>
#include "BST.h"
#include "AVL.h"



int main(int argc, char** argv) {
  std::ifstream file1;
  file1.open(argv[1]);
  nlohmann::json jsonObject;
  if (file1.is_open()) {
    file1 >> jsonObject;
  } else {
    std::cout << "Invalid Arguments";
  }

  AVLTree avl_tree;
  int numOps = jsonObject["metadata"]["numOps"];

  if(numOps == 10){
    for(int i = 0; i < numOps; i++ ){
      std::string num;
      if(i < 9){
        num = "0" + std::to_string(i+1);
      }
      else{
        num = std::to_string(i+1);
      }
      avl_tree.AVLInsert(jsonObject[num]["key"]);
    }
  }
  if(numOps == 1000){
    for(int i = 1; i <= numOps; i++ ){
      std::string num;
      if(i < 10 && i > 0){
        num = "000" + std::to_string(i);
        avl_tree.AVLInsert(jsonObject[num]["key"]);
      }
      if(i < 100 && i >= 10){
        num = "00" + std::to_string(i);
        avl_tree.AVLInsert(jsonObject[num]["key"]);
      }
      if(i < 1000 && i >= 100){
        num = "0" + std::to_string(i);
        avl_tree.AVLInsert(jsonObject[num]["key"]);
      }
      if(i == 1000){
        num = std::to_string(i);
        avl_tree.AVLInsert(jsonObject[num]["key"]);
      }
    }
  }

  std::cout << avl_tree.JSON() << "\n";
}

标签： c++jsonsegmentation-faultout-of-memoryavl-tree