이진 트리

이진트리

자식 노드가 최대 2개씩인 이진 트리

 

이진 검색 트리 / 이진 탐색 트리

루트 노드를 기준으로 왼쪽 서브트리들은 루트노드 값보다 작고, 오른쪽 서브트리들은 루트노드 값보다 크다.

 

이진 탐색 트리의 최솟값

• 트리의 가장 왼쪽에 존재

이진 탐색 트리의 최대값

• 트리의 가장 오른쪽에 존재

순회 ( = 모든 노드들을 한 번씩 방문하는 것)

• 전위 순회
  • 루트 노드부터 값 출력
  • 중앙 -> 왼쪽 -> 중앙 -> 오른쪽

• 중위 순회
  
  • 가장 왼쪽 밑의 노드에서 시작하여 값 출력
  • 왼쪽 -> 중앙 -> 오른쪽
  • 값 출력 : 낮음 -> 높음 순서대로 결과가 나온다. 

•   후위 순회
  • 가장 왼쪽 밑의 노드에서 시작하여 값 출력
  • 왼쪽 -> 오른쪽 -> 중앙

이진트리 장점

• 삽입 삭제 유연
• 삽입/ 삭제/ 검색이 빠르다
• 값의 순서대로 순회 가능하다

이진트리 단점

• 구조적으로 한쪽으로 편향되면 수행시간이 길어진다.

이진트리 시간 복잡도

• Best : O(1)
• Worst : O(N)

노드의 후임자 / 선임자

 

• 후임자
  • 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드
  • 20의 후임자 : 30
  • 17의 후임자 : 20
  • 10의 후임자 : 15
• 선임자
  • 해당 노드보다 값이 작은 노드들 중에서 가장 큰 값
  • 20의 선임자: 17
  • 10의 선임자 : 5
  • 40의 선임자: 30

 

완전 이진 트리

왼쪽부터 모두 채워져있고, 마지막 레벨을 제외하고 다 채워져 있을때

 

포화 이진 트리 perfect

완벽한 삼각형 구조

 

트리 관련 용어 정리

• 루트 노드 : 맨 위 노드
• 디그리 / 차수 : 각 노드에서 나온 가지수 ( = 자식 수)
• 단말노드 / 잎노드 / 리프노드 : 자식 노드가 없는 모든 노드
• 비단말노드 / 내부노드 : 자식 노드가 있는 모든 노드
• 조상노드 : 내 노드보다 위에 노드x
• 자식노드 : 내 밑에 아가 노드들
• 노드의 크기 : 자신 포함 자손 노드 갯수
• 노드의 깊이 : 루트 노드에서 해당 노드까지의 간선 갯수
• 레벨 : 0레벨 1레벨 2레벨..
• 서브 트리 : 큰 트리 안에 있는 서브 트리
• 트리의 높이 : 루트 노드 에서 리프노드의 간선 개수