福田附近公司做网站建设哪家效益快,线上问诊网站建设,集团企业网工管理系统,长春网络营销AVL树是高度平衡的而二叉树。它的特点是#xff1a;AVL树中任何节点的两个子树的高度最大差别为1。 旋转
如果在AVL树中进行插入或删除节点后#xff0c;可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态#xff1a;LL(左左)#xff0c;LR(左右)#xff0c;RR(右…AVL树是高度平衡的而二叉树。它的特点是AVL树中任何节点的两个子树的高度最大差别为1。 旋转
如果在AVL树中进行插入或删除节点后可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态LL(左左)LR(左右)RR(右右)和RL(右左)。下面给出它们的示意图 1) LLLeftLeft也称为”左左”。插入或删除一个节点后根节点的左子树的左子树还有非空子节点导致”根的左子树的高度”比”根的右子树的高度”大2导致AVL树失去了平衡。 例如在上面LL情况中由于”根节点(8)的左子树(4)的左子树(2)还有非空子节点”而”根节点(8)的右子树(12)没有子节点”导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。
(2) LRLeftRight也称为”左右”。插入或删除一个节点后根节点的左子树的右子树还有非空子节点导致”根的左子树的高度”比”根的右子树的高度”大2导致AVL树失去了平衡。 例如在上面LR情况中由于”根节点(8)的左子树(4)的左子树(6)还有非空子节点”而”根节点(8)的右子树(12)没有子节点”导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。
(3) RLRightLeft称为”右左”。插入或删除一个节点后根节点的右子树的左子树还有非空子节点导致”根的右子树的高度”比”根的左子树的高度”大2导致AVL树失去了平衡。 例如在上面RL情况中由于”根节点(8)的右子树(12)的左子树(10)还有非空子节点”而”根节点(8)的左子树(4)没有子节点”导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。
(4) RRRightRight称为”右右”。插入或删除一个节点后根节点的右子树的右子树还有非空子节点导致”根的右子树的高度”比”根的左子树的高度”大2导致AVL树失去了平衡。 例如在上面RR情况中由于”根节点(8)的右子树(12)的右子树(14)还有非空子节点”而”根节点(8)的左子树(4)没有子节点”导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。
前面说过如果在AVL树中进行插入或删除节点后可能导致AVL树失去平衡。AVL失去平衡之后可以通过旋转使其恢复平衡下面分别介绍”LL(左左)LR(左右)RR(右右)和RL(右左)”这4种情况对应的旋转方法。
2.1 LL的旋转
LL失去平衡的情况可以通过一次旋转让AVL树恢复平衡。如下图 /** LL左左对应的情况(左单旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::leftLeftRotation(AVLTreeNodeT* k2)
{AVLTreeNodeT* k1;k1 k2-left;k2-left k1-right;k1-right k2;k2-height max( height(k2-left), height(k2-right)) 1;k1-height max( height(k1-left), k2-height) 1;return k1;
}
2.2 RR的旋转
理解了LL之后RR就相当容易理解了。RR是与LL对称的情况RR恢复平衡的旋转方法如下 /** RR右右对应的情况(右单旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::rightRightRotation(AVLTreeNodeT* k1)
{AVLTreeNodeT* k2;k2 k1-right;k1-right k2-left;k2-left k1;k1-height max( height(k1-left), height(k1-right)) 1;k2-height max( height(k2-right), k1-height) 1;return k2;
}
2.3 LR的旋转
LR失去平衡的情况需要经过两次旋转才能让AVL树恢复平衡。如下图 /** LR左右对应的情况(左双旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::leftRightRotation(AVLTreeNodeT* k3)
{k3-left rightRightRotation(k3-left);return leftLeftRotation(k3);
}
2.4 RL的旋转
RL是与LR的对称情况RL恢复平衡的旋转方法如下 /** RL右左对应的情况(右双旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::rightLeftRotation(AVLTreeNodeT* k1)
{k1-right leftLeftRotation(k1-right);return rightRightRotation(k1);
}
完整代码
#ifndef _AVL_TREE_HPP_
#define _AVL_TREE_HPP_#include iomanip
#include iostream
using namespace std;template class T
class AVLTreeNode{public:T key; // 关键字(键值)int height; // 高度AVLTreeNode *left; // 左孩子AVLTreeNode *right; // 右孩子AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r):key(value), height(0),left(l),right(r) {}
};template class T
class AVLTree {private:AVLTreeNodeT *mRoot; // 根结点public:AVLTree();~AVLTree();// 获取树的高度int height();// 获取树的高度int max(int a, int b);// 前序遍历AVL树void preOrder();// 中序遍历AVL树void inOrder();// 后序遍历AVL树void postOrder();// (递归实现)查找AVL树中键值为key的节点AVLTreeNodeT* search(T key);// (非递归实现)查找AVL树中键值为key的节点AVLTreeNodeT* iterativeSearch(T key);// 查找最小结点返回最小结点的键值。T minimum();// 查找最大结点返回最大结点的键值。T maximum();// 将结点(key为节点键值)插入到AVL树中void insert(T key);// 删除结点(key为节点键值)void remove(T key);// 销毁AVL树void destroy();// 打印AVL树void print();private:// 获取树的高度int height(AVLTreeNodeT* tree) ;// 前序遍历AVL树void preOrder(AVLTreeNodeT* tree) const;// 中序遍历AVL树void inOrder(AVLTreeNodeT* tree) const;// 后序遍历AVL树void postOrder(AVLTreeNodeT* tree) const;// (递归实现)查找AVL树x中键值为key的节点AVLTreeNodeT* search(AVLTreeNodeT* x, T key) const;// (非递归实现)查找AVL树x中键值为key的节点AVLTreeNodeT* iterativeSearch(AVLTreeNodeT* x, T key) const;// 查找最小结点返回tree为根结点的AVL树的最小结点。AVLTreeNodeT* minimum(AVLTreeNodeT* tree);// 查找最大结点返回tree为根结点的AVL树的最大结点。AVLTreeNodeT* maximum(AVLTreeNodeT* tree);// LL左左对应的情况(左单旋转)。AVLTreeNodeT* leftLeftRotation(AVLTreeNodeT* k2);// RR右右对应的情况(右单旋转)。AVLTreeNodeT* rightRightRotation(AVLTreeNodeT* k1);// LR左右对应的情况(左双旋转)。AVLTreeNodeT* leftRightRotation(AVLTreeNodeT* k3);// RL右左对应的情况(右双旋转)。AVLTreeNodeT* rightLeftRotation(AVLTreeNodeT* k1);// 将结点(z)插入到AVL树(tree)中AVLTreeNodeT* insert(AVLTreeNodeT* tree, T key);// 删除AVL树(tree)中的结点(z)并返回被删除的结点AVLTreeNodeT* remove(AVLTreeNodeT* tree, AVLTreeNodeT* z);// 销毁AVL树void destroy(AVLTreeNodeT* tree);// 打印AVL树void print(AVLTreeNodeT* tree, T key, int direction);
};/* * 构造函数*/
template class T
AVLTreeT::AVLTree():mRoot(NULL)
{
}/* * 析构函数*/
template class T
AVLTreeT::~AVLTree()
{destroy(mRoot);
}/** 获取树的高度*/
template class T
int AVLTreeT::height(AVLTreeNodeT* tree)
{if (tree ! NULL)return tree-height;return 0;
}template class T
int AVLTreeT::height()
{return height(mRoot);
}
/** 比较两个值的大小*/
template class T
int AVLTreeT::max(int a, int b)
{return ab ? a : b;
}/** 前序遍历AVL树*/
template class T
void AVLTreeT::preOrder(AVLTreeNodeT* tree) const
{if(tree ! NULL){cout tree-key ;preOrder(tree-left);preOrder(tree-right);}
}template class T
void AVLTreeT::preOrder()
{preOrder(mRoot);
}/** 中序遍历AVL树*/
template class T
void AVLTreeT::inOrder(AVLTreeNodeT* tree) const
{if(tree ! NULL){inOrder(tree-left);cout tree-key ;inOrder(tree-right);}
}template class T
void AVLTreeT::inOrder()
{inOrder(mRoot);
}/** 后序遍历AVL树*/
template class T
void AVLTreeT::postOrder(AVLTreeNodeT* tree) const
{if(tree ! NULL){postOrder(tree-left);postOrder(tree-right);cout tree-key ;}
}template class T
void AVLTreeT::postOrder()
{postOrder(mRoot);
}/** (递归实现)查找AVL树x中键值为key的节点*/
template class T
AVLTreeNodeT* AVLTreeT::search(AVLTreeNodeT* x, T key) const
{if (xNULL || x-keykey)return x;if (key x-key)return search(x-left, key);elsereturn search(x-right, key);
}template class T
AVLTreeNodeT* AVLTreeT::search(T key)
{return search(mRoot, key);
}/** (非递归实现)查找AVL树x中键值为key的节点*/
template class T
AVLTreeNodeT* AVLTreeT::iterativeSearch(AVLTreeNodeT* x, T key) const
{while ((x!NULL) (x-key!key)){if (key x-key)x x-left;elsex x-right;}return x;
}template class T
AVLTreeNodeT* AVLTreeT::iterativeSearch(T key)
{return iterativeSearch(mRoot, key);
}/* * 查找最小结点返回tree为根结点的AVL树的最小结点。*/
template class T
AVLTreeNodeT* AVLTreeT::minimum(AVLTreeNodeT* tree)
{if (tree NULL)return NULL;while(tree-left ! NULL)tree tree-left;return tree;
}template class T
T AVLTreeT::minimum()
{AVLTreeNodeT *p minimum(mRoot);if (p ! NULL)return p-key;return (T)NULL;
}/* * 查找最大结点返回tree为根结点的AVL树的最大结点。*/
template class T
AVLTreeNodeT* AVLTreeT::maximum(AVLTreeNodeT* tree)
{if (tree NULL)return NULL;while(tree-right ! NULL)tree tree-right;return tree;
}template class T
T AVLTreeT::maximum()
{AVLTreeNodeT *p maximum(mRoot);if (p ! NULL)return p-key;return (T)NULL;
}/** LL左左对应的情况(左单旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::leftLeftRotation(AVLTreeNodeT* k2)
{AVLTreeNodeT* k1;k1 k2-left;k2-left k1-right;k1-right k2;k2-height max( height(k2-left), height(k2-right)) 1;k1-height max( height(k1-left), k2-height) 1;return k1;
}/** RR右右对应的情况(右单旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::rightRightRotation(AVLTreeNodeT* k1)
{AVLTreeNodeT* k2;k2 k1-right;k1-right k2-left;k2-left k1;k1-height max( height(k1-left), height(k1-right)) 1;k2-height max( height(k2-right), k1-height) 1;return k2;
}/** LR左右对应的情况(左双旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::leftRightRotation(AVLTreeNodeT* k3)
{k3-left rightRightRotation(k3-left);return leftLeftRotation(k3);
}/** RL右左对应的情况(右双旋转)。** 返回值旋转后的根节点*/
template class T
AVLTreeNodeT* AVLTreeT::rightLeftRotation(AVLTreeNodeT* k1)
{k1-right leftLeftRotation(k1-right);return rightRightRotation(k1);
}/* * 将结点插入到AVL树中并返回根节点** 参数说明* tree AVL树的根结点* key 插入的结点的键值* 返回值* 根节点*/
template class T
AVLTreeNodeT* AVLTreeT::insert(AVLTreeNodeT* tree, T key)
{if (tree NULL) {// 新建节点tree new AVLTreeNodeT(key, NULL, NULL);if (treeNULL){cout ERROR: create avltree node failed! endl;return NULL;}}else if (key tree-key) // 应该将key插入到tree的左子树的情况{tree-left insert(tree-left, key);// 插入节点后若AVL树失去平衡则进行相应的调节。if (height(tree-left) - height(tree-right) 2){if (key tree-left-key)tree leftLeftRotation(tree);elsetree leftRightRotation(tree);}}else if (key tree-key) // 应该将key插入到tree的右子树的情况{tree-right insert(tree-right, key);// 插入节点后若AVL树失去平衡则进行相应的调节。if (height(tree-right) - height(tree-left) 2){if (key tree-right-key)tree rightRightRotation(tree);elsetree rightLeftRotation(tree);}}else //key tree-key){cout 添加失败不允许添加相同的节点 endl;}tree-height max( height(tree-left), height(tree-right)) 1;return tree;
}template class T
void AVLTreeT::insert(T key)
{insert(mRoot, key);
}/* * 删除结点(z)返回根节点** 参数说明* tree AVL树的根结点* z 待删除的结点* 返回值* 根节点*/
template class T
AVLTreeNodeT* AVLTreeT::remove(AVLTreeNodeT* tree, AVLTreeNodeT* z)
{// 根为空 或者 没有要删除的节点直接返回NULL。if (treeNULL || zNULL)return NULL;if (z-key tree-key) // 待删除的节点在tree的左子树中{tree-left remove(tree-left, z);// 删除节点后若AVL树失去平衡则进行相应的调节。if (height(tree-right) - height(tree-left) 2){AVLTreeNodeT *r tree-right;if (height(r-left) height(r-right))tree rightLeftRotation(tree);elsetree rightRightRotation(tree);}}else if (z-key tree-key)// 待删除的节点在tree的右子树中{tree-right remove(tree-right, z);// 删除节点后若AVL树失去平衡则进行相应的调节。if (height(tree-left) - height(tree-right) 2){AVLTreeNodeT *l tree-left;if (height(l-right) height(l-left))tree leftRightRotation(tree);elsetree leftLeftRotation(tree);}}else // tree是对应要删除的节点。{// tree的左右孩子都非空if ((tree-left!NULL) (tree-right!NULL)){if (height(tree-left) height(tree-right)){// 如果tree的左子树比右子树高// 则(01)找出tree的左子树中的最大节点// (02)将该最大节点的值赋值给tree。// (03)删除该最大节点。// 这类似于用tree的左子树中最大节点做tree的替身// 采用这种方式的好处是删除tree的左子树中最大节点之后AVL树仍然是平衡的。AVLTreeNodeT* max maximum(tree-left);tree-key max-key;tree-left remove(tree-left, max);}else{// 如果tree的左子树不比右子树高(即它们相等或右子树比左子树高1)// 则(01)找出tree的右子树中的最小节点// (02)将该最小节点的值赋值给tree。// (03)删除该最小节点。// 这类似于用tree的右子树中最小节点做tree的替身// 采用这种方式的好处是删除tree的右子树中最小节点之后AVL树仍然是平衡的。AVLTreeNodeT* min maximum(tree-right);tree-key min-key;tree-right remove(tree-right, min);}}else{AVLTreeNodeT* tmp tree;tree (tree-left!NULL) ? tree-left : tree-right;delete tmp;}}return tree;
}template class T
void AVLTreeT::remove(T key)
{AVLTreeNodeT* z; if ((z search(mRoot, key)) ! NULL)mRoot remove(mRoot, z);
}/* * 销毁AVL树*/
template class T
void AVLTreeT::destroy(AVLTreeNodeT* tree)
{if (treeNULL)return ;if (tree-left ! NULL)destroy(tree-left);if (tree-right ! NULL)destroy(tree-right);delete tree;
}template class T
void AVLTreeT::destroy()
{destroy(mRoot);
}/** 打印二叉查找树** key -- 节点的键值 * direction -- 0表示该节点是根节点;* -1表示该节点是它的父结点的左孩子;* 1表示该节点是它的父结点的右孩子。*/
template class T
void AVLTreeT::print(AVLTreeNodeT* tree, T key, int direction)
{if(tree ! NULL){if(direction0) // tree是根节点cout setw(2) tree-key is root endl;else // tree是分支节点cout setw(2) tree-key is setw(2) key s setw(12) (direction1?right child : left child) endl;print(tree-left, tree-key, -1);print(tree-right,tree-key, 1);}
}template class T
void AVLTreeT::print()
{if (mRoot ! NULL)print(mRoot, mRoot-key, 0);
}
#endif
测试代码
/*** C 语言: AVL树** author skywang* date 2013/11/07*/#include iostream
#include start.h
using namespace std;static int arr[] {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
#define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )int main()
{int i,ilen;AVLTreeint* treenew AVLTreeint();cout 依次添加: ;ilen TBL_SIZE(arr);for(i0; iilen; i){cout arr[i] ;tree-insert(arr[i]);}cout \n 前序遍历: ;tree-preOrder();cout \n 中序遍历: ;tree-inOrder();cout \n 后序遍历: ;tree-postOrder();cout endl;cout 高度: tree-height() endl;cout 最小值: tree-minimum() endl;cout 最大值: tree-maximum() endl;cout 树的详细信息: endl;tree-print();i 8;cout \n 删除根节点: i;tree-remove(i);cout \n 高度: tree-height() ;cout \n 中序遍历: ;tree-inOrder();cout \n 树的详细信息: endl;tree-print();// 销毁二叉树tree-destroy();system(pause);return 0;
}
References
AVL树(二)之 C的实现 - 如果天空不死 - 博客园
效果如下
