본문 바로가기
KraftonJungle2기/Today I Learned

[TIL] LinkedList & AVL Tree (with C)

by SooooooooS 2023. 5. 5.
728x90

1. 연결리스트(Linked List)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
  • 종류
    • 단일 연결 리스트
      • 각 노드에 data 공간과 한개의 포인터 공간 존재
      • 포인터는 다음 노드를 가리킨다.
    • 이중 연결 리스트
      • 단일 연결 리스트와 비슷하지만 두개의 포인터 공간 존재
      • 포인터는 현재 노드의 앞의 노드와 뒤의 노드를 가리킨다.
    • 원형 연결 리스트
      • 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조

https://ko.wikipedia.org/wiki/연결_리스트

★ 단일 연결리스트 구현해보기(C언어) ★

1. header file - linkedlist_node.h

#pragma once

// 연결 리스트 노드
typedef struct node
{
    int data; // 값 저장
    struct node *link; //다음 노드
}node;

// 리스트 시작 노드
typedef struct linkhead
{
    node *head;
}linkhead;

//사용할 함수 정의 -> linkedlist_node.c 에 구현
linkhead* createLinkedList(void);
void freeLinkedList(linkhead *h);
void printList(linkhead *h);
void insertFirstNode(linkhead *h, int x);
void insertMiddleNode(linkhead *h, node *pre, int x);
void insertLastNode(linkhead *h, int x);
void deleteNode(linkhead *h, node *p);
node *searchNode(linkhead *h, int x);

2. 실시간 함수 - linkedlist_node.c

#include "linkedlist_node.h" //앞에서 만든 헤더파일 삽입
#include <stdlib.h>
#include <stdio.h>

// 공백 연결 리스트 생성
linkhead* createLinkedList(void) {
    //리스트 헤더를 위한 공간 할당받기
    linkhead *list = (linkhead *)malloc(sizeof(linkhead));
    list->head = NULL;
    return list;
}

//연결리스트의 전체 메모리 해제
void freeLinkedList(linkhead *h){
    node *n;
    while (h->head != NULL) {
        n = h->head;
        h->head = h->head->link;
        free(n); //메모리 해제
        n = NULL;
    }
}

//연결리스트 원소 순서대로 출력
void printList(linkhead *h){
    node *n;
    printf("list 출력 : (");
    n = h->head;
    while (n != NULL)
    {
        printf("%d", n->data);
        n = n->link;
        if (n != NULL) {
            printf(", ");
        }
    }
    printf(")\n");
}

//첫번째 노드로 삽입하는 연산
//삽입하려는 노드가 헤더가 되어야 한다.
void insertFirstNode(linkhead *h, int x){
    node *n = (node *)malloc(sizeof(node));
    n->data = x;
    n->link = h->head;
    h->head = n;
}

//중간 노드(pre 뒤로)로 삽입하는 연산
void insertMiddleNode(linkhead *h, node *pre, int x){
    node *n = (node *)malloc(sizeof(node));
    n->data = x;
    //아직 아무 원소도 없을 경우
    if (h == NULL) {
        n->link = NULL;
        h->head = n;
    }
    //앞에 원소가 없을 경우
    else if(pre == NULL) {
        n->link = h->head;
        h->head = n;
    }
    else {
        n->link = pre->link;
        pre->link = n;
    }
}

//마지막 노드로 삽입하는 연산
void insertLastNode(linkhead *h, int x){
    node *n = (node *)malloc(sizeof(node));
    n->data = x;
    n->link = NULL;
    //원소가 0개일 경우
    if (h->head == NULL) {
        h->head = n;
    }
    else {
        node *tmp = h->head;
        //현재 맨 뒤에 연결된 노드 찾기
        while (tmp->link != NULL) {
            tmp = tmp->link;
        }
        tmp->link = n;
    }
}

//노드 p 삭제하는 연산
void deleteNode(linkhead *h, node *p) {
    node *pre;
    if (h == NULL) { //빈 리스트일 경우
        printf("already empty!\n");
        return;
    }
    // 한개의 노드만 갖고 있을 경우
    if (h->head->link == NULL) {
        free(h->head);
        h = NULL;
        return;
    }
    //p가 없을 경우
    if (p == NULL) {
        printf("current node not exist!\n");
        return;
    }
    pre = h->head;
    //p 노드 찾기
    while(pre->link != p) {
        pre = pre->link;
    }
    //연결이 끊어지지 않도록 뒤의 노드와의 연결
    pre->link = p->link;
    free(p);
}

//리스트에서 x 탐색
node *searchNode(linkhead *h, int x) {
    node *tmp = h->head;
    while (tmp != NULL) {
        if (tmp->data == x) {
            return tmp;
        }
        tmp = tmp->link;
    }
    return tmp;
}

3. main()함수 - ex.c

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

int main(void) {
    linkhead *h;

    h = createLinkedList();
    printf("linkedlist에 1, 2, 3 삽입하기\n");
    insertLastNode(h, 1);
    insertLastNode(h, 2);
    insertLastNode(h, 3);
    printList(h);

    printf("2 노드 탐색하기\n");
    node *two = searchNode(h, 2);
    if (two == NULL) {
        printf("no exist\n");
    }
    else {
        printf("exist!\n");
        printf("2 노드 뒤에 4 노드 삽입하기\n");
        insertMiddleNode(h, two, 4);
        printList(h);

        printf("2 노드 삭제하기\n");
        deleteNode(h, two);
        printList(h);
        return 0;
    }
}

위의 코드 출력 화면

실제 실행 파일과 헤더파일을 나눠서 구현해보았다.
▶ header file : 컴파일러에 의해 다른 소스 파일에 자동으로 포함된 소스 코드의 파일
    #define, enum, struct 헤더부, 클래스 선언부, 함수 형 선언 등과 같이 형을 알리는 형태가 일반적이다.

c언어 헤더파일의 일반적인 형태 - https://ko.wikipedia.org/wiki/헤더_파일

gcc를 이용하여 실행파일을 생성하고 실행할 때 주의할 점은 
gcc ex.c linkedlist_node.c -o ex
위와 같이 두개의 c파일을 컴파일하고 ex라고 하는 실행파일을 생성한다.
./ex 명령어를 입력하여 위의 코드를 실행한다.

< 참고 >

🔗 https://ko.wikipedia.org/wiki/헤더_파일

🔗 https://velog.io/@kysung95/자료구조론-C로-연결리스트를-만들어보자

2. 균형 이진 탐색 트리(AVL 트리)

자가 균형 이진 탐색 트리
스스로 균형을 잡는 데이터 구조
두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다.
최악의 경우 O(log n)

https://ko.wikipedia.org/wiki/AVL_트리

★ Balance Factor(BF) ★

  • BF = height(left) - height(right)
  • BF = 1 : 왼쪽 서브트리 > 오른쪽 서브트리보다 한단계 높다.
  • BF = 0 : 왼쪽 서브트리 = 오른쪽 서브트리 높이가 같다.
  • BF = -1 : 왼쪽 서브트리 < 오른쪽 서브트리보다 한단계 낮다.
// 균형인수를 구하는 연산
int getBF(node *p) {
    if (p == NULL) {
        return 0;
    }
    return getHeight(p->left) - getHeight(p->right);
}

★ height를 구하는 방식 ★

  •  자식 노드를 가지고 있는 부모노드의 개수를 체크하여 높이 확인
//서브 트리의 높이를 구하는 연산
int getHeight(node *p) {
    int height = 1;
    if (!p) {
        return 0;
    }
    else if (p->left == NULL && p->right == NULL) {
        return 0;
    }
    else if (p->left != NULL) {
        height += getHeight(p->left);
    }
    else if (p->right != NULL) {
        height += getHeight(p->right);
    }
    return height;
}

 

★ Rotation  ★

▶ LL

  1. y->right 를 z 로 변경
  2. z->left 를 원래 y->right 에 있던 서브트리로 변경
node* LL_rotate(node *parent) {
    node *root = parent->left;
    parent->left = root->right;
    root->right = parent;
    return root;
}

▶ RR

  1. y->left 를 z 로 변경
  2. z -> right 를 원래 y->left 에 있던 서브트리로 변경
node* RR_rotate(node *parent) {
    node *root = parent->right;
    parent->right = root->left;
    root->left = parent;
    return root;
}

▶ LR

  1. y에 대해 RR_rotate() 실행하여 x를 z의 왼쪽 자식으로 만든다.
  2. z에 대해 LL_rotate() 실행한다.
node* LR_rotate(node *parent) {
    node *left = parent->left;
    left = RR_rotate(left);
    return LL_rotate(parent);
}

▶ RL

  1. y 에 대해 LL_rotate() 를 실행하여 x를 z의 오른쪽 자식으로 만든다.
  2. z 에 대해 RR_rotate()를 실행한다.
node* RL_rotate(node *parent) {
    node *right = parent->right;
    right = LL_rotate(right);
    return RR_rotate(parent);
}

★ 균형 맞추기 ★

//불균형이 발생한 경우 회전 연산 호출
//이중 포인터 사용
node* rebalance(node **p) {
    int bf = getBF(*p);
    // 현재 노드의 bf가 2 이상일 경우 - 양수 = 왼쪽
    if (bf > 1) {
        // 왼쪽 노드의 bf가 양수일 경우 = 왼쪽
        if (getBF((*p)->left) > 0) {
            *p = LL_rotate(*p);
        }
        else {
            *p = LR_rotate(*p);
        }
    }
    //현재 노드의 bf가 -2 이하일 경우 - 음수 = 오른쪽
    else if (bf < -1) {
        // 오른쪽 노드의 bf가 음수일 경우 = 오른쪽
        if (getBF((*p)->right) < 0) {
            *p = RR_rotate(*p);
        }
        else {
            *p = RL_rotate(*p);
        }
    }
    return *p;
}

★ 노드 삽입 ★

//AVL 트리에 노드 삽입 -> rebalance() 호출
//이중 포인터 사용
node* insertNode(node **root, int x) {
    if (*root == NULL) { //현재 아무것도 없을 경우
        *root = (node *)malloc(sizeof(node));
        (*root)->data = x;
        (*root)->left = NULL;
        (*root)->right = NULL;
    }
    // root보다 작은 값일 경우 -> 왼쪽
    else if(x < (*root)->data) {
        // 이중 포인터를 함수의 인자로 받기 때문에 주소값 넘겨주기
        (*root)->left = insertNode(&((*root)->left), x);
        *root = rebalance(root); //균형 맞추기
    }
    // root보다 큰 값일 경우 -> 오른쪽
    else if(x > (*root)->data) {
        // 이중 포인터를 함수의 인자로 받기 때문에 주소값 넘겨주기
        (*root)->right = insertNode(&((*root)->right), x);
        *root = rebalance(root); //균형 맞추기
    }
    else {
        printf("same value exist!\n");
        return 0;
    }
    return *root;
}

★ 전체 코드 - 이중 포인터 사용해보는 코드 ★

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

typedef struct node
{
    int data;
    struct node *left;
    struct node *right;
} node;

//이진 탐색 트리를 중위 순회하면서 출력
void display(node *root) {
    if (root != NULL) {
        display(root->left);
        printf("%d ", root->data);
        display(root->right);
    }
}

// 값이 x인 노드의 위치 탐색
node* searchBST(node *root, int x) {
    node *p = root;
    int count = 0;
    while (p != NULL)
    {
        count++;
        if (x < p->data)
        {
            p = p->left;
        }
        else if (x > p->data) {
            p = p->right;
        }
        else {
            printf("%d번째에서 search success!\n", count);
            return p;
        }
    }
    count++;
    printf("%d번째에서 search fail\n", count);
    return p;
}

node* LL_rotate(node *parent) {
    node *root = parent->left;
    parent->left = root->right;
    root->right = parent;
    return root;
}

node* RR_rotate(node *parent) {
    node *root = parent->right;
    parent->right = root->left;
    root->left = parent;
    return root;
}

node* LR_rotate(node *parent) {
    node *left = parent->left;
    left = RR_rotate(left);
    return LL_rotate(parent);
}

node* RL_rotate(node *parent) {
    node *right = parent->right;
    right = LL_rotate(right);
    return RR_rotate(parent);
}

//서브 트리의 높이를 구하는 연산
int getHeight(node *p) {
    int height = 1;
    if (p == NULL) {
        return 0;
    }
    else if (p->left == NULL && p->right == NULL) {
        return 0;
    }
    else if (p->left != NULL) {
        height += getHeight(p->left);
    }
    else if (p->right != NULL) {
        height += getHeight(p->right);
    }
    return height;
}

// 균형인수를 구하는 연산
int getBF(node *p) {
    if (p == NULL) {
        return 0;
    }
    return getHeight(p->left) - getHeight(p->right);
}

//불균형이 발생한 경우 회전 연산 호출
//이중 포인터 사용 연습
node* rebalance(node **p) {
    int bf = getBF(*p);
    // 현재 노드의 bf가 2 이상일 경우 - 양수 = 왼쪽
    if (bf > 1) {
        // 왼쪽 노드의 bf가 양수일 경우 = 왼쪽
        if (getBF((*p)->left) > 0) {
            *p = LL_rotate(*p);
        }
        else {
            *p = LR_rotate(*p);
        }
    }
    //현재 노드의 bf가 -2 이하일 경우 - 음수 = 오른쪽
    else if (bf < -1) {
        // 오른쪽 노드의 bf가 음수일 경우 = 오른쪽
        if (getBF((*p)->right) < 0) {
            *p = RR_rotate(*p);
        }
        else {
            *p = RL_rotate(*p);
        }
    }
    return *p;
}

//AVL 트리에 노드 삽입 -> rebalance() 호출
//이중 포인터 사용 연습
node* insertNode(node **root, int x) {
    if (*root == NULL) { //현재 아무것도 없을 경우
        *root = (node *)malloc(sizeof(node));
        (*root)->data = x;
        (*root)->left = NULL;
        (*root)->right = NULL;
    }
    // root보다 작은 값일 경우 -> 왼쪽
    else if(x < (*root)->data) {
        (*root)->left = insertNode(&((*root)->left), x);
        *root = rebalance(root);
    }
    // root보다 큰 값일 경우 -> 오른쪽
    else if(x > (*root)->data) {
        (*root)->right = insertNode(&((*root)->right), x);
        *root = rebalance(root);
    }
    else {
        printf("same value exist!\n");
        return 0;
    }
    return *root;
}

int main(void) {
    node *root = NULL;

    // 트리 생성
    insertNode(&root, 50);
    insertNode(&root, 60);
    insertNode(&root, 70);
    insertNode(&root, 90);
    insertNode(&root, 80);
    insertNode(&root, 75);
    insertNode(&root, 73);
    insertNode(&root, 72);
    insertNode(&root, 78);
    printf("트리 출력하기\n");
    display(root);
    printf("\nAVL Tree에서 70 탐색\n");
    searchBST(root, 70);
    printf("\nAVL Tree에서 72 탐색\n");
    searchBST(root, 72);
    printf("\nAVL Tree에서 77 탐색\n");
    searchBST(root, 77);
}

위의 코드 출력 결과

★ 전체 코드 - 이중 포인터 사용하지 않는 코드 ★

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

typedef struct node
{
    int data;
    struct node *left;
    struct node *right;
} node;

//이진 탐색 트리를 중위 순회하면서 출력
void display(node *root) {
    if (root != NULL) {
        display(root->left);
        printf("%d ", root->data);
        display(root->right);
    }
}

// 값이 x인 노드의 위치 탐색
node* searchBST(node *root, int x) {
    node *p = root;
    int count = 0;
    while (p != NULL)
    {
        count++;
        if (x < p->data)
        {
            p = p->left;
        }
        else if (x > p->data) {
            p = p->right;
        }
        else {
            printf("%d번째에서 search success!\n", count);
            return p;
        }
    }
    count++;
    printf("%d번째에서 search fail\n", count);
    return p;
}

node* LL_rotate(node *parent) {
    node *root = parent->left;
    parent->left = root->right;
    root->right = parent;
    return root;
}

node* RR_rotate(node *parent) {
    node *root = parent->right;
    parent->right = root->left;
    root->left = parent;
    return root;
}

node* LR_rotate(node *parent) {
    node *left = parent->left;
    left = RR_rotate(left);
    return LL_rotate(parent);
}

node* RL_rotate(node *parent) {
    node *right = parent->right;
    right = LL_rotate(right);
    return RR_rotate(parent);
}

//서브 트리의 높이를 구하는 연산
int getHeight(node *p) {
    int height = 1;
    if (p == NULL) {
        return 0;
    }
    else if (p->left == NULL && p->right == NULL) {
        return 0;
    }
    else if (p->left != NULL) {
        height += getHeight(p->left);
    }
    else if (p->right != NULL) {
        height += getHeight(p->right);
    }
    return height;
}

// 균형인수를 구하는 연산
int getBF(node *p) {
    if (p == NULL) {
        return 0;
    }
    return getHeight(p->left) - getHeight(p->right);
}

//불균형이 발생한 경우 회전 연산 호출
node* rebalance(node *p) {
    int bf = getBF(p);
    // 현재 노드의 bf가 2 이상일 경우 - 양수 = 왼쪽
    if (bf > 1) {
        // 왼쪽 노드의 bf가 양수일 경우 = 왼쪽
        if (getBF(p->left) > 0) {
            p = LL_rotate(p);
        }
        else {
            p = LR_rotate(p);
        }
    }
    //현재 노드의 bf가 -2 이하일 경우 - 음수 = 오른쪽
    else if (bf < -1) {
        // 오른쪽 노드의 bf가 음수일 경우 = 오른쪽
        if (getBF(p->right) < 0) {
            p = RR_rotate(p);
        }
        else {
            p = RL_rotate(p);
        }
    }
    return p;
}

//AVL 트리에 노드 삽입 -> rebalance() 호출
node* insertNode(node *root, int x) {
    if (root == NULL) { //현재 아무것도 없을 경우
        root = (node *)malloc(sizeof(node));
        root->data = x;
        root->left = NULL;
        root->right = NULL;
    }
    // root보다 작은 값일 경우 -> 왼쪽
    else if(x < root->data) {
        root->left = insertNode(root->left, x);
        root = rebalance(root);
    }
    // root보다 큰 값일 경우 -> 오른쪽
    else if(x > root->data) {
        root->right = insertNode(root->right, x);
        root = rebalance(root);
    }
    else {
        printf("same value exist!\n");
        return root;
    }
    return root;
}

int main(void) {
    node *root = NULL;

    // 트리 생성
    insertNode(root, 50);
    insertNode(root, 60);
    insertNode(root, 70);
    insertNode(root, 90);
    insertNode(root, 80);
    insertNode(root, 75);
    insertNode(root, 73);
    insertNode(root, 72);
    insertNode(root, 78);

    //연산 실행
    printf("트리 출력하기\n");
    display(root);
    printf("\nAVL Tree에서 70 탐색\n");
    searchBST(root, 70);
    printf("\nAVL Tree에서 72 탐색\n");
    searchBST(root, 72);
    printf("\nAVL Tree에서 77 탐색\n");
    searchBST(root, 77);
}

< 참고 >

🔗 https://ko.wikipedia.org/wiki/AVL_트리

🔗 https://velog.io/@qlwb7187/자료구조-AVL트리-C

🔗 https://dmsitter.tistory.com/64

🔗 https://kjt9109.tistory.com/entry/AVL-Tree-구현

🔗 https://ymcoder.tistory.com/222

 

728x90
저작자표시

'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글

[TIL] Make란? + stack 문제 풀이  (0) 2023.05.07
[TIL] Red-Black Tree 개념(삽입/삭제) + 기계 수준 표현(스택)2  (0) 2023.05.06
[TIL] C언어 공부하기  (0) 2023.05.04
[TIL] 문제 풀이 연습 - two point (with python)  (1) 2023.05.03
[TIL] 동적 프로그래밍 문제 풀이3  (0) 2023.05.02

관련글

티스토리툴바