严老太，在您面前小孙孙我实在心智底下啊！一个AVL就把我整的团团转，单向右旋，单向左旋，双向旋转先左后右，双向旋转先右后左，很简单的道理，您就是不肯轻易说出来，在那转啊转的，貌似很神秘的样子！
在构造AVL树的时候，会出现插入某个节点后输不再平衡的情况，这时候只需要找到离插入点最近的、平衡因子不合法的节点，调整以此节点为根的子树(*)，使其平衡因子合法，其实就是使这棵子树(*)的高度与插入节点前相比不发生变化。具体的调整策略因具体情况而异，但原则都是一样的：首先应该明确根节点大于左孩子而小于右孩子，另外，调整后的子树(*)的根是一定会发生变化的，且变化后的子树应该满足平衡条件，即平衡因子为1，0，-1之一。
这里有一个图示，
rotate sample
还有两个，
"/"型
"<"型
这里还有两段示例代码，
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void R_Rotate (BSTree &p) { //~ 对以*p为根的二叉排序树作右旋转处理，处理之后p指向新的树根结点，即旋转 //~ 处理之前的左子树的根结点 lc=p->lchild ; //~ lc指向的*p的左子树根结点 p->lchild=lc->rchild ; //~ lc的右子树挂接为*p的左子树 lc->rchild=p ; p=lc ; //~ p指向新的根结点 }//~ R_Rotate void L_Rotate (BSTree &p) { //~ 对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转 //~ 处理之前的右子树的根结点 rc=p->rchild ; //~ rc指向的*p的右子树根结点 p->rchild=rc->lchild ; //~ rc左子树挂接为*p的右子树 rc->lchild=p ; p=rc ; //~ p指向新的根结点 }//~ L_Rotate |
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
Be the first to comment on this entry.