트리 (Tree Data Structure) 기초 , 이진트리와 이진탐색트리

https://blog.naver.com/jhc9639/222289089015

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

---

트리(Tree data Structure)

 

나무 가지를 뒤집어놓은 모양.

트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미.

• 자식 노드와 부모 노드로 이루어진 계층 구조 (회사 조직도 생각하기)
• 무방향 그래프 (즉, 양방향 단방향이 없음)
  • 방향그래프(direct graph)와 무방향그래프(indirect graph) 개념
  • 방향성 있는 간선(directed edge = ark)
• 사이클이 없는 자료구조

간선을 중복해서 사용하지 않고, 어떠한 정점에서 자기 자신으로 돌아올 수 있을 때 “사이클이 있다” 라고 합니다.

• 루트 노드 : 가장 위에 있는 노드 
  • 문제나 면접에서 트리가 주어지면 루트노드부터 탐색하는 게 좋다
• 내부 노드 : 루트노드와 리프 노드 사이에 있는 노드
• 리프 노드 : 자식노드가 없는 노드 

---

트리(Tree data Structure)의 특징

• 부모, 자식 계층 구조를 가진다.
  • 같은 경로 상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드
• V(노드 수) - 1 = E(간선 수)
• 임의의 두 노드 사이의 경로는 유일무이하게 존재한다.
  • 즉, 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없다.
  • 4번에서 9번도 갈 수 있음

---

트리(Tree data Structure)의 높이와 레벨

• 깊이
  • 각각의 노드마다 다르다
  • 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리
  • 4번 노드의 깊이는 2, 9번 노드의 깊이는 3
• 높이
  • 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미
  • 트리의 높이는 3
• 레벨
  • 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미
  • 1번 노드: 0레벨, 4번노드 2레벨 등
• 서브트리
  • 트리 내의 하위 집합. 트리 내의 부분집합
• 숲(forest)
  • 트리로 이루어진 집합

문제의 정의에 따라 다름

---

이진트리(BT, Binary Tree)

 

각각의 노드와 자식 노드 수가 2개 이하로 구성되어 있는 트리를 의미하며 이를 다음과 같이 분류한다.

 

• 정 이진트리 (full binary tree)
  • 자식 노드가 0 또는 2개인 이진 트리
• 완전 이진 트리 (complete binary tree)
  • 왼쪽에서부터 채워져 있는 이진 트리
  • 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막레벨의 경우 왼쪽부터 채워짐
• 변질 이진 트리 (degenerate binary tree)
  • 자식 노드가 하나밖에 없는 이진 트리
• 포화 이진 트리(perfect binary tree)
  • 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리 (balanced binary tree)
  • 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리
  • map,set을 구성하는 레드 블랙트리는 균형 이진트리 중 하나.

---

이진탐색트리(BST, Binary Search Tree)

 

이진트리의 일종.

노드의 오른쪽 하위 트리에는 '노드의 값보다 큰 값'이 있는 노드만 포함되고 왼쪽 하위트리에는 '노드의 값보다 작은 값'이 들어있는 트리.

 

이렇게 두면 검색을 하기에 용이하다.

10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으면되기 떄문에 전체 탐색을 하지 않아도 된다.

 

이진탐색트리(BST, Binary Search Tree)의 시간복잡도?

이렇게 균형잡히게 분포되어 있다면 탐색,삽입,삭제 수정 모두 O(logN)

하지만 이것은 삽입 순서에 따라 달라진다. 

예를 들어 1,2,3 이렇게 삽입되어 이진탐색트리가 완성되었다면 선형적 자료구조가 완성되어버린다.

*선형적은 직선,비선형적은 직선이 아닌 모양을 의미

 

1-2-3이렇게 삽입되어버리면  시간 복잡도가 O(N)이 되어버림.

 

즉, 이진탐색트리는 삽입순서에 따라 영향을 받는다.

그러나 삽입 순서가 어떻게 되든 트리의 노드들을 회전하는 방법 등을 통해 균형잡히게 만든 이진탐색트리에서 발전된 트리로는 AVI 트리, 레드블랙트리 등이 있다.

 

예를 들어 map이라는 자료구조는 삽입,탐색,삭제 수정의 시간 복잡도가 모두 O(logN)임을 보장받는데 그 이유가 균형잡힌 레드블랙트리를 기반으로 구현되어 있기 때문이다.