数据结构 编程1年新手视角的平衡二叉树AVL从C与C++实现②

数据结构 编程1年新手视角的平衡二叉树AVL从C与C++实现②"/>

数据结构 编程1年新手视角的平衡二叉树AVL从C与C++实现②

接下来，是数据的插入

我们需要对数据插入的结点先进行判断，有如下三个情况

当插入的数据value<结点的value，应该递归地插入该结点的左子树（的左子树...的左子树）

当插入的数据value>结点的value，应该递归地插入结点的右子树（的右子树...的右子树）

直至递归地到达左右子树为空处，顺利插入并申请一个新的空间（new或者malloc放置新数据），此处是函数的出口。

那么我们可以写出insert函数

void insert(node*node, int value){

        if(node==NULL){

                node = newNode(value);

                return;

        if(value<node->value){

                insert(node->left, value);

                node->height = getUpdateHeight(node);

                if (//LL型 LR 型){

                //statement;

                }

        }

        if(value>node->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的左子树的平衡因子==-1），LR型可看作成LL型与RR型的结合，对应操作是先对node左子树(RR型)进行左旋leftRotate(node->left)，再对node本身(LL型)作右旋rightRotate(node)。

RR型（结点的左子树高度-右子树高度==-2，且node的右子树的平衡因子==-1），

RR型对应的操作为左旋leftRotate(node)。

RL型（node的右子树的平衡因子==1），RL型可看作成RR型与LL型的结合，对应操作是先对node右子树(LL型)进行右旋rightRotate(node->right)，再对node本身(RR型)作左旋leftRotate(node)。