CODEWITHSUNDEEP
c++avl-tree
user3280133
user3280133

Reputation: 10679

AVL Tree never having uneven balance C++

So I'm making a self-balancing AVL Tree, and I'm implementing it just like I've seen many other AVL Trees implemented, but when I go to balance the tree, my functions return that the tree is balanced when it is obviously not.

Here is my AVLTree class:

#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;
}

I've stepped through it a few times and it keeps returning that the left balance is 2 and the right balance is 2 after I add 3, 5, and then 10 making the tree have a right balance of 2.

Upvotes: 0

Views: 101

Answers (1)

Anthony
Anthony

Reputation: 12397

This part jumps out at me:

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

This will always result in left == right and therefore left - right == 0.

You forgot to pass in the 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;

Upvotes: 2

Related Questions