오늘은 알고리즘 구조 중 하나인 트리구조에 대해 수강했다.
트리 란?
몇가지 제약이 있는 방향그래프의 일종이다. 하나의 Root에서 하위로 뻗어나가는 구조를 가지고있다. 가장 상위에 존재하는 정점을 Root라고 부르며, 각 정점을 Node라고 부르며, 자식이 없는 Node를 Leaf Node라고 부른다. 또한 특이한 점으로는 트리에는 Level이란 것이 존재하는데, Root로부터 몇번째 깊이에 있는지를 표현하는 것이다. 그리고 한 정점에서 뻗어나가는 간선을 Degree 혹은 차수라고 부른다.
트리의 가장 큰 특징으로는 Root를 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
이 특징으로 인해 다른 특징들이 발생하게 되는데, 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
Root에서 특정 정점으로가는 경로는 유일하다. 이 두가지의 특징은 모두 하나의 부모정점만을 가지는 트리의 특징 때문이다.
트리의 종류 중 이진트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.
각 이진 트리, 완전 이진 트리, 포화 이진 트리, 편향 트리로 구분되며
이진 트리는 정점이 최대 2개의 자식 정점을 가지는 트리를 의미한다.
완전 이진트리는 하나의 정점을 제외하고는 전부 2개의 자식을 가지는 트리를 말한다.
포화 이진 트리는 모든 정점이 전부 2개의 자식을 가지는 트리를 말한다.
편향트리는 한 방향으로만 정점이 이어진 것을 말한다.
이진트리의 특징으로는 아래와 같다.
정점이 N개인 포화 또는 완전 이진 트리의 높이는 log N이다. 이는 이진트리는 이진법을 따르기 때문이다.
높이가 H인 포화 이진트리는 2^h -1 개의 정점을 가지는데 이진법을 생각하면 간단하다.
이진트리의 구현은 그래프의 일종이기 때문에 그래프와 마찬가지로 인접 행렬, 인접 리스트 두 가지 방식으로 트리를 표현할 수 있다.
이진 트리를 자바스크립트 배열로 구현할 때, 몇가지만 알고있으면 충분히 구현 가능하다.
index * 2를 하면 왼쪽 정점이고 index*2 + 1을하면 오른쪽 정점이 된다. 부모의 정점을 알고싶다면 index를 2로나누고 소숫점을 버리면 된다.
이진 트리를 연결리스트로 구현하는 것 또한 어렵지 않다.
기존의 연결리스트의 next자리에 left와 right를 넣고 값을 계속 연결시켜주면 이진트리가 완성된다
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 알고리즘 강의 10일차 - 힙(heap)의 기초 (0) | 2023.03.16 |
|---|---|
| 알고리즘 강의 10일차 - 잠시 휴식 (0) | 2023.03.15 |
| 알고리즘 강의 8일차 - 그래프의 기초 (0) | 2023.03.13 |
| 알고리즘 강의 7일차 - 해시테이블 기초 (0) | 2023.03.10 |
| 알고리즘 강의 6일차 - 큐(Queue)의 기초와 알고리즘 (0) | 2023.03.09 |