东圃网站建设,怀远做网站电话,海贼王路飞和女帝做的网站,建设一个个人小说网站AVL树是带有平衡条件的二叉查找树。这个平衡条件必须保持#xff0c;并且它必须保证树的深度是O#xff08;logN#xff09;。 一棵AVL树是其每一个节点的左子树和右子树的高度最多差1的二叉查找树。#xff08;空树的高度定义为-1#xff09;。在插入以后。仅仅有那些从插… AVL树是带有平衡条件的二叉查找树。这个平衡条件必须保持并且它必须保证树的深度是OlogN。 一棵AVL树是其每一个节点的左子树和右子树的高度最多差1的二叉查找树。空树的高度定义为-1。 在插入以后。仅仅有那些从插入点到根节点的路径上的节点的平衡可能被改变由于仅仅有这些节点的子树可能发生变化。当我们沿着这条路径上行到根并更新平衡信息时。我们能够找到一个节点它的新平衡破坏了AVL条件。我们将指出怎样在第一个这种节点(即最深的节点又一次平衡这棵树并证明这一又一次平衡保证整个树满足AVL特性。 让我们把必须又一次平衡的这个节点叫做a。因为随意节点最多有两个儿子因此高度不平衡时。a点的两棵子树的高度差2。easy看出这样的不平衡可能出如今以下四种情况中 1.对a的左儿子的左子树进行一次插入 2.对a的左儿子的右子树进行一次插入 3.对a的右儿子的左子树进行一次插入 4.对a的右儿子的右子树进行一次插入 第一种情况是插入发生在“外边的情况即左—左的情况或右—右的情况。该情况通过对树的一次单旋转而完毕调整。另外一种情况是插入发生在”内部“的情形(即左—右的情况或右—左的情况该情况通过略微复杂些的双旋转来处理。 AVL树本质上还是一棵二叉搜索树它的特点是 本身首先是一棵二叉搜索树。 带有平衡条件每一个结点的左右子树的高度之差的绝对值平衡因子最多为1 #include iostream
using namespace std;
const int LH 1;
const int EH 0;
const int RH -1;
bool TRUE 1;
bool FALSE 0;typedef struct BSTNode
{int key;int bf;BSTNode *lchild, *rchild;
}BSTNode;//中序遍历
void inordertree(BSTNode * root)
{if (root){inordertree(root-lchild);cout root-key,;inordertree(root-rchild);}
}//前序遍历
void preordertree(BSTNode * root)
{if (root){cout root-key,;preordertree(root-lchild);preordertree(root-rchild);}
}
//右旋
void R_Rotate(BSTNode * p)
{BSTNode *lc p-lchild;p-lchild lc-rchild;lc-rchild p;p lc;
}//左旋
void L_Rotate(BSTNode * p)
{BSTNode *rc p-rchild;p-rchild rc-lchild;rc-lchild p;p rc;
}void LeftBalance(BSTNode * T)
{BSTNode *lc T-lchild;switch (lc-bf){case LH:T-bf lc-bf EH;R_Rotate(T);break;case RH:BSTNode *rd lc-rchild;switch (rd-bf){case LH:T-bf RH;lc-bf EH;break;case EH:T-bf lc-bf EH;lc-bf LH;break;}rd-bf EH;L_Rotate(T-lchild);//先左旋R_Rotate(T);break;}
}void RightBalance(BSTNode * T)
{BSTNode *rc T-rchild;switch (rc-bf){case RH:T-bf rc-bf EH;L_Rotate(T);break;case LH:BSTNode *ld rc-lchild;switch (ld-bf){case RH:T-bf LH;rc-bf EH;break;case EH:T-bf rc-bf EH;break;case LH:T-bf EH;rc-bf RH;break;}ld-bf EH;R_Rotate(T-rchild);L_Rotate(T);break;}
}int insertAVL(BSTNode * t, int e, bool taller)
{if (!t){t new BSTNode;t-key e;t-lchild t-rchild NULL;t-bf EH;taller TRUE;}else{if (e t-key){taller FALSE;return 0;}if (e t-key){if (!insertAVL(t-lchild, e,taller))return 0;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;}}}else{if (!insertAVL(t-rchild, e, taller))return 0;if (taller){switch (t-bf){case RH:RightBalance(t);taller FALSE;break;case EH:t-bf RH;taller TRUE;break;case LH:t-bf EH;taller FALSE;break;}}}}return 1;
}BSTNode *search(BSTNode *t, int key)
{BSTNode *p t;while (p){if (p-key key)return p;else if (p-key key)p p-rchild;elsep p-lchild;}return p;
}int main()
{BSTNode *root NULL;BSTNode *r;bool taller FALSE;int array[] { 13, 24, 37, 90, 53 };for (int i 0; i 5; i)insertAVL(root, array[i], taller);cout inorder traverse... endl;inordertree(root);cout endl;cout preorder traverse... endl;preordertree(root);cout endl;cout search key... endl;r search(root, 37);if (r){cout r-key endl;}else{cout not find endl;}system(pause);return 0;
}转载于:https://www.cnblogs.com/jhcelue/p/6880336.html
