트리 이진트리 이진탐색트리 간단 정리

트리

• 비선형, 계층형 구조
• 방향성이 있는 비순환 그래프
• 원소들간 1:n 관계
• 사이클이 존재할 수 없다.
• 노드 : 트리원소
• 간선 : 노드 연결선
• 루트노드 : 트리의 최상위 노드
• 형제노드 : 부모가 같은 노드들
• 조상노드 : 간선을 따라 위로 올라갔을 때 만나는 부모노드들
• 차수 :
  노드 차수 => 노드에 연결된 자식노드 수
  트리 차수 => 트리에 있는 노드의 차수 중 가장 큰 값
• 단말노드 : 차수가 0인 노드
• 높이 :
  노드 높이 => 루트에서 노드애 이르는 간선 수
  트리 높이 => 트리 노드 중 가장 큰 높이 값(즉 단말노드 중 가장 밑에 있는)
• 노드가 N개인 트리는 항상 N-1개의 간선을 가짐
• 종류 : 이진 트리, 이진 탐색 트리, 균형 트리(AVL, red-black), 이진 힙

 

이진 트리

• 모든 노드들이 2개의 서브트리를 갖는다.
• i레벨에서 노드의 최대 개수는 2^i개
• 높이가 h인 이진트리 최소 노드 개수는 h+1

포화 이진 트리

• 모든 레벨의 노드가 포화상태인 이진 트리

 

완전 이진 트리

• 높이가 h 이고 노드 수가 n 일 때 포화 이진 트리의 1번 노드부터 n번까지 빈자리가 없는 이진 트리.

 

편향 이진 트리

• 높이 h에 대한 최소 노드 개수를 가지면서 한 쪽 방향의 자식만 있는 트리

 

이진 트리 순회

전 중 후가 부모 기준이라고 생각하면 된다.

• 전위 순회
  • 부모 - 왼쪽자식 - 오른쪽자식 순 순회
• 중위 순회
  • 왼쪽 자식 - 부모 - 오른쪽자식 순 순회
• 후위 순회
  • 왼쪽 자식 - 오른쪽자식 - 부모 순 순회

 

트리 구현 방법

1. 인접 배열

빨간색 숫자가 배열 인덱스.

i번 노드의 부모는 i/2번, i번 노드의 왼쪽 자식 번호는 i*2, i번 노드의 오른쪽 자식 번호는 i*2+1 이다.

배열 최대 크기 = 2^(n+1)-1

 

단점 : 편향이진트리의 경우 메모리 낭비. 트리 중간에 새로운 노드를 삽입/삭제 할 때 비효율적이다.

 

2. 인접 리스트

n개의 배열을 만드는데 각 칸을 arraylist로 정의한다면, 위 그림으로 봤을 때 1번노드의 arraylist엔 2, 3 이 들어있는 식.