AVL

#include <iostream>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

/*
// Definicja typu wêz³ów drzewa AVL
//---------------------------------
struct AVLNode
{
  AVLNode * up, * left, * right;
  int bf;
  string key;
};
*/

struct Key
{
    string surname, name, adress;
    vector<string> phone;
};

bool operator < (const Key &lhs, const Key &rhs)
{
    if(lhs.surname < rhs.surname) return true;
    else if(lhs.surname == rhs.surname && lhs.name < rhs.name ) return true;
    else if(lhs.surname == rhs.surname && lhs.name == rhs.name && lhs.adress < rhs.adress) return true;
    else false;
}
bool operator != (const Key &lhs, const Key &rhs)
{
    if(lhs.surname != rhs.surname) return true;
    return false;
}

std::ostream & operator <<( std::ostream & s, const Key & key )
{
    return s << key.surname << '.' << key.name << '.' << key.adress;
}
/*Struktura która przechowuje dane książki telefonicznej*/
struct AVL
{
    AVL *up, *left, *right;
    int bf;
    Key key;
};


string cr,cl,cp;      // łańcuchy do znaków ramek

/* Procedura wypisuje drzewo */
void printBT(string sp, string sn, AVL *v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr) s[s.length() - 2] = ' ';
    printBT(s + cp, cr, v->right);

    s = s.substr(0,sp.length()-2);
    cout << s << sn << v->key << ":" << v->bf << endl;

    s = sp;
    if(sn == cl) s[s.length() - 2] = ' ';
    printBT(s + cp, cl, v->left);
  }
}

 /*Procedura do usuwania drzewa*/
void DFSRelease(AVL * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam wêze³
  }
}

/* Rotacja RR */
void RR(AVL *&root, AVL *A)
{
  AVL *B = A->right, *p=A->up;

  A->right = B->left;
  if(A->right) A->right->up = A;

  B->left = A;
  B->up = p;
  A->up = B;

  if(p)
  {
    if(p->left == A) p->left = B; else p->right = B;
  }
  else root = B;

  if(B->bf == -1) A->bf = B->bf = 0;
  else
  {
    A->bf = -1; B->bf = 1;
  }
}

vector <Key> Read(char *nazwa)
{
    fstream file;
    vector<Key> key;
    file.open(nazwa, std::ios::in | std::ios::out );
        if( file.good() == true )
        {

        while( !file.eof() )
        {
            Key tmp;
            file>>tmp.surname;
            file>>tmp.name;
            file>>tmp.adress;
            int qty;
            file>>qty;
            for(qty; qty > 0; qty --)
            {
                string number;
                file>>number;
                tmp.phone.push_back(number);
            }
            key.push_back(tmp);
        }
        file.close();
        }
        else printf("Nie udalo sie otworzyc pliku\n");
        return key;
}

/* Rotacja LL */
void LL(AVL *&root, AVL *A)
{
  AVL *B = A->left, *p = A->up;

  A->left = B->right;
  if(A->left) A->left->up = A;

  B->right = A;
  B->up = p;
  A->up = B;

  if(p)
  {
    if(p->left == A) p->left = B; else p->right = B;
  }
  else root = B;

  if(B->bf == 1) A->bf = B->bf = 0;
  else
  {
    A->bf = 1; B->bf = -1;
  }
}

/* Rotacja RL */
void RL(AVL *& root, AVL *A)
{
  AVL *B = A->right, *C = B->left, *p = A->up;

  B->left = C->right;
  if(B->left) B->left->up = B;

  A->right = C->left;
  if(A->right) A->right->up = A;

  C->left = A;
  C->right = B;
  A->up = B->up = C;
  C->up = p;

  if(p)
  {
    if(p->left == A) p->left = C; else p->right = C;
  }
  else root = C;

  if(C->bf == -1) A->bf =  1; else A->bf = 0;
  if(C->bf ==  1) B->bf = -1; else B->bf = 0;

  C->bf = 0;
}

/* Rotacja LR */
void LR(AVL *&root, AVL *A)
{
  AVL *B = A->left, *C = B->right, *p = A->up;

  B->right = C->left;
  if(B->right) B->right->up = B;

  A->left = C->right;
  if(A->left) A->left->up = A;

  C->right = A;
  C->left = B;
  A->up = B->up = C;
  C->up = p;

  if(p)
  {
    if(p->left == A) p->left = C; else p->right = C;
  }
  else root = C;

  if(C->bf ==  1) A->bf = -1; else A->bf = 0;
  if(C->bf == -1) B->bf =  1; else B->bf = 0;

  C->bf = 0;
}

/* Wstawianie */
void insertAVL(AVL *& root, Key k)
{
  AVL * w,* p,* r;
  bool t;

  w = new AVL;        // tworzymy dynamicznie nowy wezel
  w->left = w->right = w->up = NULL;
  w->key  = k;
  w->bf  = 0;

  p = root;              // rozpoczynamy od korzenia

  if(!p) root = w;       // jeœli drzewo jest puste, to wêze³ w umieszczamy w korzeniu
  else
  {                      // inaczej szukamy miejsce dla w
    while(true)
      if(k < p->key)     // porównujemy klucze
      {
        if(!p->left)     // jeœli p nie posiada lewego syna, to
        {
          p->left = w;   // lewym synem p staje siê wêze³ w
          break;         // wychodzimy z pêtli
        }
        p = p->left;     // inaczej przechodzimy do lewego syna
      }
      else
      {
        if(!p->right)    // jeœli p nie posiada prawego syna, to
        {
          p->right = w;  // prawym synem staje siê wêze³ w
          break;         // wychodzimy z pêtli
        }
        p = p->right;    // inaczej przechodzimy do prawego syna
      }

    w->up = p;           // ojcem w jest p

    //---------------------------------
    // FAZA 2 - równowazenie drzewa AVL
    //---------------------------------

    if(p->bf) p->bf = 0; // UWAGA NR 1
    else
    {
      if(p->left == w)   // UWAGA NR 2
        p->bf = 1;
      else
        p->bf = -1;

      r = p->up;        // bêdziemy szli w górê drzewa w kierunku korzenia
                        // r i p wskazuj¹ ojca i syna na tej œcie¿ce
      t = false;
      while(r)
      {
        if(r->bf)
        {
          t = true;     // ustalamy wynik pêtli
          break;        // przerywamy pêtlê
        };
                        // inaczej modyfikujemy r.bf
        if(r->left == p) r->bf =  1;
        else             r->bf = -1;

        p = r;          // przechodzimy w górê na wy¿szy poziom
        r = r->up;
      }

      if(t)             // jeœli r.bf = +/- 1, to musimy
      {                 // równowa¿yæ drzewo
        if(r->bf == 1)
        {
          if(r->right == p) r->bf = 0;  // ga³êzie siê równowa¿¹
          else if(p->bf == -1) LR(root,r);
          else                 LL(root,r);
        }
        else
        {              // r.bf = -1
          if(r->left == p) r->bf = 0;  // ga³êzie siê równowa¿¹
          else if(p->bf == 1) RL(root,r);
          else                RR(root,r);
        }
      }
    }
  }
}

// Funkcja znajduje poprzednik wêz³a p
//------------------------------------
AVL * predAVL(AVL *p)
{
  AVL *r;

  if(p)
  {
    if(p->left)
    {
      p = p->left;
      while(p->right) p = p->right;
    }
    else
      do
      {
        r = p;
        p = p->up;
      } while(p && p->right != r);
  }
  return p;
}

// Funkcja szuka w drzewie AVL wêz³a o zadanym kluczu.
// Jeœli go znajdzie, zwraca jego wskazanie. Je¿eli nie,
// to zwraca wskazanie puste.
// Parametrami s¹:
// p - wskazanie korzenia drzewa AVL
// k - klucz poszukiwanego wêz³a
//----------------------------------------------------
AVL *findAVL(AVL *p, Key k)
{
  while(p && p->key != k)
    p = (k < p->key) ? p->left: p->right;

  return p;
}

// Funkcja usuwa rekurencyjnie wêze³ x
// root - referencja do zmiennej z adresem korzenia
// x - wskazanie usuwanego wêz³a
//-------------------------------------------------
AVL * removeAVL(AVL *& root, AVL *x)
{
  AVL  *t,*y,*z;
  bool nest;

  if(x->left && x->right)
  {
    y    = removeAVL(root,predAVL(x));
    nest = false;
  }
  else
  {
    if(x->left)
    {
      y = x->left; x->left = NULL;
    }
    else
    {
      y = x->right; x->right = NULL;
    }
    x->bf = 0;
    nest  = true;
  }

  if(y)
  {
    y->up    = x->up;
    y->left  = x->left;  if(y->left)  y->left->up  = y;
    y->right = x->right; if(y->right)  y->right->up = y;
    y->bf    = x->bf;
  }

  if(x->up)
  {
    if(x->up->left == x) x->up->left = y; else x->up->right = y;
  }
  else root = y;

  if(nest)
  {
    z = y;
    y = x->up;
    while(y)
    {
      if(!y->bf)
      {              // Przypadek nr 1
        if(y->left == z)  y->bf = -1; else y->bf = 1;
        break;
      }
      else
      {
        if(((y->bf == 1) && (y->left == z)) || ((y->bf == -1) && (y->right == z)))
        {           // Przypadek nr 2
          y->bf = 0;
          z = y; y = y->up;
        }
        else
        {
          if(y->left == z)  t = y->right; else t = y->left;
          if(!t->bf)
          {         // Przypadek 3A
            if(y->bf == 1) LL(root,y); else RR(root,y);
            break;
          }
          else if(y->bf == t->bf)
          {         // Przypadek 3B
            if(y->bf == 1) LL(root,y); else RR(root,y);
            z = t; y = t->up;
          }
          else
          {         // Przypadek 3C
            if(y->bf == 1) LR(root,y); else RL(root,y);
            z = y->up; y = z->up;
          }
        }
      }
    }
  }
  return x;
}

int main()
{

  AVL * root = NULL;


  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

vector<Key> keys;
keys=Read("dane.txt");

for (int i = 0; i < keys.size(); i++)
{
insertAVL(root, keys[i]);
}


printBT("","",root);      // Wyświetlamy zawartość drzewa AVL


  return 0;
}