AVL tree

rlawlgus·2022년 10월 1일
0

Data structures augmentation 코딩

Rank 구현

특정 값보다 작은 값을 가지는 노드의 개수

  • 찾고자 하는 값이 나올 때까지 루트노드부터 내려간다.
  • 찾고자 하는 값보다 작거나 같음 => +1, +왼쪽서브트리의 개수
  • 찾고자 하는 값보다 큼 => 아무일도 일어나지 않음
#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* left, * right;
    int leftSize;
};
// x노드를 찾고자 한다.
int getRank(Node* root, int x)
{
    // Step 1. x일 경우
    if (root->data == x)
        return root->leftSize;
    // Step 2. x보다 큼
    if (x < root->data) {
        if (!root->left)
            return -1;
        else
            return getRank(root->left, x); //아무일도 일어나지 않음
    }
    // Step 3. x보다 작거나 같음
    else {
        if (!root->right)
            return -1;
        else {
            int rightSize = getRank(root->right, x);
            if (rightSize == -1) return -1;
            return root->leftSize + 1 + rightSize;
        }
    }
}

AVL tree 구현

#include <iostream>
using namespace std;
struct nodeAVL
{
    int data;
    struct nodeAVL* left;
    struct nodeAVL* right;
} *root;
class classAVL
{
public:
    // 노드의 높이를 반환
    int getHeight(nodeAVL* node) {
        int h = 0;
        if (node != NULL)
        {
        // 재귀적으로 왼쪽 혹은 오른쪽으로 검색
            int left = getHeight(node->left);
            int right = getHeight(node->right);
            int maxHeight = max(left, right);
            h = maxHeight + 1;
        }
        return h;
    }
    // 균형인수(높이의 차이)를 반환
    int getHeightDiff(nodeAVL* node) {
        // 왼쪽 자식의 높이와 오른쪽 자식의 높이 차이를 반환
        if (node == NULL) return 0;
        int hleft = getHeight(node->left);
        int hright = getHeight(node->right);
        return hleft - hright;
    }
    // RR 회전 함수
    nodeAVL* rr(nodeAVL* parent) {
        nodeAVL* child = parent->right;
        parent->right = child->left;
        child->left = parent;
        return child;
    }
    // LL 회전 함수
    nodeAVL* ll(nodeAVL* parent) {
        nodeAVL* child = parent->left;
        parent->left = child->right;
        child->right = parent;
        return child;
    }
    // LR 회전 함수입니다.
    nodeAVL* lr(nodeAVL* parent) {
        // LR 회전은 왼쪽 자식을 기준으로 RR, 본인을 기준으로 LL회전
        nodeAVL* child = parent->left;
        parent->left = rr(child);
        return ll(parent);
    }
    // RL 회전 함수
    nodeAVL* rl(nodeAVL* parent) {
        // RL 회전은 오른쪽쪽 자식을 기준으로 LL, 본인을 기준으로 RR회전
        nodeAVL* child = parent->right;
        parent->right = ll(child);
        return rr(parent);
    }
    // 트리의 균형을 맞추는 함수
    nodeAVL* balance(nodeAVL* parent) {
        int BF = getHeightDiff(parent);
        // 왼쪽 서브트리쪽으로 삽입이 되어 균형이 깨진 경우
        if (BF > 1)
        {
            // 그 왼쪽 자식노드
            if (getHeightDiff(parent->left) > 0)
            {
                parent = ll(parent); //LL
            }
            // 그 오른쪽 자식 노드
            else
            {
                parent = lr(parent); //LR
            }
        }
        else if (BF < -1)
        {
            if (getHeightDiff(parent->right) > 0)
            {
                parent = rl(parent); //RR
            }
            else
            {
                parent = rr(parent); //RL
            }
        }
        return parent;
    }
    // AVL 트리에 새로운 원소를 삽입
    nodeAVL* insertAVL(nodeAVL* parent, int value) {
        // 현재 트리가 비었을 때
        if (parent == NULL)
        {
            parent = new nodeAVL;
            parent->data = value;
            parent->left = NULL;
            parent->right = NULL;
            return parent;
        }
        else if (value < parent->data)
        {
            parent->left = insert(parent->left, value);
            parent = balance(parent);
        }
        // 크거나 같은 경우 오른쪽 서브트리에 삽입
        else if (value >= parent->data)
        {
            parent->right = insert(parent->right, value);
            parent = balance(parent);
        }
        return parent;
    }
    // 트리에 원소를 삽입하는 함수
    nodeAVL* insert(nodeAVL* parent, int value)
    {
        // 현재 트리가 비었을 때
        if (parent == NULL)
        {
            parent = new nodeAVL;
            parent->data = value;
            parent->left = NULL;
            parent->right = NULL;
            return parent;
        }
        else if (value < parent->data)
        {
            parent->left = insert(parent->left, value);
            parent = balance(parent);
        }
        // 크거나 같은 경우 오른쪽 서브트리에 삽입
        else if (value >= parent->data)
        {
            parent->right = insert(parent->right, value);
            parent = balance(parent);
        }
        return parent;
    }
};

AVL tree 정의 등 강의 내용 정리

이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조로 탐색이 걸리는 시간도는 O(log n)으로 동일하다. 이진 탐색 트리는 O(log n)의 시간 복잡도를 가지며, 삽입과 삭제에 용이하다. 하지만 최악의 경우 이진 탐색 트리의 형태가 경사 트리가 될 때 탐색의 시간복잡도는 O(n)로 높아지게 된다. 그러므로 균형 트리와 같은 형태의 균형을 유지는 것이 중요하며 이진 탐색 트리에서 균형 상태가 되도록 하는 방법을 AVL tree라고 한다.

AVL tree

AVL tree는 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. AVL tree는 항상 균형 트리를 보장하기 때문에 탐색의 시간 복잡도를 O(log n)으로 보장한다.

  • 이진 탐색 트리의 속성을 가진다.
  • 탐색의 시간 복잡도는 O(log n)
  • 삽입, 삭제로 인해 불균형 상태가 되면 회전을 통해 균형 상태를 유지한다.
  • 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.

AVL tree에서 불균형 상태일 때 4가지의 경우로 분류할 수 있다. 부모 노드를 기준으로 삽입되는 노드가 부모노드로 부터의 위치를 기준으로 분류한다.

  • LL타입 : 삽입할 노드가 부모노드의 왼쪽 서브트리의 왼쪽 서브트리에 삽입된다.
  • RR타입 : 삽입할 노드가 부모노드의 오른쪽 서브트리의 오른쪽 서브트리에 삽입된다.
  • LR타입 : 삽입할 노드가 부모노드의 왼쪽 서브트리의 오른쪽 서브트리에 삽입된다.
  • RL타입 : 삽입할 노드가 부모노드의 오른쪽 서브트리의 왼쪽 서브트리에 삽입된다.

Balance Factor(BF)

AVL tree 를 확인하기 위해서는 Balanced factor(BF), 즉 균형인수를 통해서 알 수 있다. 균형인수는 AVL tree 에서 살펴봤듯이 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이로 정의한다.

균형이 잡힌 트리란 이진 트리에 노드를 꽉꽉 채워 눌러담은 형태로 모든 노드에 대해 노드의 BF 절대값이 1이하인 트리를 말한다.

AVL tree 연산

AVL tree 는 삽입과 삭제 연산에서 균형 상태을 벗어나 불균형 상태가 된다. 다시 균형 상태로 유지하기 위한 방법은 회전(Rotation)이다.

불균형 상태는 각각 LL 회전, RR 회전, LR 회전, RL 회전으로 균형 상태로 만들 수 있다.

LL 회전

RR 회전

LL 회전과 RR 회전은 1번 회전을 하며 이를 단순 회전이라고 한다. 탐색의 순서를 유지하면서 부모와 자식의 위치를 교환한다.

rotate_LL(A)

  • B <- A의 왼쪽 자식
  • B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
  • A를 B의 오른쪽 자식 노드로 만든다.
    rotate_RR(A)
  • B <- A의 왼쪽 자식
  • B의 오른쪽 자식을 A의 오른쪽 자식으로 만든다.
  • A를 B의 왼쪽 자식 노드로 만든다.

LR 회전

RL 회전

LR 회전과 RL 회전은 균형 상태를 유지하기 위해 2회 회전이 필요하며, 이를 이중 회전이라 한다. 탐색의 순서를 유지하면서 LR 회전은 왼쪽-오른쪽 회전하며, RL 회전은 오른쪽-왼쪽 회전한다. 재호출을 통해 구현할 수 있다.

rotate_LR(A)

  • B <- A의 왼쪽 자식
  • rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
  • rotate_LL(A)
    rotate_RL(A)
  • B <- A의 왼쪽 자식
  • rotate_RR(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
  • rotate_LL(A)

모든 회전의 경우 탐색의 순서는 그대로 유지한다. 순서가 변하지 않음.

*Geeks for geeks 참조하세요.
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

Leet code 문제 풀이

https://leetcode.com/problems/balanced-binary-tree/

문제 설명

이진 트리가 주어지면 높이 균형이 맞는지 확인합니다.
이 문제에서 높이 균형 이진 트리는 다음과 같이 정의됩니다.
모든 노드의 왼쪽 및 오른쪽 하위 트리의 높이가 1 이하로 다른 이진 트리.

문제 예시

문제 풀이

트리의 모든 노드의 왼쪽 및 오른쪽 하위 트리의 높이가 2이상 차이가 날 경우 boolean값인 False, 차이가 1이하일 경우 True로 반환한다. 높이 값을 구하는 함수와 균형 상태를 확인하는 함수로 구현한다.

 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  	// 균형 상태 확인하는 함수
    bool checkBalanced(TreeNode* root) {
        return (checkheight(root) != -1);
    }
	// 높이 값을 구하는 함수
    int checkheight(TreeNode* root) {
        if (root == NULL) return 0;
  
        int left_height =  checkheight(root->left);
        if (left_height == -1) return -1;

        int right_height = checkheight(root->right);
        if (right_height == -1) return -1;
  
		// abs함수:절대값 구하는 함수
        if (abs(left_height - right_height) > 1) return -1; 

        return 1 + max(left_height, right_height);
    }
};
profile
rlawlgus
Hello
이전 포스트

BinarySearchTree

다음 포스트

Generics

0개의 댓글