[1주차 TIL] KnockOn Bootcamp 트리

• 트리의 개념
• 트리의 순회 방법
• 이진 트리, 완전 이진 트리
• 이진 탐색 트리

1. 트리의 개념

• 나무를 닮은 자료구조

1-1. 트리의 구성 요소

 

트리의 구성 요소: 뿌리, 가지, 잎 모두 똑같은 노드이나 위치에 따라 명칭이 다르다.

구성 요소

• 뿌리(Root): 가장 위에 있는 노드
• 가지(Branch): 뿌리와 잎 사이
• 잎(Leaf): 끝에 있음(단말:terminal)이라고 하기도 함.

• 부모(parents): A는 B,C,D의 부모
• 자식(Children): B,C,D는 A의 자식
• 형제(Sibling): B,C,D는 형제

---

경로

• 경로: 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서
  example) A에서 K까지의 경로: A,B,E,K
• 경로의 길이(length): 출발 노드에서 목적 노드까지 거쳐야 하는 노드의 개수
  ex) A-K: 3
• 깊이(Depth): 뿌리 노드에서 해당 노드까지 이르는 경로의 길이
  ex) K: 3
• 레벨(level): 깊이가 같은 노드의 집합
  ex) level 3: K, L, M
• 높이(height): 가장 깊은 곳에 있는 잎 노드까지의 깊이
  ex) 3
• 차수(Degree): 노드의 차수->그 노드의 자식 노드 개수, 트리의 차수->트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수

---

2. 트리의 기본 연산

2-2. 노드 선언

Left Child, Right Sibling 형태 표현법(LCRS)에서
노드 구조체는

typedef char ElementType;
typedef struct tagLCRSNode {
  struct tagLCRSNode *LeftChild;
  struct tagLCRSNode *RightSibling;
  ElementType Data;
} LCRSNode;

와 같이 데이터 필드와 Left Child, Right Sibling 두 개 포인터로 구성된다.

2-3. 노드 생성/소멸

//노드 생성
LCRSNode *LCRS_CreateNode(ElementType NewData) {
  LCRSNode *NewNode = (LCRSNode *)malloc(sizeof(LCRSNode));
  NewNode->LeftChild = NULL;
  NewNode->RightSibling = NULL;
  return NewNode;
}
//노드 소멸
void LCRS_DestroyNode(LCRSNode *Node) { free(Node); }

• 노드 생성: 자유 저장소에 LCRSNode 구조체의 크기만큼 메모리를 할당하고 매개변수 NewData를 Data에 저장한 후 노드 메모리 주소 반환
• 노드 소멸: 자유 저장소에서 할당했던 메모리만 해제하면 됨

2-4. 자식 노드 연결

void LCRS_AddChildNode(LCRSNode *Parent, LCRSNode *Child) {
//자식 노드가 있는지 검사
  if (Parent->LeftChild == NULL)
  //자식 노드가 없으면 왼쪽노드에 바로 저장
    Parent->LeftChild = Child;
  else {
  //자식 노드가 있는 경우
    LCRSNode *TempNode = Parent->LeftChild;
    while (TempNode->RightSibling != NULL)
    //RightSibling을 이용해 가장 오른쪽의 자식 노드를 찾고 Child를 가장 오른쪽 자식 노드의 RightSibling노드에 대입
      TempNode = TempNode->RightSibling;
    TempNode->RightSibling = Child;
  }
}

위 함수 과정을 통해 부모 노드는 자식을 하나 추가한다.

2-5. 트리 출력

void LCRS_PrintTree(LCRSNode *Node, int Depth) {
//들여쓰기
  for (int i = 0; i < Depth - 1; i++) {
    printf("   ");
    if (Depth > 0) //자식 노드 여부
      printf("+--");
      //노드 데이터 출력
    printf("%c\n", Node->Data);
    if (Node->LeftChild != NULL)
      LCRS_PrintTree(Node->LeftChild, Depth + 1);
    if (Node->RightSibling != NULL)
      LCRS_PrintTree(Node->RightSibling, Depth);
  }
}

구성된 트리를 출력하는 코드

---

3. 이진 트리

앞쪽 코드에서 구현한 트리는 노드의 자식 노드 개수에 제한이 없었으나 이진트리는 하나의 노드가 자식 노드를 2개까지만 가질 수 있다.

3-1. 이진 트리의 종류

• 포화 이진 트리
• 완전 이진 트리
• 이진 탐색 트리

포화 이진 트리

 

위 사진처럼 잎 노드를 제외한 모든 노드가 자식을 2개씩 갖고 있으면 포화 이진 트리라고 한다.

완전 이진 트리

모든 노드가 자식 2개를 갖고 있진 않아도 잎 노드들이 왼쪽부터 차곡차곡 채워져있으면 완전 이진 트리라고 한다.
B처럼 중간에 노드가 빈 트리는 완전 이진 트리가 아니다.

높이 균형 트리

뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2이상 차이 나지 않는 이진 트리

완전 높이 균형 트리

왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 완전히 같은 이진 트리

• 트리의 성능과 모양: 가능한 완전한 모습으로 유지해야 높은 성능을 낼 수 있다. 이진 트리는 컴파일러나 검색과 같은 알고리즘의 뼈대가 되는 특별한 자료구조이므로, 이러한 모양이 중요하다.

3-4. 이진 탐색 트리

• 한마디로 탐색을 위한 이진 트리(이진 탐색)

이진 탐색은 배열에만 사용 가능하기 때문에 링크드 리스트에서 탐색을 위해서 이진 탐색 트리를 쓸 수 있다.

이진 탐색 트리의 특징

• 부모 노드 입장에서 왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 크다.

위와 같은 특징을 통해 탐색이 작동한다.
중앙 요소를 찾아 좌우의 대소르 비교하여 탐색 범위를 정하고 다시 중앙 요소를 찾아 좌우의 요소를 비교하는 것을 반복하여 탐색한다.

예시) 위 트리에서 5를 찾는다고 해보자.
5는 8보다 작으니 왼쪽 노드로, 다시 5는 3보다 크니 오른쪽 노드로 이동하는 것이다.