[완료]안녕하세요 AVL tree 구현 관련 질문입니다.

template <class K, class E>
void AVL<K, E>::insert(const K& k, const E& e)
{
        if(!root){
                root = malloc(sizeof(AvlNode<K,E>));
                return;
        }
 
        AvlNode<K,E> *a = NULL,  /*균형 인수 +-1을 가진 가장 최근의 노드*/
                     *pa = NULL, /*균형 인수 +-1을 가진 가장 최근의 노드 의 부모*/
                     *p = root,  /*연산에 사용될 노드의 임의 저장소*/
                     *pp = NULL; /*위 노드의 부모*/
 
        while(p){               /*삽입 위치 탐색*/
                if(p->bf){a = p; pa = pp;}/*균형 인수가 +_ 1 이면 a, ap에 저장*/
                if(k < p->key){pp = p; p = p->left_child;} //왼쪽 자식 으로 이동
                else if( k > p->key){pp = p; p = p->right_child;} //오른쪽 자식으로 이동
                        else{p ->element= e; return;}
        }
        AvlNode<K,E> *y = malloc(sizeof(AvlNode<K,E>)); // 추가할 노드 생성
        y->key =  k;
        y->element = e;
//원소를 적절한 위치에 추가한다.
        if(k < pp->key) pp->left_child = y;
        else pp->right_child = y;
//노드 a에서 pp의 균형 인수를 조정. a의 정의에 의해, 이 경로 내에
//있는 모든 노드들은 균형 인수 0이 되어야 하며 후에 +_1로 변경
//d = +1은 x 가 a의 왼쪽 서브트리에 삽입된 것을 의미
//d = -1은 x 가 a의 오른쪽 서브 트리에 삽입된 것을 의미
        int d;//원소 1개가 추가 되었으므로 1 또는 -1의 값을 갖는다.
        AvlNode<K,E> *b, //a의 자식
                     *c; //b의 자식
        if(k > a ->key){b = p = a->right_child; d = -1;} //a의 오른쪽 서브트리에 삽입
        else{b = p = a->left_child; d = 1;}              //a의 왼쪽 서브트리에 삽입
//위에 근거해서 a의 오른쪽트리에 삽입 되었는지 왼쪽 트리에 삽입 되었는지 추정
        while(p != y)           //a 부터 시작하여 추가 노드까지 균형 인수 변경
        {
                if(k > p->key){//오른쪽 높이가 1 만큼 증가
                        p->bf = -1; p = p->right_child;
                }else{         //왼쪽 높이가 1 만큼 증가
                        p -> bf = 1; p = p->left_child;
                }
        }
 
        //트리가 불균형 인가?
        if(!(a->bf) || !(a->bf +d)){//트리가 계속 균형을 유지
                a->bf += d; return;
        }
 
        //아래 각각의 연산이 끝난 후에는 변수 b에 회전시킨 서브 트리의 root를 assign 해 놓는다.
        if(d == 1){//왼쪽 불균형
                if(b->bf ==1){//LL 회전
                        a->left_child = b->right_child;
                        b->right_child = a; a->bf = 0; b->bf = 0;
                }else{//LR 회전
                        c = b->right_child;
                        b->right_child = c->left_child;
                        a->left_child = c->right_child;
                        c->left_child = b;
                        c->right_child = a;
                        switch(c->bf){
                                case 1:
                                        a->bf = -1; b->bf = 0;
                                        break;
                                case -1:
                                        b->bf = 1; a->bf = 0;
                                        break;
                                case 0:
                                        b->bf = 0; a->bf = 0;
                                        break;
                        }
                        c->bf = 0; b = c;//회전시킨 서브트리의 루트를 b에 assign
               }
        }else{//오른쪽 불균형- L 타입과 대칭
                if(b->bf == -1){//RR 회전
                        a->right_child = b->left_child;
                        b->left_child = a; a->bf = 0; b->bf = 0;
                }else{
                        c = b->left_child;
                        a->right_child = c->left_child;
                        b->left_child = c->right_child;
                        c->left_child = a;
                        c->right_child = b;
                        switch(c->bf){
                                case 1:
                                        a->bf = 0; b->bf = -1;
                                        break;
                                case -1:
                                        a->bf = 1; b->bf = 0;
                                        break;
                                case 0:
                                        a->bf = 0; b->bf = 0;
                                        break;
                        }
                        c->bf = 0; b = c;
                }
        }
//변경된 서브트리의 루트를 기존 트리에 assign한다.
        if(!pa)root = b;
        else if(a == pa->left_child)pa->left_child = b;
             else pa->right_child = b;
        return;
}