[C 자/알] 이진 트리와 이진 힙

노드 기반 자료구조
노드 기반 자료구조는 배열의 정적 길이의 제약과

중간 삽입/삭제 시간복잡도를 해결한 자료구조로 링크드리스트가 대표적이다
하지만 링크드리스트도 탐색은 O(N)이 걸리기 때문에 

이를 해결하기 위해

1차원의 링크드리스트를 2차원 계층구조로 만든 것 트리 구조이다

 

트리(Tree)
노드 기반 계층구조를 가진 자료구조이다
트리의 노드들은 위치에 따라 각각 부모와 자식 관계를 가지고 있다

트리 관련 용어
- 루트 노드 (Root Node): 트리의 최상단 노드
- 리프 노드 (Leaf Node): 자식 정점이 없는 정점

- 서브 트리 (Subtree): 특정 노드 기준으로 해당 노드의 후손 노드들
- 높이 (Height): 계층의 수
- 레벨 (Level): 루트노드가 Level 0, 루트노드의 자식이 Level 1,... 이런 식으로 Level이 증가

 

이진 트리(Binary Tree)
모든 노드가 최대 2개의 자식을 갖는 트리이다
각각의 자식들을 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 구분된다

 

이진 탐색 트리(Binary Search Tree)

탐색에 최적화된 이진 트리이다
저장하고자 하는 데이터 값이 작으면 왼쪽 서브트리에,
크면 오른쪽 서브트리에 저장하는 방식으로 자료를 저장한다
이진 탐색처럼 탐색에 O(logN) 시간 복잡도가 소모된다

또한, 마지막 레벨을 제외한 모든 노드에서 반드시 2개의 자식 노드를 갖는 트리를

완전 이진 트리(Complete Binary Tree)라고 한다

 

이진 탐색 트리 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct Node Node_t;
struct Node
{
    int Data;
    Node_t* LeftChild;
    Node_t* RightChild;
};

void Insert(Node_t* InCurrentNode, int InData)
{
    assert(NULL != InCurrentNode);

    if (InData < InCurrentNode->Data)
    {
        if (NULL == InCurrentNode->LeftChild)
        {
            InCurrentNode->LeftChild = (Node_t*)malloc(sizeof(Node_t));
            InCurrentNode->LeftChild->Data = InData;
            InCurrentNode->LeftChild->LeftChild = NULL;
            InCurrentNode->LeftChild->RightChild = NULL;
        }
        else
        {
            Insert(InCurrentNode->LeftChild, InData);
        }
    }
    else
    {
        if (NULL == InCurrentNode->RightChild)
        {
            InCurrentNode->RightChild = (Node_t*)malloc(sizeof(Node_t));
            InCurrentNode->RightChild->Data = InData;
            InCurrentNode->RightChild->LeftChild = NULL;
            InCurrentNode->RightChild->RightChild = NULL;
        }
        else
        {
            Insert(InCurrentNode->RightChild, InData);
        }
    }
}

Node_t* Find(Node_t* InCurrentNode, int InData)
{
    if (NULL == InCurrentNode)
    {
        return NULL;
    }

    if (InData == InCurrentNode->Data)
    {
        return InCurrentNode;
    }

    if (InData < InCurrentNode->Data)
    {
        return Find(InCurrentNode->LeftChild, InData);
    }
    else
    {
        return Find(InCurrentNode->RightChild, InData);
    }
}

void Destroy(Node_t* InCurrentNode)
{
    if (NULL == InCurrentNode)
    {
        return;
    }

    Destroy(InCurrentNode->LeftChild);
    Destroy(InCurrentNode->RightChild);

    free(InCurrentNode);
    InCurrentNode = NULL;
}

int main(void)
{
    size_t i = 0, InputCount = 0;
    int Data = 0;
    Node_t* BST = (Node_t*)malloc(sizeof(Node_t));
    BST->Data = 5;
    BST->LeftChild = NULL;
    BST->RightChild = NULL;

    scanf("%zu", &InputCount);
    for (i = 0u; i < InputCount; ++i)
    {
        scanf("%d", &Data);
        Insert(BST, Data);
    }

    Node_t* FoundNode = Find(BST, 7);
    if (NULL != FoundNode)
    {
        printf("Find(7): %d\n", FoundNode->Data);
    }
    else
    {
        printf("Find(7): None\n");
    }

    FoundNode = Find(BST, 99);
    if (NULL != FoundNode)
    {
        printf("Find(99): %d\n", FoundNode->Data);
    }
    else
    {
        printf("Find(99): None\n");
    }

    Destroy(BST);

    return 0;
}

 

---

 

 

이진 힙(Binary Heap)
힙 속성을 만족하는 완전 이진 트리를 이진 힙이라고 부른다

힙 속성(Heap Property)
1. 루트 노드는 항상 최대값 또는 최소값이다
2. 최대 힙 속성(Max Heap Property)
: 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다
3. 최소 힙 속성(Min Heap Property)
: 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같다
4. 완전 이진 트리이기 때문에 트리의 높이는 logN이다
  
이진 탐색 트리 vs. 이진 힙

	이진 탐색 트리	힙
트리의 분류	이진 트리	완전 이진 트리
원소 중복 여부	중복 불가능	중복 가능
원소 정렬 여부	정렬 됨 (중위 탐색 시)	정렬 안됨
빠른 원소 탐색	지원 (이진 탐색, O(logN))	미지원 (순차 탐색, O(N))
원소의 삽입/삭제	O(logN) or O(N)	O(logN)
최대값/최소값 참	O(logN) or O(N)	O(1)

이진 힙 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

// 함수 호출에 의한 오버헤드를 줄이기 위함.
#define PARENT(INDEX) (INDEX / 2)
#define LEFT(INDEX) (INDEX * 2)
#define RIGHT(INDEX) (INDEX * 2 + 1)

enum
{
    FALSE = 0,
    TRUE = 1,
    MAXCOUNT = 1024
};

typedef struct Heap
{
    int Data[MAXCOUNT];
    size_t Count;
} Heap_t;

void Swap(int* LHS, int* RHS);
void HeapifyUp(Heap_t* InHeap, size_t InIndex);
void Push(Heap_t* InHeap, int InData);
int Top(Heap_t* InHeap);
int Size(Heap_t* InHeap);
int IsEmpty(Heap_t* InHeap);
void HeapifyDown(Heap_t* InHeap, size_t InIndex);
int Pop(Heap_t* InHeap);

int main(void)
{
    Heap_t Heap = {
        0,
    };
    Heap.Count = 1;
    Push(&Heap, 10);
    Push(&Heap, 5);
    Push(&Heap, 15);
    Push(&Heap, 7);
    Push(&Heap, 3);
    Push(&Heap, 9);
    Push(&Heap, 14);
    Push(&Heap, 8);
    Push(&Heap, 2);
    Push(&Heap, 4);

    while (FALSE == IsEmpty(&Heap))
    {
        printf("%d, ", Pop(&Heap));
    }

    return 0;
}

void Swap(int* LHS, int* RHS)
{
    int Temp = *LHS;
    *LHS = *RHS;
    *RHS = Temp;
}

void HeapifyUp(Heap_t* InHeap, size_t InIndex)
{
    if (1 < InIndex && InHeap->Data[PARENT(InIndex)] < InHeap->Data[InIndex])
    {
        Swap(&InHeap->Data[PARENT(InIndex)], &InHeap->Data[InIndex]);
        HeapifyUp(InHeap, PARENT(InIndex));
    }
}

void Push(Heap_t* InHeap, int InData)
{
    assert(InHeap->Count < MAXCOUNT);

    InHeap->Data[InHeap->Count++] = InData;
    HeapifyUp(InHeap, InHeap->Count - 1);
}

int Top(Heap_t* InHeap)
{
    return InHeap->Data[1];
}

int Size(Heap_t* InHeap)
{
    return InHeap->Count - 1;
}

int IsEmpty(Heap_t* InHeap)
{
    if (1 <= Size(InHeap))
    {
        return FALSE;
    }
    return TRUE;
}

void HeapifyDown(Heap_t* InHeap, size_t InIndex)
{
    size_t Biggest = InIndex;

    if (LEFT(InIndex) < InHeap->Count && InHeap->Data[Biggest] < InHeap->Data[LEFT(InIndex)])
    {
        Biggest = LEFT(InIndex);
    }

    if (RIGHT(InIndex) < InHeap->Count && InHeap->Data[Biggest] < InHeap->Data[RIGHT(InIndex)])
    {
        Biggest = RIGHT(InIndex);
    }

    if (Biggest != InIndex)
    {
        Swap(&InHeap->Data[InIndex], &InHeap->Data[Biggest]);
        HeapifyDown(InHeap, Biggest);
    }
}

int Pop(Heap_t* InHeap)
{
    int ReturnedData = InHeap->Data[1];
    InHeap->Data[1] = InHeap->Data[--InHeap->Count];
    HeapifyDown(InHeap, 1);
    return ReturnedData;
}