AVL 트리

AVL 트리

• 균형잡힌 이진 탐색 트리

• 검색, 삽입, 삭제의 시간 복잡도는 ​

• 각각의 노드 마다 왼쪽의 서브트리의 높이와 오른쪽의 서브트리의 높이 차이(균형)가 1보다 크지 않음.

노드 클래스

class Node {
public:
    int data;
    int height;
    Node* left;
    Node* right;
​
    Node(int data) {
        this->data = data;
        this->height = 1;
        left = NULL;
        right = NULL;
    }
};

AVLTree 클래스

class AVLTree {
public:
    Node* root;
​
    AVLTree(int data) {
        root = new Node(data);
    }
    
    Node* RotateLL(Node* node) {}
    Node* RotateRR(Node* node) {}
    Node* RotateLR(Node* node) {}
    Node* RotateRL(Node* node) {}
    
    int Height(Node* node) {}
    int HeightDiff(Node* node) {}
    void Rebalance() {}
​
    void Insert(int data) {}
    
    void Preorder(Node* root) {}
    void Inorder(Node* root) {}
    void Postorder(Node* root) {}
};

AVL 트리의 회전

Node* RotateLL(Node* node) {
    Node* parentNode = node;
    Node* childNode = parentNode->left;
​
    parentNode->left = childNode->right;
    childNode->right = parentNode;
​
    return childNode;
}
​
Node* RotateRR(Node* node) {
    Node* parentNode = node;
    Node* childNode = parentNode->right;
​
    parentNode->right = childNode->left;
    childNode->left = parentNode;
​
    return childNode;
}
​
Node* RotateLR(Node* node) {
    Node* parentNode = node;
    Node* childNode = parentNode->left;
​
    parentNode->left = RotateRR(childNode);
    return RotateLL(parentNode);
}
​
Node* RotateRL(Node* node) {
    Node* parentNode = node;
    Node* childNode = parentNode->right;
​
    parentNode->right = RotateLL(childNode);
    return RotateRR(parentNode);
}

• AVL 트리의 회전은 크게 4가지 종류가 있다. LL, RR, LR, RR

• LL 회전은 LL 상태(자식 노드가 왼쪽으로 연속으로 연결되어 균형이 +2 이상이 된 상태)를 보완하기 위한 회전이다.

    5
   /
  3         =>          3
 /                     /  \
1                       1    5

• RR 회전은 반대로

    1
      \
       3    =>          3
        \              /  \
          5             1    5

• LR회전은 LR 상태에서 왼쪽 서브트리를 기준으로 RR회전을하고, LL 상태로 만든뒤, LL 회전을 하는 과정이다.

    5                     5
   /                     /
  1         =>          3           =>          3
   \                   /                       /  \
    3                  1                         1    5

• RL회전은 LR 회전의 반대

    1                  1
      \                 \
       5    =>          3           =>          3
      /                   \                    /  \
     3                       5                  1    5

AVL 트리의 높이 차이(균형)

int Height(Node* node) {
    if (node == NULL) {
        return 0;
    }
    int leftHeight = Height(node->left);
    int rightHeight = Height(node->right);
​
    if (leftHeight > rightHeight) {
        return leftHeight + 1;
    }
    else {
        return rightHeight + 1;
    }
}
​
int HeightDiff(Node* node) {
    if (node == NULL) {
        return 0;
    }
​
    int leftHeight = Height(node->left);
    int rightHeight = Height(node->right);
    return leftHeight - rightHeight;
}

Rebalancing

void Rebalance() {
    int hDiff = HeightDiff(this->root);
    if (hDiff > 1) {
        if (HeightDiff(this->root->left) > 0) {
            this->root = RotateLL(this->root);
        }
        else {
            this->root = RotateLR(this->root);
        }
    }
​
    if (hDiff < -1) {
        if (HeightDiff(this->root->right) < 0) {
            this->root = RotateRR(this->root);
        }
        else {
            this->root = RotateRL(this->root);
        }
    }
}

• 높이차이가 1보다 크면 LR이나 LL 상태이다.

  • 왼쪽서브트리의 높이차이가 0보다 크면 LL 상태이고, 아니면 LR상태

• 높이차이가 -1보다 작으면 RR이나 RL 상태이다.

  • 오른쪽서브트리의 높이차이가 0보다 작으면 RR 상태이고, 아니면 RL상태

AVL 트리 삽입

void Insert(int data) {
    Node* parent = NULL;
    Node* cur = root;
​
    while (cur != NULL) {
        if (data == cur->data) {
            return;
        }
​
        parent = cur;
​
        if (cur->data > data) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }
​
    cur = new Node(data);
​
    if (parent != NULL) {
        if (data < parent->data) {
            parent->left = cur;
        }
        else {
            parent->right = cur;
        }
    }
​
    Rebalance();
}

• 노드를 삽입하고 나서 리밸런싱을 한번 해준다.

트리 순회

void Preorder(Node* root) {
    cout << root->data << endl;
    if (root->left != NULL) Preorder(root->left);
    if (root->right != NULL) Preorder(root->right);
}
​
void Inorder(Node* root) {
    if (root->left != NULL) Inorder(root->left);
    cout << root->data << endl;
    if (root->right != NULL) Inorder(root->right);
}
​
void Postorder(Node* root) {
    if (root->left != NULL) Postorder(root->left);
    if (root->right != NULL) Postorder(root->right);
    cout << root->data << endl;
}

메인 함수

int main() {
    AVLTree* tree = new AVLTree(1);
    tree->Insert(3);
    tree->Insert(5);
    tree->Insert(7);
    tree->Insert(9);
    tree->Insert(4);
​
    tree->Preorder(tree->root);
    //tree->Inorder(tree->root);
    //tree->Postorder(tree->root);
​
    return 0;
}