Data Structure - 4

@Super_E끌림·2025년 7월 12일
Cavl데이터구조이진탐색트리힙
post-thumbnail

  • 이진탐색트리 (BST)

    이진탐색트리란? 정렬된 이진트리의 형태이다.

    이진탐색트리의 속성 (KEY : 노드의 숫자)

    • 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드만 포함됩니다

    • 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드만 포함됩니다.

    • 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다.

    • 중복된 키를 허용하지 않습니다.

      이러한 이진 탐색 트리의 특성 때문에 효율적인 검색이 가능합니다.

      이진탐색트리 구현 - C

      #include <stdio.h>
#include <stdlib.h>

// 노드 구조 정의
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

// 노드 생성 함수
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        perror("Memory allocation failed");
        exit(1);
    }
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 노드 삽입 함수
Node* insertNode(Node* root, int key) {
    if (root == NULL) {
        return createNode(key);
    }

    if (key < root->key)
        root->left = insertNode(root->left, key);
    else if (key > root->key)
        root->right = insertNode(root->right, key);

    return root;
}

// 키 탐색 함수
Node* searchNode(Node* root, int key) {
    if (root == NULL || root->key == key)
        return root;

    if (key < root->key)
        return searchNode(root->left, key);
    else
        return searchNode(root->right, key);
}

// 중위 순회 함수 (In-order Traversal)
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->key);
        inorderTraversal(root->right);
    }
}

// 최소값 노드 찾기 (삭제용)
Node* findMinNode(Node* root) {
    while (root->left != NULL)
        root = root->left;
    return root;
}

// 노드 삭제 함수
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return NULL;

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        // 삭제할 노드 발견
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        // 두 자식이 있는 경우: 오른쪽 서브트리에서 최소값 대체
        Node* temp = findMinNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// 메모리 해제
void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// 직접 구현
int main() {
    
}

  • AVL 트리 (균형 트리)

    균형 트리란? 스스로 균형을 잡는 이진 탐색 트리 형태이다.

    균형 트리의 특징으로는

    • AVL 트리는 이진 탐색 트리의 속성을 가집니다.

    • 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.

    • 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다. → 1<∣x∣1<|x|이면 회전을 진행한다.(차이 : x)

    • AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다.

      회전을 하기 위해서는 BF라는 Balance Factor 값을 구해야 합니다.
      이는 외쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값입니다.

      아래의 그림에서 50의 BF를 구한다고 보면은

      50을 기준으로 왼쪽 서브티리의 높이는 3이고 오른쪽의 서브트리의 높이는 2가 됩니다. 따라서 3-2인 1이 나오게 되는 것입니다.
      여기서 주의 하실 점은 예시로 20의 BF를 구한다고 한다면 20인 노드의 레벨이 0이 됩니다!!! 즉, BF를 구하고자 하는 노드의 높이부터 시작하므로 20의 BF를 구한다고 한다면 20인 노드의 레벨은 L = 0이 됩니다.

      이제부터는 회전에 대해 알아보겠습니다.

      검색, 순회 연산은 BF가 변경되지 않지만 삽입, 삭제에서는 BF가 변경될 수 있습니다.
      삽입 삭제 시 불균형 상태(BF가 -1 ,0, 1이 아닌 경우) 가 되면 AVL트리는 불균형 노드를 기준으로 서브트리의 위치를 변경하는 rotation 작업을 수행하여 트리의 균형을 맞추게 됩니다.

      불균형은 4가지의 형태로 발생하게 되는데 LL,RR,LR,RL이 있다. 이는 각 사황에 따라 회전하는 방향을 달리하여 균형을 맞추게 됩니다.

    1. LL Case

      y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여 균형을 맞춥니다.

      right rotation 수행 과정

      • y노드의 오른쪽 자식 노드를 z노드로 변경합니다.
      • z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경합니다.
      • y는 새로운 루트 노드가 됩니다.

      Right Rotation 구현 - C

      struct node *rightRotate (struct node *z) {
  struct node *y = z->left;
  struct node *T2 = y->right;

// right 회전 수행
  y->right = z;
  z->left = T2;

// 노드 높이 갱신
  z->height = 1 + max(z->left->height, z->right->height);
  y->height = 1 + max(y->left->height, y->right->height);

// 새로운 루트 노드 y를 반환  
  return y;
}

    2. RR Case

      y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여 균형을 맞춥니다.

      left rotation 수행 과정

      • y노드의 왼쪽 자식 노드를 z노드로 변경합니다.
      • z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경합니다.
      • y는 새로운 루트 노드가 됩니다.

      Left Rotaion 구현 - C

      struct node *leftRotate (struct node *z) {
  struct node *y = z->right;
  struct node *T2 = y->left;

// left 회전 수행
  y->left = z;
  z->right = T2;

// 노드 높이 갱신
  z->height = 1 + max(z->left->height, z->right->height);
  y->height = 1 + max(y->left->height, y->right->height);

// 새로운 루트 노드 y를 반환  
  return y;
}

    3. LR Case

      y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춥니다.

      Left-Right Rotaion 구현 - C

      y = z->left;
y = leftRotate(y);
z = rightRotate(z);

    4. RL Case

      y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춥니다.

      Right-Left Rotation 구현 - C

      y = z->right;
y = rightRotate(y);
z = leftRotate(z);

      AVL Tree 구현 - C

      #include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    int height;
} Node;

// 최대값 구하기
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 노드의 높이 반환
int height(Node* node) {
    return (node == NULL) ? 0 : node->height;
}

// 새 노드 생성
Node* create_node(int key) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // 새 노드의 높이는 1
    return node;
}

// 오른쪽 회전 (LL 회전)
Node* right_rotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 회전 수행
    x->right = y;
    y->left = T2;

    // 높이 업데이트
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

// 왼쪽 회전 (RR 회전)
Node* left_rotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 회전 수행
    y->left = x;
    x->right = T2;

    // 높이 업데이트
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

// 균형 인수 계산
int get_balance(Node* node) {
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}

// 삽입 함수
Node* insert(Node* node, int key) {
    // 1. 일반 BST 삽입
    if (node == NULL)
        return create_node(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // 중복 키는 무시
        return node;

    // 2. 높이 업데이트
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. 균형 인수 계산
    int balance = get_balance(node);

    // 4. 회전으로 균형 유지
    // LL
    if (balance > 1 && key < node->left->key)
        return right_rotate(node);

    // RR
    if (balance < -1 && key > node->right->key)
        return left_rotate(node);

    // LR
    if (balance > 1 && key > node->left->key) {
        node->left = left_rotate(node->left);
        return right_rotate(node);
    }

    // RL
    if (balance < -1 && key < node->right->key) {
        node->right = right_rotate(node->right);
        return left_rotate(node);
    }

    return node;
}

// Preorder 순회 (루트 -> 왼쪽 -> 오른쪽)
void preorder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}

// 직접 구현
int main(){

}

  • 힙 (Heap)

    힙이란? 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전이진트리 형태이다.

    힙의 조건으로는

    • 완전이진트리의 형태를 가집니다.
    • 이진탐색트리와 달리 중복값을 허용합니다.
    • 힙은 최대힙(Max heap)과 최소힙(Min heap)으로 나뉘어진다. 최대힙은 자식 노드보다 부모 노드의 값이 크고, 최소힙은 자식 노드보다 부모 노드의 값이 작다.
    • 최소 힙 (Min Heap)

      • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

      • key(부모 노드) <= key(자식 노드)

        최소 힙 구현 - C

        #include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int size;
} MinHeap;

void initMinHeap(MinHeap* h) {
    h->size = 0;
}

void insertMinHeap(MinHeap* h, int value) {
    int i = ++(h->size);

    // shift up
    while (i != 1 && value < h->data[i / 2]) {
        h->data[i] = h->data[i / 2];
        i /= 2;
    }
    h->data[i] = value;
}

int deleteMin(MinHeap* h) {
    if (h->size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    int min = h->data[1];
    int temp = h->data[h->size--];
    int parent = 1, child = 2;

    // shift down
    while (child <= h->size) {
        if (child < h->size && h->data[child] > h->data[child + 1]) {
            child++;
        }
        if (temp <= h->data[child]) break;
        h->data[parent] = h->data[child];
        parent = child;
        child *= 2;
    }
    h->data[parent] = temp;
    return min;
}

// 직접 구현
int main(){

}
    • 최대 힙 (Max Heap)

      • 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

      • key(부모 노드) >= key(자식 노드)

        최대 힙 구현 - C

        #include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int size;
} MaxHeap;

void initMaxHeap(MaxHeap* h) {
    h->size = 0;
}

void insertMaxHeap(MaxHeap* h, int value) {
    int i = ++(h->size);

    // shift up
    while (i != 1 && value > h->data[i / 2]) {
        h->data[i] = h->data[i / 2];
        i /= 2;
    }
    h->data[i] = value;
}

int deleteMax(MaxHeap* h) {
    if (h->size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    int max = h->data[1];
    int temp = h->data[h->size--];
    int parent = 1, child = 2;

    // shift down
    while (child <= h->size) {
        if (child < h->size && h->data[child] < h->data[child + 1]) {
            child++;
        }
        if (temp >= h->data[child]) break;
        h->data[parent] = h->data[child];
        parent = child;
        child *= 2;
    }
    h->data[parent] = temp;
    return max;
}
profile
@Super_E끌림
SoC:) SoC:)
이전 포스트

Data Structure - 3

다음 포스트

Data Structure - 5

0개의 댓글