当前访客身份:游客 [ 登录 | 加入开源中国 ]

代码分享

当前位置:
代码分享 » C/C++  » 编程基础
intergret

AVL树

intergret 发布于 2012年09月27日 15时, 1评/2908阅
分享到: 
收藏 +0
1

    一棵AVL树是一棵平衡树,除了二叉查找树的性质外,还有这个性质:它的左子树和右子树 都是AVL树,且左子树和右子树的高度之差的绝对值不超过1关于二叉查找树、AVL树、红黑树的性质及实现,详见博客:http://blog.sina.com.cn/s/blog_62186b460101a2m4.html

标签: <无>

代码片段(2) [全屏查看所有代码]

1. [代码]AVL     跳至 [1] [2] [全屏预览]

#ifndef AVLTree_H
#define AVLTree_H

#include <stack>
using namespace std;

#define MAX(a,b) (a > b ? a : b)


template<typename T>
class TreeNode
{
public:
  T value; // value contained in the node
  TreeNode<T> * parent; // Pointer to the parent
  TreeNode<T> * left; // Pointer to the left child
  TreeNode<T> * right; // Pointer to the right child
  int height;

  TreeNode() // No-arg constructor
  {
    left = NULL;
    right = NULL;
    parent = NULL;
    height = 0;
  }

  TreeNode(T value) // Constructor
  {
    this->value = value;
    left = NULL;
    right = NULL;
    parent = NULL;
    height = 0;
  }
};


template < typename T >
class AVLTree
{
public:
  int treeSize;
  AVLTree();
  AVLTree(T values[],int arraySize);
  int insert(T value);
  void inOrder();
  void inOrderNorRec();
  int deleteNode(T value);
  int successor(T value);
  int predecessor(T value);
  int maxValue();
  int minValue();
  int getSize(T value);
  void output();

private:
  TreeNode<T> * treeroot;
  void LeftRotate(TreeNode<T> * target);
  void RightRotate(TreeNode<T> * target);
  void LeftRightRotate(TreeNode<T> * target);
  void RightLeftRotate(TreeNode<T> * target);
  int insert(TreeNode<T> * targetParent,TreeNode<T> * target,T value);
  void inOrder(TreeNode<T> *target);
  void inOrderNorRec(TreeNode<T> *target);
  TreeNode<T> * search(T searchvalue);
  int deleteNode(TreeNode<T> *target,T value);
  TreeNode<T> * successor(TreeNode<T> *target);
  TreeNode<T> * predecessor(TreeNode<T> *target);
  TreeNode<T> * maxValue(TreeNode<T> *target);
  TreeNode<T> * minValue(TreeNode<T> *target);
  int Height(TreeNode<T> *target);
  int getSize(TreeNode<T> *target);
  void output(TreeNode<T> *target,int totalSpaces);
};


template < typename T >
AVLTree<T>::AVLTree()
{
  treeroot = NULL;
  treeSize = 0;
}


template < typename T >
AVLTree<T>::AVLTree(T values[],int arraySize)
{
  treeroot = NULL;
  treeSize = 0;
  for(int i=0 ; i<arraySize ; i++){
    insert(treeroot,treeroot,values[i]);
  }
}


template< typename T >
void AVLTree<T>::LeftRotate(TreeNode<T> * target)
{
   TreeNode<T> *rightchild = target->right;
   target->right = rightchild->left;
   if (rightchild->left != NULL){
    rightchild->left->parent = target;
   }

   if (target->parent == NULL){
    treeroot = rightchild;
    rightchild->parent = NULL;
   }else if(target->parent->left == target){
    target->parent->left = rightchild;
    rightchild->parent = target->parent;
   }else{
    target->parent->right = rightchild;
    rightchild->parent = target->parent;
   }
   
   rightchild->left = target;
   target->parent = rightchild;

   int leftHeight = Height(target->left);
   int RightHeight = Height(target->right);
   target->height = MAX(leftHeight,RightHeight) + 1;

   leftHeight = Height(rightchild->left);
   RightHeight = Height(rightchild->right);
   rightchild->height = MAX(leftHeight,RightHeight) + 1;
}


template< typename T >
void AVLTree<T>::RightRotate(TreeNode<T> * target)
{
  {
   TreeNode<T> *leftchild = target->left;
   target->left = leftchild->right;
   if (leftchild->right != NULL){
    leftchild->left->parent = target;
   }

   if (target->parent == NULL){
    treeroot = leftchild;
    leftchild->parent = NULL;
   }else if(target->parent->left == target){
    target->parent->left = leftchild;
    leftchild->parent = target->parent;
   }else{
    target->parent->right = leftchild;
    leftchild->parent = target->parent;
   }

   leftchild->right = target;
   target->parent = leftchild;
   
   int leftHeight = Height(target->left);
   int RightHeight = Height(target->right);
   target->height = MAX(leftHeight,RightHeight) + 1;

   leftHeight = Height(leftchild->left);
   RightHeight = Height(leftchild->right);
   leftchild->height = MAX(leftHeight,RightHeight) + 1;
 }
}
 

template< typename T >
void AVLTree<T>::LeftRightRotate(TreeNode<T> * target)
{
   LeftRotate(target->left);
   RightRotate(target);
}


template< typename T >
void AVLTree<T>::RightLeftRotate(TreeNode<T> * target)
{
   RightRotate(target->right);
   LeftRotate(target);
}


template <typename T>
int AVLTree<T>::insert(T value)
{
  this->insert(treeroot,treeroot,value);
  return 0;
}


template <typename T>
int AVLTree<T>::insert(TreeNode<T> * targetParent,TreeNode<T> * target,T value)
{
  if (target == NULL){
    target = new TreeNode<T>(value);
    if (targetParent == NULL){
      this->treeroot = target;
    }else{
      target->parent = targetParent;
      if (targetParent->value > value){
        targetParent->left = target;
      }else{
        targetParent->right = target;
      }
    }
    this->treeSize++;
    return 0;
  }
  else if(target->value > value){
    this->insert(target,target->left,value);
    if(this->Height(target->left) - this->Height(target->right) >= 2){
      if(target->left->value > value){
        this->RightRotate(target);
      }
      else{
        this->LeftRightRotate(target);
      }
    }
  }
  else if(target->value < value){
    this->insert(target,target->right,value);
    if(this->Height(target->right) - this->Height(target->left) >= 2){
      if(target->right->value < value){
        this->LeftRotate(target);
      }
      else{
        this->RightLeftRotate(target);
      }
    }
  }else{
    return 1;
  }

  int leftHeight = Height(target->left);
  int RightHeight = Height(target->right);
  target->height = MAX(leftHeight,RightHeight) + 1;
  return 0;
}


template <typename T>
TreeNode<T> * AVLTree<T>::search(T searchvalue)
{
  TreeNode<T> *current = this->treeroot;
  int find =0;
  while (current != NULL && find == 0){
    if (current->value == searchvalue){
      find = 1;
    }
    else if(current->value > searchvalue){
      current = current->left;
    }else{
      current = current->right;
    }
  }

  if (find == 1){
    return current;
  }else{
    return NULL;
  }
}


template <typename T>
int AVLTree<T>::deleteNode(T value){
  TreeNode<T> *delNode = this->search(value);
  if ( delNode == NULL){
    cout << "not find " << endl;
    return 1;
  }
  this->deleteNode(this->treeroot,value);
  cout << "Node "<< value <<" has been deleted."<< endl;
  return 0;
}


template <typename T>
int AVLTree<T>::deleteNode(TreeNode<T> *target,T value){
  if(target->value > value) deleteNode(target->left,value);
  else if(target->value < value) deleteNode(target->right,value);
  else if(target->left != NULL)
  {
     target->value = this->maxValue(target->left)->value;
     deleteNode(target->left,target->value);
  }
  else if(target->right != NULL)
  {
     target->value = this->minValue(target->right)->value;
     deleteNode(target->right,target->value);
  }
  else
  {
     if(target->parent->left == target){
      target->parent->left = NULL;
     }else{
      target->parent->right = NULL;
     }
     delete target;
     this->treeSize--;
     return 0;
  }

  int leftHeight = Height(target->left);
  int RightHeight = Height(target->right);
  target->height = MAX(leftHeight,RightHeight) + 1;
  if (RightHeight - leftHeight >= 2)
  {
   if(target->right->right==NULL)
   {
    this->RightLeftRotate(target);
   }
   else
   {
    this->LeftRotate(target);
   }
  }
  else if(leftHeight - RightHeight >= 2)
  {
   if(target->left->left == NULL)
   {
    this->LeftRightRotate(target);
   }
   else
   {
    this->RightRotate(target);
   }
  }

  return 0;
}


template <typename T>
int AVLTree<T>::successor(T value)
{
  TreeNode<T> *position = this->search(value);
  if ( position == NULL){
    cout << "not find " << endl;
    return 1;
  }
  TreeNode<T> *successorNode = this->successor(position);
  if ( successorNode != NULL)
    cout << value << " \'s successor is:" << successorNode->value << endl;
  else
    cout << value << " has no successor" << endl;
  return 0;
}


template <typename T>
TreeNode<T> * AVLTree<T>::successor(TreeNode<T> *target)
{
  if ( target->right != NULL){
    return minValue(target->right);
  }
  TreeNode<T> * parentNode =target->parent;
  while ( parentNode != NULL && parentNode->right == target){
    target = parentNode;
    parentNode = parentNode->parent;
  }
  return parentNode;
}


template <typename T>
int AVLTree<T>::predecessor(T value)
{
  TreeNode<T> *position = this->search(value);
  if ( position == NULL){
    cout << "Can\'t find " << value <<" in AVL tree." <<endl;
    return 1;
  }
  TreeNode<T> *predecessorNode = this->predecessor(position);
  if ( predecessorNode != NULL)
    cout << value << " \'s predecessor is:" << predecessorNode->value << endl;
  else
    cout << value << " has no predecessor" << endl;
  return 0;
}


template <typename T>
TreeNode<T> * AVLTree<T>::predecessor(TreeNode<T> *target)
{
  if ( target->left != NULL){
    return maxValue(target->left);
  }
  TreeNode<T> * parentNode =target->parent;
  while ( parentNode != NULL && parentNode->left == target){
    target = parentNode;
    parentNode = parentNode->parent;
  }
  return parentNode;
}


template <typename T>
int AVLTree<T>::maxValue()
{
  TreeNode<T> * max = this->maxValue(treeroot);
  return max->value;
}


template <typename T>
TreeNode<T> * AVLTree<T>::maxValue(TreeNode<T> *target)
{
  while (target -> right != NULL){
    target = target -> right;
  }
  return target;
}


template <typename T>
int AVLTree<T>::minValue()
{
  TreeNode<T> * min = this->minValue(treeroot);
  return min->value;
}


template <typename T>
TreeNode<T> * AVLTree<T>::minValue(TreeNode<T> *target)
{
  while (target -> left != NULL){
    target = target -> left;
  }
  return target;
}


template <typename T>
int AVLTree<T>::getSize(T value)
{
  TreeNode<T> *target = this->search(value);
  return getSize(target);
}


template <typename T>
int AVLTree<T>::getSize(TreeNode<T> *target)
{
  if (target == NULL){
    return 0;
  }

  if (target->left == NULL && target->left == NULL){
    return 1;
  }else {
    return this->getSize(target->left) + 1 + this->getSize(target->right);
  }
}


template <typename T>
void AVLTree<T>::inOrder()
{
  inOrder(treeroot);
  cout << endl;
}


template <typename T>
void AVLTree<T>::inOrder(TreeNode<T> *target)
{
  if (target == NULL)
    return ;
  inOrder(target->left);
  cout << target->value << " ";
  inOrder(target->right);
}


template <typename T>
void AVLTree<T>::inOrderNorRec()
{
  inOrderNorRec(treeroot);
  cout << endl;
}


template <typename T>
void AVLTree<T>::inOrderNorRec(TreeNode<T> *target)
{
  stack < TreeNode<T> *> s;
  while ((target != NULL) || !s.empty())
  {
      if (target != NULL)
      {
          s.push(target);
          target = target->left;
      }
      else
      {
          target = s.top();
          cout << target->value << " ";
          s.pop();
          target = target->right;
      }
  }
}


template< typename T >
int AVLTree<T>::Height(TreeNode<T> *target)
{
  return target == NULL ? -1 : target->height;
}


template <typename T>
void AVLTree<T>::output()
{
    output(treeroot,0);
}


template <typename T>
void AVLTree<T>::output(TreeNode<T> *target,int totalSpaces)
{
    if(target != NULL)
    {
        output(target->right,totalSpaces+4);
        for(int i=0;i<totalSpaces;i++){
          cout<<' ';
        }
        if (target->parent != NULL){
          cout << target->value << "[" << target->parent->value << "]" << endl;
        }
        else{
          cout << target->value << "[ROOT]" << endl;
        }
        output(target->left,totalSpaces+4);
    }
};

#endif

2. [代码]Test     跳至 [1] [2] [全屏预览]

#include <iostream>
#include <ctime>
#include <cstdlib>
#include "AVLTree.H"
// 插入操作与BST相同,插入后从插入结点到根节点从下到上依次调整高度,该旋转的旋转

// 删除操作:首先定位要删除的节点。
// 如果该节点有左孩子,则用左子树的最大结点替换替换该节点,替换后递归删除左子树的最大结点;
// 如果该节点没有左孩子有右孩子,则用右子树的最小结点替换替换该节点,替换后递归删除右子树的最小结点;
// 如果该节点没有孩子,则删除该结点。
// 删除后从删除结点到根节点从下到上依次调整高度,该旋转的旋转

using namespace std;

int main()
{
  int NodeNum = 20;
  srand(time(0));

  // int *intArray = new int[NodeNum];
  // for ( int i = 0; i < NodeNum; i++){
  //   intArray[i] = rand() % 100;
  // }

  int intArray[] = {21,23,16,64,1,67,93,10,77,30,80,46,72,40,96,90,95,61,25,19};
  cout<<"Insert order:"<<endl;
  for ( int i = 0; i < NodeNum; i++){
    cout << intArray[i] << " ";
  }
  cout<<endl;
  cout<<endl;

  AVLTree<int> tree(intArray,20);
  // cout << "Inorder: " << endl;
  
  // for ( int i = 0; i < NodeNum; i++){
  //   tree.insert(intArray[i]);
  //   tree.output();
  //   cout<<"****************"<<endl;
  // }
  // cout << "Inorder: " << endl;
  // tree.inOrder();

  // cout << "InorderNorRec: " << endl;
  // tree.inOrderNorRec();

  // cout << "The number of nodes is " << tree.treeSize << endl;

  // cout << "The max value is " << tree.maxValue() << endl;
  // cout << "The min value is " << tree.minValue() << endl;


  // tree.successor(intArray[ rand() % NodeNum ]);
  // // tree.successor(64);
  // tree.predecessor(intArray[ rand() % NodeNum ]);

  for ( int i = 0; i < NodeNum-3; i++){
    cout << "Deleteing "<< intArray[i] <<"....."<< endl;
    tree.deleteNode(intArray[i]);tree.output();
  cout << "The number of nodes is " << tree.treeSize << endl;
  }

  // tree.deleteNode(1);
  // tree.output();
  // tree.deleteNode(10);
  // tree.output();
  // tree.deleteNode(16);
  // tree.output();
  // tree.deleteNode(77);
  // tree.output();

  return 0;
}


开源中国-程序员在线工具:Git代码托管 API文档大全(120+) JS在线编辑演示 二维码 更多»

发表评论 回到顶部 网友评论(1)

  • 1楼:习惯受重伤 发表于 2013-12-30 20:19 回复此评论
    要多加学习。。删除节点还有严重错误。。希望改进。。好好加油。。
开源从代码分享开始 分享代码
intergret的其它代码 全部(35)...