🌳트리🌳

리스트, 스택, 큐 등은 선형 구조
트리 : 계층적인 구조를 나타내는 비선형 자료구조

• 트리는 부모-자식 관계의 노드들로 이루어진다.
  응용분야 :
  • 계층적인 조직 표현
  • 컴퓨터 디스크의 디렉토리 구조
  • 인공지능에서의 의사결정트리 (decision tree)

트리의 용어

노드 (node) : 트리의 구성 요소
루트 (root) : 부모가 없는 노드
서브트리 (subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
단말노드 (terminal node) : 자식이 없는 노드
비단말노드 (nonterminal node) : 적어도 하나의 자식을 가지는 노드

자식, 부모, 형제, 조상, 자손 노드 : 사람과 동일
레벨 (level) : 트리의 각층의 번호
높이 (height) : 트리의 최대 레벨
차수 (degree) : 노드가 가지고 있는 자식 노드의 개수

🔅 이진 트리

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리 (서브트리는 공집합일 수 있다.)
• 노드에 최대 2개까지의 자식 노드 존재
• 모든 노드의 차수가 2 이하가 된다 -> 구현하기가 편리
• 서브 트리간의 순서 존재

이진 트리 검증

이진 트리는 공집합이거나, 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다.
이진 트리의 서브 트리들은 모두 이진 트리이어야 한다.

이진 트리 성질

노드의 개수가 n개이면 간선의 개수 n-1
높이가 h인 이진 트리의 경우, 최소 h개 ~ 최대 2^h -1개의 노드를 가진다.
n개의 노드를 가지는 이진트리의 높이 (최대 n, 최소 |log2(n+1)|(올림) )

이진 트리의 분류

1. 포화 이진 트리 (full binary tree)
   • 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 뜻한다.
     포화 이진 트리에는 다음과 같이 각 노드에 번호를 붙일 수 있다.

     

2. 완전 이진 트리 (complete binary tree)
   • 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽까지 노드가 순서대로 채워져 있는 이진트리

3. 기타 이진 트리

이진 트리의 표현

1. 배열 표현법
   모든 이진 트리를 포화 이진 트리라고 가정하고
   각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

   노드 i의 부모 노드 인덱스 = i/2
   노드 i의 왼쪽 자식 노드 인덱스 = 2i
   노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

2. 링크 표현법
   포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법
   노드는 구조체로, 링크는 포인터로 표현

이진 트리의 순회

순회 (traversal) : 트리의 노드들을 체계적으로 방문하는 것

1. 전위순회 (preorder traversal) : VLR

   • 자손노드보다 루트노드를 먼저 방문
     • 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

2. 중위순회 (inorder traversal) : LVR

   • 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
     • 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리

3. 후위순회 (postorder traversal) : LRV

   • 루트노드보다 자손을 먼저 방문
     • 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드

4. 레벨 순휘 (level order)

   • 각 노드를 레벨 순으로 검사하는 순회 방법
     큐를 사용하는 순회 법 (전위, 중위, 후위는 스택 사용)

스레드 이진 트리 (threaded binary tree)

NULL 링크에 중위 순회시에 후속 노드인 중위 후속자 (inorder successor)를 저장시켜 놓은 트리
이진트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회

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

탐색작업을 효율적으로 하기 위한 자료구조
key(왼쪽서브트리) < key(루트노드) < key(오른쪽서브트리)
이진탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

탐색 연산

주어진 키 값이 루트 노드의 키 값보다 작으면 루트 노드의 왼쪽 자식을 기준으로 탐색 시작
주어진 키 값이 루트 노드의 키 값보다 크면 루트 노드의 오른쪽 자식을 기준으로 탐색 시작
비교한 결과가 같으면 성공적!

삽입 연산

이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요

탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치

삭제 연산

3가지의 경우

1. 삭제하려는 노드가 단말 노드 일 경우
   -> 단말 노드의 부모를 찾아서 연결을 끊으면 된다.

2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
   -> 그 노드는 삭제하고 서브 트리는 부모 노드에 붙여준다.

3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우
   -> 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제노드 위치로 가져온다.

   • 가장 비슷한 값 ?
     • 왼쪽 서브 트리에서 제일 큰 값
     • 오른쪽 서브 트리에서 제일 작은 값

성능분석

이진탐색트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 h에 비례

• 최선의 경우
  이진 트리가 균형적으로 생성되어 있는 경우 = h=log2(n)
• 최악의 경우
  한쪽으로 치우친 경사이진트리의 경우 = h=n
  순차탐색과 시간복잡도가 같다.