# 트리 구조

### 트리의 구조와 관련 용어

* 트리 : 노드(node) + 가지(edge)
* 루트 : 맨 위에 있는 노드
* 리프 : 맨 아래에 있는 노드. \[ = 단말 노드(terminal node), 외부 노드(external node) ]
* 비단말 노드 : 리프를 제외한 노드. \[ = 내부 노드(internal node) ]
* 형제 : 부모가 같은 노드
* 조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드
* 자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
* 레벨 : 루트에서 얼마나 멀리 떨어져 있는지 (루트는 0)
* 차수 : 각 노드가 갖는 자식의 수
* 높이 : 루트에서 가장 멀리 있는 리프까지의 거리

### 순서 트리와 무순서 트리

* 순서 트리(ordered tree): 형제 노드의 순서 관계가 있음
* 무순서 트리(unordered tree): 형제 노드끼리 순서 구분 없음

#### 순서 트리의 검색

<figure><img src="/files/DkvPZXfwDfWwwDQrSNbY" alt=""><figcaption></figcaption></figure>

[이미지 출처](https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS-lp8zywtn)

* 너비 우선 검색(breadth-first search): 낮은 레벨부터 왼쪽에서 오른쪽으로 검색
* 폭 우선 검색, 가로 검색, 수평 검색이라고도 한다
* 같은 레벨에 검색하지 않은 노드가 있다면 먼저 검색한다
* 완전 이진 트리를 리스트로 구현했다면 인덱스 0부터 끝까지 +1하면서 순회 검색

<figure><img src="/files/M0bdqQdNGsXMPGzhWld0" alt=""><figcaption></figcaption></figure>

[이미지 출처](https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS)

* 깊이 우선 검색(depth-first search): 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로
* 세로 검색, 수직 검색이라고도 한다
* 아래 레벨 노드에 검색 안한게 있으면 일단 아래로 내려갔다온다

### 전위, 중위, 후위 순회

전위 순회

> 노드 방문 → 왼쪽 자식 → 오른쪽 자식

중위 순회

> 왼쪽 자식 → 노드 방문 → 오른쪽 자식

후위 순회

> 왼쪽 자식 → 오른쪽 자식 → 노드 방문

<figure><img src="/files/jY9PRr2eP6RiVt6n4d74" alt=""><figcaption></figcaption></figure>

<https://www.youtube.com/watch?v=WLvU5EQVZqY>

어려워서 이해 못했는데 인도인이 알려줬다.

일단 탐색 순서는 그려진 대로의 경로가 고정.\
\- 전위 순회 : 처음 만난 노드를 바로 기록\
\- 중위 순회 : 두번 만난 노드만 기록\
\- 후위 순회 : 세번 만난 노드만 기록

### 이진 트리

가지 2개까지만 가질 수 있는 트리.

어렵게 말하면, 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리.

### 완전 이진 트리

대충 딱 보면 빈틈 없이 꽉 차있는 트리

어렵게 말하면, 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리

* 마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차 있다.
* 마지막 레벨에 한해서 반드시 끝까지 채우지 않아도 된다.

### 균형 검색 트리

* 이진 검색 트리는 키의 오름차순으로 노드가 삽입되면 트리의 높이가 깊어지는 단점이 있다.
* 예를 들어, 1, 2, 3, 4, 5 순으로 노드를 삽입하면 직선 모양이 된다.
* 균형 검색 트리 : 높이를 O(log n)으로 제한하여 고안된 검색 트리
* 이진 균형 검색 트리 : AVL 트리, 레드블랙 트리 등
* (이진 아닌) 균형 검색 트리 : B 트리, 2-3 트리

### 이진 검색 트리

이진 검색 트리는 모든 노드가 다음 조건을 만족해야 함.

> * 왼쪽 서브트리의 노드의 키값은 자신의 노드 키값보다 작아야 한다.
> * 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.

따라서 키값이 같은 노드는 복수로 존재하면 안됨.\
모든 키값은 고유해야 함. 안 그럼 규칙 위배함.

> * 구조가 단순하다.
> * 중위 순회의 깊이 우선 검색을 통하여 노드값을 오름차순으로 얻을 수 있다.
> * 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다.
> * 노드를 삽입하기 쉽다.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-5.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.