트리(Tree)

트리란?

  -> 계층적 관계를 표현하는 자료구조

  -> 하나의 중심을 기점으로 뻗어나가는 구조

트리 용어

- 노드(Node): 트리의 구성 요소(기본 단위) => A, B, C, D, E, F, G, H, I, J

- 간선: 노드와 노드를 연결하는 선

- 루트 노드(Root): 트리 구조에서 최상위에 존재하는 노드 => A

- 단말 노드(Leaf Node): 아래로 또 다른 노드가 연결되어 있지 않은 노드 => H, I, J, F, G

- 내부 노드: 단말 노드를 제외한 모든 노드 => A, B, C, D, E

 

- 서브 트리(Sub-tree): 트리에서 일부를 떼어낸 트리

- 레벨(level): 루트 노드를 기준으로 레벨 0부터 자식 노드로 가면서 레벨이 증가한다.

- 높이: 최대 레벨의 값(0부터 셌을 때)

- 부모-자식 관계(Parent Node-Child Node): 계층적으로 위-아래에 있는 관계

- 형제 관계(Siblings): 같은 부모 노드를 가지는 동일 레벨의 관계

 

이진 트리

조건:

- 루트 노드를 중심으로 2개의 서브트리로 나누어진다.

- 나누어진 서브 트리도 전부 이진 트리이다. 

- 단말 노드도 이진 트리라고 간주한다 -> 공집합 노드(빈 노드)로 채움(5, 11, 9 밑에 공노드로 채워짐)

 

이진 탐색 트리

-> 데이터의 저장 규칙이 있는 이진 트리

조건: 부모 노드를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 저장

 

이진 탐색 트리 삽입

1. 루트 노드부터 비교하면서 삽입 데이터가 작으면 왼쪽으로, 크면 오른쪽으로 이동하면서 자리를 찾음(탐색도)

2. 1번 반복

이진 탐색 트리 삭제(3가지 경우)

1. 삭제할 노드가 단말 노드인 경우

  -> 부모노드에서 해당 단말노드를 삭제한다.

2. 삭제할 노드가 1개의 자식 노드(서브트리)를 갖는 경우

  -> 해당 노드를 삭제하고 서브 트리를 부모 노드(삭제된 위치)에 붙여준다. (위치 그대로)

3. 삭제할 노드가 2개의 자식 노드(서브트리)를 갖는 경우

  1) 해당 노드의 서브트리 기준 왼쪽에서 가장 큰 값 또는 오른쪽에서 가장 작은 값을 찾는다.

  2) 둘 중에 하나의 값으로 기존 노드를 채운다. (보통 오른쪽에서 작은 값을 선택한다고 함.)

  3) 찾았던 값의 자리를 삭제한다. (새로운 삭제)