AVLTree.h

Go to the documentation of this file.

#ifndef AVLTREE_H
#define AVLTREE_H
#include <sys/types.h>
#include <List.h>
#include <new>
template <class Key, class Data> class AVLTree;

template <class Key, class Data>
class AVLNode
{
  public:
    AVLNode(Key key, Data data, int8_t balance = 0, AVLNode *parent = NULL, AVLNode *left = NULL, AVLNode *right = NULL);
    ~AVLNode();
    void getTree(List<Data> &list);
    AVLNode<Key, Data>* getLastInOrder();
    AVLNode<Key, Data>* getFirstInOrder();
    AVLNode<Key, Data>* getNextInOrder();
    AVLNode<Key, Data>* getPrevInOrder();
    bool isLeftChild();
    bool isRightChild();
    bool LR();
    bool RR();
    bool dLR();
    bool dRR();
    AVLNode<Key, Data> *getRoot();
    unsigned int depth();
    void print();
    AVLNode *left;
    AVLNode *right;
    AVLNode *parent;
    Key key;
    Data data;
    int8_t balance;
  private:
    AVLNode<Key, Data>* getInsertPosition(Key key);
    bool resturctureInsert();
    bool resturctureDelete();
    friend class AVLTree<Key, Data>;
};

template <class Key, class Data>
AVLNode<Key, Data>* AVLNode<Key, Data>::getLastInOrder()
{
  AVLNode<Key, Data> *item = this;
  while(item->right)item = item->right;
  return item;
}

template <class Key, class Data>
AVLNode<Key, Data>* AVLNode<Key, Data>::getFirstInOrder()
{
  AVLNode<Key, Data> *item = this;
  while(item->left)item = item->left;
  return item;

}

template <class Key, class Data>
AVLNode<Key, Data>* AVLNode<Key, Data>::getNextInOrder()
{
  if(right)
  {
    return right->getFirstInOrder();
  }
  if(isLeftChild())return parent;
  AVLNode<Key, Data> *item = this;
  while(item->parent)
  {
    if(item->isRightChild())
    {
      item = item->parent;
    }
    else
    {
      return item->parent;
    }
  }
  return NULL;
}

template <class Key, class Data>
AVLNode<Key, Data>* AVLNode<Key, Data>::getPrevInOrder()
{
  if(left)
  {
    return left->getLastInOrder();
  }
  if(isRightChild())return parent;
  AVLNode<Key, Data> *item = this;
  while(item->parent)
  {
    if(item->isLeftChild())
    {
      item = item->parent;
    }
    else
    {
      return item->parent;
    }
  }
  return NULL;
}

template <class Key, class Data>
void AVLNode<Key, Data>::getTree(List<Data> &list)
{
  if(left)left->getTree(list);
  list.pushDown(data);
  if(right)right->getTree(list);
}

template <class Key, class Data>
void AVLNode<Key, Data>::print()
{
  //cout<<"this="<<this<<" left="<<left<<" right="<<right<<" parent="<<parent<<" key="<<key<<" balance="<<(int)balance<<"\n";
  if(left)left->print();
  if(right)right->print();
}
template <class Key, class Data>
unsigned int AVLNode<Key, Data>::depth()
{
  unsigned int l = 0, r = 0;
  if(left)l = left->depth();
  if(right)r = right->depth();
  return (l>r?l:r) + 1;
}

template <class Key, class Data>
AVLNode<Key, Data>::AVLNode(Key key, Data data, int8_t balance, AVLNode *parent, AVLNode *left, AVLNode *right)
{
  this->key = key;
  this->data = data;
  this->balance = balance;
  this->parent = parent;
  this->left = left;
  this->right = right;
}

template <class Key, class Data>
AVLNode<Key, Data>::~AVLNode()
{
  if(left)delete left;
  if(right)delete right;
}

template <class Key, class Data>
AVLNode<Key, Data>* AVLNode<Key, Data>::getRoot()
{
  AVLNode<Key, Data> *cur = this;
  while(cur->parent)cur = cur->parent;
  return cur;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::isLeftChild()
{
  if(parent)
  {
    return parent->left == this;
  }
  return false;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::isRightChild()
{
  if(parent)
  {
    return parent->right == this;
  }
  return false;
}

template <class Key, class Data>
AVLNode<Key, Data>* AVLNode<Key, Data>::getInsertPosition(Key key)
{
  AVLNode<Key, Data> *cur = this;
  while(cur)
  {
    if(key < cur->key)
    {
      if(!cur->left)return cur;
      cur = cur->left;
    }
    else
    {
      if(key > cur->key)
      {
        if(!cur->right)return cur;
        cur = cur->right;
      }
      else
      {
        return NULL;
      }
    }
  }
  return NULL;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::LR()
{
  if(!right)return false;
  AVLNode<Key, Data>* b = right;
  if(parent)
  {
    if(isLeftChild())
      parent->left = b;
    else
      parent->right = b;
    b->parent = parent;
  }
  else
  {
    b->parent = NULL;
  }
  right = b->left;
  b->left = this;
  parent = b;
  if(right != NULL)right->parent = this;
  if(b->balance == 0)
  {
    balance = 1;
    b->balance = -1;
  }
  else
  {
    balance = 0;
    b->balance = 0;
  }
  return true;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::RR()
{  
  if(left == NULL)return false;
  AVLNode<Key, Data>* b = left;
  if (parent)
  {
    if (isLeftChild())
      parent->left = b;
    else
      parent->right = b;
    b->parent = parent;
  }
  else
  {
    b->parent = NULL;
  }
  left = b->right;
  b->right = this;
  parent = b;
  if(left != NULL)left->parent = this;
  if(b->balance == 0)
  {
    balance = -1;
    b->balance = 1;
  }
  else
  {
    balance = 0;
    b->balance = 0;
  }
  return true;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::dLR()
{  
  if(left == NULL || left->right == NULL) return false;
  AVLNode<Key, Data>* b = left;
  AVLNode<Key, Data>* c = left->right;
  if (parent)
  {
    if(isLeftChild())
      parent->left = c;
    else
      parent->right = c;
  }
  b->right = c->left;
  left = c->right;
  c->left = b;
  c->right = this;
  c->parent = parent;
  parent = c;
  b->parent = c;
  if (b->right != NULL) b->right->parent = b;
  if (left != NULL) left->parent = this;
  switch (c->balance)
  {
  case -1:
    balance = 1;
    b->balance = 0;
    break;
  case 0:
    balance = 0;
    b->balance = 0;
    break;
  case 1:
    balance = 0;
    b->balance = -1;
    break;
  }
  c->balance = 0;
  return true;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::dRR()
{  
  if(right == NULL || right->left == NULL)return false;
  AVLNode<Key, Data>* b = right;
  AVLNode<Key, Data>* c = right->left;
  if(parent)
  {
    if(isLeftChild())
      parent->left = c;
    else
      parent->right = c;
  }
  right = c->left;
  b->left = c->right;
  c->left = this;
  c->right = b;
  c->parent = parent;
  parent = c;
  b->parent = c;
  if (right != NULL) right->parent = this;
  if (b->left != NULL) b->left->parent = b;
  switch (c->balance)
  {
  case -1:
    balance = 0;
    b->balance = 1;
    break;
  case 0:
    balance = 0;
    b->balance = 0;
    break;
  case 1:
    balance = -1;
    b->balance = 0;
    break;
  }
  c->balance = 0;
  return true;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::resturctureInsert()
{
  AVLNode<Key, Data>* item = this;
  while(item->parent)
  {
    if(item->isLeftChild() && item->parent->balance == 0)
    {
      item->parent->balance = -1;
      item = item->parent;
      continue;
    }
    if(item->isRightChild() && item->parent->balance == 0)
    {
      item->parent->balance = 1;
      item = item->parent;
      continue;
    }
    if(item->isLeftChild() && item->parent->balance == 1)
    {
      item->parent->balance = 0;
      break;
    }
    if(item->isRightChild() && item->parent->balance == -1)
    {
      item->parent->balance = 0;
      break;
    }
    if(item->isLeftChild() && item->parent->balance == -1)
    {
      if(item->balance == 1)
        item->parent->dLR();
      else
        item->parent->RR();
      break;
    }
    if(item->isRightChild() && item->parent->balance == 1)
    {
      if(item->balance == -1)
        item->parent->dRR();
      else
        item->parent->LR();
      break;
    }
  }
  return true;
}

template <class Key, class Data>
bool AVLNode<Key, Data>::resturctureDelete()
{
  AVLNode<Key, Data>* item = this;
  if(item->balance == 0 && item->left == NULL) 
  {
    item->balance = 1;
    return true;
  }
  if(item->balance == 0 && item->right == NULL) 
  {
    item->balance = -1;
    return true;
  }
  if(item->balance == -1 && item->left == NULL)
  {
    item->balance = 0;
  }
  if(item->balance == 1 && item->right == NULL)
  {
    item->balance = 0;
  }
  if(item->balance == -1 && item->right == NULL)
  {
    if(item->left->balance == 1)
    {
      item->dLR();
      item = item->parent; 
    }
    else
    {
      item->RR();
      item = item->parent;
    }
    if(item->balance == 1)
      return true;
  }
  if(item->balance == 1 && item->left == NULL)
  {
    if(item->right->balance == -1)
    {
      item->dRR();
      item = item->parent;
    }
    else
    {
      item->LR();
      item = item->parent;
    }
    if(item->balance == -1)
      return true;
  }
  while(item->parent)
  {
    if(item->isLeftChild() && item->parent->balance == 0)
    {
      item->parent->balance = 1;
      break;
    }
    if(item->isRightChild() && item->parent->balance == 0)
    {
      item->parent->balance = -1;
      break;
    }
    if(item->isLeftChild() && item->parent->balance == -1)
    {
      item->parent->balance = 0;
      item = item->parent;
      continue;
    }
    if(item->isRightChild() && item->parent->balance == 1)
    {
      item->parent->balance = 0;
      item = item->parent;
      continue;
    }
    if(item->isRightChild() && item->parent->balance == -1)
    {
      if(item->parent->left->balance == 1)
      {
        item->parent->dLR();
        item = item->parent->parent;
      }
      else
      {
        item->parent->RR();
        item = item->parent->parent;
      }
      if(item->balance == 1)
        return true;
      continue;
    }
    if(item->isLeftChild() && item->parent->balance == 1)
    {
      if(item->parent->right->balance == -1)
      {
        item->parent->dRR();
        item = item->parent->parent;
      }
      else
      {
        item->parent->LR();
        item = item->parent->parent;
      }
      if(item->balance == -1)
        return true;
      continue;
    }
    break;
  }
  return true;
}

template <class Key, class Data>
class AVLTree
{
  public:
    AVLTree();
    ~AVLTree();
    void add(Key key, Data);
    AVLNode<Key, Data>* find(Key key);
    bool del(Key key);
    AVLNode<Key, Data>* getRoot(){return root;}
    void zerroRoot(){root = NULL; nodeCount = 0;}
    void clear();
    unsigned long getNodesCount(){return nodeCount;}
    void setTree(const AVLTree<Key, Data> &tree){nodeCount = tree.nodeCount; root = tree.root;}
  private:
    AVLNode<Key, Data> *root;
    unsigned long nodeCount;
};

template <class Key, class Data>
void AVLTree<Key, Data>::clear()
{
  if(root)delete root;
  root = NULL;
  nodeCount = 0;
}

template <class Key, class Data>
AVLTree<Key, Data>::AVLTree()
{
  root = NULL;
  nodeCount = 0;
}

template <class Key, class Data>
AVLTree<Key, Data>::~AVLTree()
{
  if(root)delete root;
}

template <class Key, class Data>
void AVLTree<Key, Data>::add(Key key, Data data)
{
  if(__builtin_expect(root!=NULL, 1))
  {
    AVLNode<Key, Data> *item = root->getInsertPosition(key);
    if(__builtin_expect(item != NULL, 1))
    {
      AVLNode<Key, Data> *newItem = new(std::nothrow) AVLNode<Key, Data>(key, data, 0, item);
      if(__builtin_expect(newItem != NULL, 1))
      {
        if(key < item->key)
        {
          item->left = newItem;
        }
        else
        {
          item->right = newItem;
        }
        newItem->resturctureInsert();
        root = root->getRoot();
        nodeCount++;
      }
    }
  }
  else
  {
    root = new(std::nothrow) AVLNode<Key, Data>(key, data);
    nodeCount++;
    return;
  }
}

template <class Key, class Data>
AVLNode<Key, Data>* AVLTree<Key, Data>::find(Key key)
{
  AVLNode<Key, Data> *cur = root;
  while(cur)
  {
    if(cur->key == key)return cur;
    cur = key < cur->key ? cur->left : cur->right;
  }
  return NULL;
}

template <class Key, class Data>
bool AVLTree<Key, Data>::del(Key key)
{ 
  if(!root) return false;
  AVLNode<Key, Data>* item = find(key);
  if(item == NULL) return false;
  if(item == root)
  {
    if(item->left == NULL && item->right == NULL)
    {
      delete root;
      root = NULL;
      nodeCount--;
      return true;
    }
  }
  AVLNode<Key, Data>* startitem = NULL;
  if(item->left == NULL && item->right == NULL)
  {
    if(item->isLeftChild())
      item->parent->left = NULL;
    else
      item->parent->right = NULL;
    startitem = item->parent;
    delete item;
    item = NULL;
  }
  if(item != NULL && item->left == NULL && item->right != NULL)
  {
    item->data = item->right->data;
    item->key = item->right->key;
    delete item->right;
    item->right = NULL;
    startitem = item;
  }
  if(item != NULL && item->left != NULL && item->right == NULL)
  {
    item->data = item->left->data;
    item->key = item->left->key;
    delete item->left;
    item->left = NULL;
    startitem = item;
  }
  if(item != NULL && item->left != NULL && item->right != NULL)
  {
    AVLNode<Key, Data>* y = item->left;
    while(y->right)y = y->right;
    AVLNode<Key, Data>* z = y->left;
    item->data = y->data;
    item->key = y->key;
    if(z != NULL)
    {
      y->data = z->data;
      y->key = z->key;
      y->left = NULL;
      delete z;
      startitem = y;
    }
    else
    {
      if(y->isLeftChild())
        y->parent->left = NULL;
      else
        y->parent->right = NULL;
      startitem = y->parent;
      delete y;
    }
  }
  startitem->resturctureDelete();
  while(root->parent)root = root->parent;
  nodeCount--;
  return true;
}
#endif