c++ - AVL 树永远不会有不均衡的平衡 C++

Question

所以我正在制作一个自平衡的 AVL 树，我正在实现它，就像我看到许多其他 AVL 树的实现一样，但是当我去平衡树时，我的函数返回树是平衡的当它显然不是。

这是我的 AVLTree 类:

#include "AVLTree.h"
#include "Node.h"
#include <iostream>

using namespace std;

AVLTree::AVLTree(void)
{
  root = nullptr;
}

Node* AVLTree::GetRoot()
{
  return root;
}

Node* AVLTree::RotateLeft(Node *root)
{
  Node *temp = root;
  root = temp->GetRight();
  temp->SetRight(root->GetLeft());
  root->SetLeft(temp);
  return root;
}

Node* AVLTree::RotateRight(Node *root)
{
  Node *temp = root;
  root = temp->GetLeft();
  temp->SetLeft(root->GetRight());
  root->SetLeft(temp);
  return root;
}

Node* AVLTree::DoubleRight(Node *root)
{
  RotateLeft(root->GetLeft());
  RotateRight(root);
  return root;
}

Node* AVLTree::DoubleLeft(Node *root)
{
  RotateRight(root->GetRight());
  RotateLeft(root);
  return root;
}

void AVLTree::Add(int value, Node *r)
{
  Node *node;
  if (r == nullptr)
    node = root;
  if (root == nullptr)
  {
    root = new Node(value);
    return;
  }

  if (value < node->GetValue())
  {
    if (node->GetLeft() == nullptr)
    {
      node->SetLeft(new Node(value));
      node = MakeBalance(node);
    }
    else
    {
      Add(value, node->GetLeft());
      node = MakeBalance(node);
    }
  }

  else if (node->GetRight() == nullptr)
  {
    node->SetRight(new Node(value));
    node = MakeBalance(node);
  }

  else
  {
    Add(value, node->GetRight());
    node = MakeBalance(node);
  }
}

void AVLTree::Traverse(Node *node)
{
  cout << node->GetValue() << ", ";
  if (node->GetLeft() != nullptr)
    Traverse(node->GetLeft());
  if (node->GetRight() != nullptr)
    Traverse(node->GetRight());
}

int AVLTree::CheckHeight(Node *node)
{
  int height = 0;
  if (node != nullptr)
  {
    int left = CheckHeight(node->GetLeft());
    int right = CheckHeight(node->GetRight());
    height = max(left, right) + 1;
  }
  return height;
}

int AVLTree::GetDifference(Node *node)
{
  int left = CheckHeight(node);
  int right = CheckHeight(node);
  int balance = left - right;
  return balance;
}

Node* AVLTree::MakeBalance(Node *node)
{
  int balance = GetDifference(node);
  if (balance > 1)
  {
    if (GetDifference(node->GetLeft()) > 0)
      node = RotateLeft(node);
    else
      node = DoubleLeft(node);
  }
  else if (balance < -1)
  {
    if (GetDifference(node->GetRight()) > 0)
      node = DoubleRight(node);
    else
      node = RotateRight(node);
  }
  return node;
}

我已经遍历了几次，在我添加 3、5 和 10 使树的右平衡为 2 之后，它一直返回左平衡为 2，右平衡为 2。

Answer 1

这部分让我印象深刻:

int AVLTree::GetDifference(Node *node)
{
    int left = CheckHeight(node);
    int right = CheckHeight(node);
    int balance = left - right;
    return balance;
}

这将始终导致 left == right，因此 left - right == 0。

你忘了传递 children :

// You might want this too: if (!node) return 0;
int left = CheckHeight(node->GetLeft());
int right = CheckHeight(node->GetRight());
int balance = left - right;
return balance;