Study with Me!
Seongmo
Study with Me!
전체 방문자
오늘
어제
  • Computer (126)
    • Computer Science (61)
      • Data Structure (51)
      • Algorithm (6)
      • 선형대수 with C++ (4)
    • Arm Architecture (1)
      • Register (0)
      • Assembly Instruction (1)
    • Linux (30)
      • Linux Kernel (4)
      • 라이브러리 함수 구현하기 (0)
      • 쉘, 쉘 명령어 구현하기 (15)
      • Ubuntu (11)
    • AWS (3)
    • Baekjoon (18)
    • Tools (6)
      • Git & Github (5)
      • Vim (1)
    • 개발 환경 (7)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • STL

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Study with Me!

Seongmo

6-3. 이진 트리의 구현 방법
Computer Science/Data Structure

6-3. 이진 트리의 구현 방법

2023. 7. 24. 03:16

이진 트리를 구현하는 방법은 크게 두 가지가 있다.

배열을 이용하는 방법과 연결 리스트를 이용하는 방법이다.


배열을 이용해 이진 트리를 구현하는 방법

이진 트리의 높이가 h이면 먼저 2h-1개의 공간을 배열로 할당한다.

이진 트리의 '위에서 아래로', '왼쪽에서 오른쪽으로'의 순서대로 번호를 할당한다.

이 번호가 배열의 인덱스로 사용된다.

노드간의 부모/자식 관계를 쉽게 파악하기 위해 노드의 번호는 1부터 사용한다.

노드의 번호를 1부터 사용하면 다음과 같은 장점이 있다.

  • 노드 i 의 부모 노드 인덱스 : i / 2
  • 노드 i 의 왼쪽 자식 노드 인덱스 : 2 * i
  • 노드 i 의 오른쪽 자식 노드 인덱스 : 2 * i + 1

임의의 노드 인덱스 값만 알고 있다면 그 노드의 부모/자식 노드를 쉽게 알 수가 있다.

 

하지만, 배열을 사용했으므로 메모리 낭비와 한정된 크기라는 단점도 함께 따라온다.


연결 리스트를 이용해 이진 트리를 구현하는 방법

연결 리스트를 이용하면 배열을 이용했을 때의 단점이 극복되지만, 구현이 상대적으로 복잡해진다.

연결 리스트로 이진 트리를 구현하면 삽입/삭제 연산 시에 메모리 동적 할당/해제의 과정을 거치기 때문에 트리의 노드들은 메모리 여기저기에 흩어져 있고, 각 노드는 데이터 필드와 링크 필드를 갖는다.

링크 필드는 각각 왼쪽 자식 노드, 오른쪽 자식 노드를 가리키게 된다.

저작자표시 (새창열림)

'Computer Science > Data Structure' 카테고리의 다른 글

6-5. [C++] 이진 트리의 순회(전위/중위/후위/레벨 순회) 구현  (0) 2023.07.24
6-4. [C++] 연결 리스트로 구현한 이진 트리  (0) 2023.07.24
6-2. 이진 트리란?  (0) 2023.07.24
6-1. 트리란?  (0) 2023.07.24
4-4. [C++] 연결 리스트로 구현한 큐  (0) 2023.07.11
    'Computer Science/Data Structure' 카테고리의 다른 글
    • 6-5. [C++] 이진 트리의 순회(전위/중위/후위/레벨 순회) 구현
    • 6-4. [C++] 연결 리스트로 구현한 이진 트리
    • 6-2. 이진 트리란?
    • 6-1. 트리란?
    Study with Me!
    Study with Me!
    Study with Me!

    티스토리툴바