河南省建设网站,桂林漓江阳朔,内蒙网站开发,深圳企业网站建设专业接下来#xff0c;是数据的插入
我们需要对数据插入的结点先进行判断#xff0c;有如下三个情况
当插入的数据value结点的value#xff0c;应该递归地插入该结点的左子树#xff08;的左子树...的左子树#xff09;
当插入的数据value结点的value#xff0c;应…接下来是数据的插入
我们需要对数据插入的结点先进行判断有如下三个情况
当插入的数据value结点的value应该递归地插入该结点的左子树的左子树...的左子树
当插入的数据value结点的value应该递归地插入结点的右子树的右子树...的右子树
直至递归地到达左右子树为空处顺利插入并申请一个新的空间new或者malloc放置新数据此处是函数的出口。 那么我们可以写出insert函数
void insert(node*node, int value){ if(nodeNULL){ node newNode(value); return; if(valuenode-value){ insert(node-left, value); node-height getUpdateHeight(node); if (//LL型 LR 型){ //statement; } } if(valuenode-value){ insert(node-right, value); node-height getUpdateHeight(node); if (//RR型 RL型){ //statement; } }
}
以上预留了//statement位置应对AVL的平衡特性正如篇①的情况插入结点可能会导致冲突/不平衡。根据前人的总结共有以下4种类型
LL型结点的左子树高度-右子树高度2即平衡因子2且node的左子树的平衡因子1
LL型对应的操作为右旋rightRotate(node)。
LR型node的左子树的平衡因子-1LR型可看作成LL型与RR型的结合对应操作是先对node左子树(RR型)进行左旋leftRotate(node-left)再对node本身(LL型)作右旋rightRotate(node)。
RR型结点的左子树高度-右子树高度-2且node的右子树的平衡因子-1
RR型对应的操作为左旋leftRotate(node)。
RL型node的右子树的平衡因子1RL型可看作成RR型与LL型的结合对应操作是先对node右子树(LL型)进行右旋rightRotate(node-right)再对node本身(RR型)作左旋leftRotate(node)。
