建设工程网站单位名单,网站建设的几个要素,聊城的网站制作公司,徐州网站关键词排名平衡二叉树(Balancedbinary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskiiand Landis)于1962年首先提出的#xff0c;所以又称为AVL树。 定义#xff1a;平衡二叉树或为空树,或为如下性质的二叉排序树: #xff08;1#xff09;左右子树深度之差的绝对值不超过1; 所以又称为AVL树。 定义平衡二叉树或为空树,或为如下性质的二叉排序树: 1左右子树深度之差的绝对值不超过1; 2左右子树仍然为平衡二叉树. 平衡二叉树可以避免排序二叉树深度上的极度恶化使树的高度维持在Ologn来提高检索效率。 因为插入节点导致整个二叉树失去平衡分成如下的四种情况 假设由于在二叉排序树上插入节点而失去平衡的最小子数根节点的指针为a即a是离插入节点最近且平衡因子绝对值超过1的祖先节点则失去平衡后进行调整的规律如下 1.如上图LL单向右旋处理由于在*a的左子树根节点的左子树上插入节点*a的平衡因子由1增至2致使以*a为根节点的子树失去平衡则需要进行一次向右的顺时针旋转操作。 2.如上图RR单向左旋处理由于在*a的右子树根节点的右子树上插入节点 *a的平衡因子有-1变为-2致使以*a为根节点的子树失去平衡则学要进行一次向左的逆时针旋转操作。 3.如上图LR双向旋转先左后右处理由于在*a的左子树根节点的右子树插入节点*a的平衡因子有1增至2致使以*a为根节点的子树失去平衡则需要进行两次旋转先左旋后右旋操作。 4.如上图RL双向旋转先右后左处理由于在*a的右子树根节点的左子树上插入节点*a的平衡因子由-1变为-2致使以*a为根节点的子树失去平衡则需要进行两次旋转先左旋后右旋操作。 #includeiostream
#includecstring
#includestring
#includequeue
#includemap
#includecstdio
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
using namespace std;template typename ElemType
class BSTNode{public:ElemType data;//节点的数据 int bf;//节点的平衡因子BSTNode *child[2];BSTNode(){child[0] NULL;child[1] NULL;}
};typedef BSTNodestring BSTnode, *BSTree;template typename ElemType
class AVL{public:BSTNodeElemType *T;void buildT();void outT(BSTNodeElemType *T);private:bool insertAVL(BSTNodeElemType* T, ElemType key, bool taller); void rotateT(BSTNodeElemType* o, int x);//子树的左旋或者右旋void leftBalance(BSTNodeElemType* o);void rightBalance(BSTNodeElemType* o);
};template typename ElemType
void AVLElemType::rotateT(BSTNodeElemType* o, int x){BSTNodeElemType* k o-child[x^1];o-child[x^1] k-child[x];k-child[x] o;o k;
}template typename ElemType
void AVLElemType::outT(BSTNodeElemType *T){if(!T) return;coutT-data ;outT(T-child[0]);outT(T-child[1]);
}template typename ElemType
void AVLElemType::buildT(){T NULL;ElemType key;while(cinkey){if(key0) break;bool taller false;insertAVL(T, key, taller);outT(T);coutendl;}
}template typename ElemType
bool AVLElemType::insertAVL(BSTNodeElemType* T, ElemType key, bool taller){if(!T){//插入新的节点tallertrue 那么树的高度增加 T new BSTNodeElemType();T-data key;T-bf EH;taller true;} else {if(T-data key){taller false;return false;}if(T-data key){//向T的左子树进行搜索并插入 if(!insertAVL(T-child[0], key, taller)) return false;if(taller){//switch(T-bf){case LH://此时左子树的高度高左子树上又插入了一个节点失衡需要进行调整 leftBalance(T);taller false;//调整之后高度平衡 break; case EH:T-bf LH;taller true;break; case RH:T-bf EH;taller false; break;}}} if(T-data key) {//向T的右子树进行搜索并插入 if(!insertAVL(T-child[1], key, taller)) return false;switch(T-bf){case LH:T-bf EH;taller false; break; case EH:T-bf RH;taller true;break; case RH:rightBalance(T); taller false; break;}}}return true;
}template typename ElemType
void AVLElemType::leftBalance(BSTNodeElemType* T){BSTNodeElemType* lchild T-child[0];switch(lchild-bf){//检查T的左子树的平衡度并作相应的平衡处理 case LH://新节点 插入到 T的左孩子的左子树上需要对T节点做单旋(右旋)处理 T-bf lchild-bf EH; rotateT(T, 1);break;case RH://新节点 插入到 T的左孩子的右子树上需要做双旋处理 1.对lchild节点进行左旋2.对T节点进行右旋 BSTNodeElemType* rdchild lchild-child[1];switch(rdchild-bf){//修改 T 及其左孩子的平衡因子 case LH: T-bf RH; lchild-bf EH; break;case EH: T-bf lchild-bf EH; break;//发生这种情况只能是 rdchild无孩子节点case RH: T-bf EH; lchild-bf LH; break; }rdchild-bf EH; rotateT(T-child[0], 0);//不要写成 rotateT(lc, 0);//这样的话T-lchild不会改变 rotateT(T, 1);break;}
}template typename ElemType
void AVLElemType::rightBalance(BSTNodeElemType* T){BSTNodeElemType* rchild T-child[1];switch(rchild-bf){//检查T的左子树的平衡度并作相应的平衡处理 case RH://新节点 插入到 T的右孩子的右子树上需要对T节点做单旋(左旋)处理 T-bf rchild-bf EH; rotateT(T, 0);break;case LH://新节点 插入到 T的右孩子的左子树上需要做双旋处理 1.对rchild节点进行右旋2.对T节点进行左旋 BSTNodeElemType* ldchild rchild-child[0];switch(ldchild-bf){//修改 T 及其右孩子的平衡因子 case LH: T-bf EH; rchild-bf RH; break;case EH: T-bf rchild-bf EH; break;//发生这种情况只能是 ldchild无孩子节点 case RH: T-bf LH; rchild-bf EH; break; }ldchild-bf EH; rotateT(T-child[1], 1);rotateT(T, 0);break;}
}int main(){AVLint avl;avl.buildT();avl.outT(avl.T);return 0;
} /*13 24 37 90 53 0
*/ 转载于:https://www.cnblogs.com/hujunzheng/p/4665451.html
