ALVTree.cpp

#include "AVLTree.hpp"
#include <algorithm>                                    //dla wykorzystania max
using namespace std;

int AVLTree::height(AVLNode* node) {
    if(node == nullptr) {                               //jeśli węzeł jest zerowy to i jego wysokość też
        return 0;
    }
    return node -> height;
}

int AVLTree::getBalance(AVLNode* node) {
    if(node == nullptr) {                               //jeśli węzeł jest zerowy to nie ma on left ani right
        return 0;
    }                                                   //zwracamy left - right, powinno być {-1, 0, 1}
    return height(node -> left) - height(node -> right);
}

void AVLTree::insert(int key, int value) {
  root = insert(root, key, value);
}

void AVLTree::remove(int key) {
  root = remove(root, key);
}

AVLNode* AVLTree::rotateRight(AVLNode* y) {             //rotacja Right (LL)
    AVLNode* x = y -> left;                             //y to niezbalansowany węzeł a x to jego left, bo to left przeciąża drzewo
    AVLNode* T2 = x -> right;                           //T2 to prawe poddrzewo x'a, które będziemy rotować

    x -> right = y;                                     //prawe dziecko x'a zmieniamy na y
    y -> left = T2;                                     //lewe dziecko y'ka zmieniamy na T2

    y -> height = 1 + max(height(y -> left), height(y -> right));   //nowa wysokość y'ka po zmianie, czyli największa z jego dzieci +1
    x -> height = 1 + max(height(x -> left), height(x -> right));   //nowa wysokość x'a (zależy od y'ka więc jest po nim)

    return x;

/*
           y                         x
         /   \                     /   \
        x     T3         =>      T1     y
      /   \                           /   \
    T1     T2                       T2     T3
*/

}

AVLNode* AVLTree::rotateLeft(AVLNode* x) {              //rotacja Left (RR)
    AVLNode* y = x -> right;                            //x to niezbalansowany węzeł, a y to jego right, bo tym razem right przeciąża drzewo
    AVLNode* T2 = y -> left;                            //T2 to lewe poddrzewo y'ka, które będziemy rotować

    y -> left = x;                                      //lewe dziecko y'ka zmieniamy na x'a
    x -> right = T2;                                    //prawe dziecko x'a zmieniamy na T2

    x -> height = 1 + max(height(x -> left), height(x -> right));   //nowa wysokość x'a po zmianie, czyli największa z jego dzieci +1
    y -> height = 1 + max(height(y -> left), height(y -> right));   //nowa wysokość y'ka (zależy od x'a więc jest po nim)

    return y;

/*
          x                         y
        /   \                     /   \
     T1      y         =>       x      T3
           /   \              /   \
         T2     T3          T1     T2
*/

}

AVLNode* AVLTree::rotateLeftRight(AVLNode* y) {
    y -> left = rotateLeft(y -> left);                  //y left czyli x i z, rotujemy rotate Left
    return rotateRight(y);                              //całość rotujemy right

/*
        y                                   y                               z
      /   \                               /   \                           /   \
    x      T4                           z       T4                      x       y
  /   \                     =>        /   \                 =>        /   \    /  \
T1     z                            x       T3                      T1     T2 T3    T4
     /   \                        /    \
    T2    T3                    T1      T2
*/
}

AVLNode* AVLTree::rotateRightLeft(AVLNode* x) {
    x -> right = rotateRight(x -> right);               //x right czyli y i z, rotujemy rotate right
    return rotateLeft(x);                               //całość rotujemy left

/*
        x                           x                                       z
      /   \                       /   \                                   /   \
    T1     y                    T1     z                                x       y
         /   \         =>            /   \                  =>        /   \   /   \
        z    T4                    T2      y                        T1    T2 T3    T4
      /   \                              /   \
    T2      T3                         T3      T4
*/
}

AVLNode* AVLTree::insert(AVLNode* node, int key, int value) {
  if(node == nullptr) {                                 //jeśli trafimy na miejsce gdzie jest nullptr
    return new AVLNode(key, value);                     //tworzymy i zwracamy tam nowy węzeł
  }

  if(key < node -> key) {                               //jeśli klucz jest mniejszy, idziemy w lewo
    node -> left = insert(node -> left, key, value);
  }
  else if (key > node -> key) {                         //jeśli klucz jest większy, idziemy w prawo
    node -> right = insert(node -> right, key, value);
  }
  else {
    node -> value = value;                              //zmienamy wartość value przy powtórce klucza
    return node;
  }

  node -> height = 1 + max(height(node -> left), height(node -> right));  //uaktualniamy wysokość węzła

  int balance = getBalance(node);                       //sprawdzamy jaki jest bilans balansu xpp

  if(balance > 1 && key < node -> left -> key) {        //jeśli drzewo jest przechylone LL
    return rotateRight(node);                           //rotujemy je w prawo
  }

  if(balance < -1 && key > node -> right -> key) {      //jeśli drzewo jest przechylone RR
    return rotateLeft(node);                            //rotujemy je w lewo
  }

  if(balance > 1 && key > node -> left -> key) {        //jesli drzewo jest przechylone LR
    return rotateLeftRight(node);                       //rotujemy je odpowiednio
  }

  if(balance < -1 && key < node -> right -> key) {      //jeśli drzewo jest przechylone RL
    return rotateRightLeft(node);                       //analogicznie rotujemy
  }

  return node;                                          //zwracamy węzeł
}

AVLNode* AVLTree::remove(AVLNode* node, int key) {
  if(node == nullptr) {
    return node;                                        //nie ma nic do usunięcia
  }

  if(key < node -> key) {
    node -> left = remove(node -> left, key);           //jeśli klucz jest mniejszy to idziemy w lewo
  }

  else if(key > node -> key) {
    node -> right = remove(node -> right, key);         //analogicznie w prawo
  }

  else {                                                //key == node -> key
    if(node -> left == nullptr && node -> right == nullptr) {     //mamy liść
      delete node;
      return nullptr;                                   //liść możemy swobodnie usunąć
    }

    else if(node -> left == nullptr) {                  //jeśli ma tylko prawe dziecko
      AVLNode* temp = node -> right;                    //tymczasowo je zapisujemy
      delete node;                                      //usuwamy
      return temp;                                      //zwracamy prawe dziecko
    }

    else if(node -> right == nullptr) {                 //analogicznie jak ma drugie dziecko
      AVLNode* temp = node -> left;
      delete node;
      return temp;
    }

    else {                                              //niestety ma dwa dziecka
      AVLNode* kid = minValueNode(node -> right);       //bierzemy sobie najmniejszy z większych elementów
      
      node -> key = kid -> key;                         //kopiujemy klucz dziecka
      node -> value = kid -> value;                     //kopiujemy też wartość
      node -> right = remove(node -> right, kid -> key);//dziecko usuwamy
    }
  }

  node -> height = 1 + max(height(node -> left), height(node -> right));  //liczymy nową wysokość node'a
  int balance = getBalance(node);                       //zbieramy obecny balans

  if(balance > 1 && getBalance(node -> left) >= 0) {    //na podstawie balansu rotujemy np tutaj LL
    return rotateRight(node);
  }

  if(balance < -1 && getBalance(node -> right) <= 0) {  //RR
    return rotateLeft(node);
  }

  if(balance > 1 && getBalance(node -> left) < 0) {     //LR
    return rotateLeftRight(node);
  }

  if(balance < -1 && getBalance(node -> right) > 0) {   //RL
    return rotateRightLeft(node);
  }

  return node;
}

AVLNode* AVLTree::minValueNode(AVLNode* node) {
  AVLNode* current = node;                              //tworzymy tymczasowy wyznacznik

  while(current -> left != nullptr) {                   //dopóki nie znajdziemy najmniejszej (max lewo)
    current = current -> left;                          //idziemy dalej w lewo
  }

  return current;
}