AVL Tree

AVL 트리

: 자가 균형 이진 탐색 트리

Rotation

왼쪽 자식과 오른쪽 자식의 높이를 비교해서 그 차이가 1을 넘는다면
균형을 맞추기 위해서 노드를 이동시킨다

// null 일 때 까지 재귀를 돌려서, 카운팅을 하며 높이를 구한다
int NodeHeight(Node *node){
    if (node == NULL) return 0;
	
    int leftDepth = NodeHeight(node->left);
    int rightDepth = NodeHeight(node->right);
	
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

Balance Factor
왼쪽 자식이 더 높으면 오른쪽으로 rotation하고 오른쪽 자식이 더 높이 있다면 왼쪽으로 rotation하는 조건을 넣는다

if (BF(node->left)>0){
	node = LL(node); 
    }else{
    	node = LR(node);
}

함수가 실행되면
왼 자식을 부모노드로 하여 오른쪽으로 한칸씩 이동하게 된다

Node *LL(Node *node){
    Node *LNode = node->left;
    node->left = LNode->right;
    LNode->right = node;
    return LNode;
}
Node *LR(Node *node){
    Node *Left = node->left;
    Left = RR(Left);
    return LL(node);
}

이 로테이션을 오른 자식으로도 적용을 시켜준다

Insertion

조건에 맞게 탐색해서 NULL 인 곳에 새로운 노드를 추가해준다
조건 : 루트 노드보다 작으면 왼 자식으로 크면 오른 자식으로 간다

Node *Insert(Node *node, int data){
    if (!node){
        node = (Node *)malloc(sizeof(Node));
        node->data = data;
        node->left = node->right = NULL;
    }
    else if (data < node->data){
        node->left = Insert(node->left,data);
        node = AVL(node);
    }else if (data > node->data){
        node->right = Insert(node->right,data);
        node = AVL(node);
    }else{
        printf("Already Exist : %d\n",data);
    }
    return node;
}

🛸 LINKS
[Visualization] AVL Tree
[Tistory] AVL Tree