[알고리즘] - 트리

출처: https://www.geeksforgeeks.org/properties-of-binary-tree/

이진 트리 (Binary Tree)

• 자식 노드의 개수가 최대 2개인 트리

포화 이진 트리 (Full Binary Tree)

 

• 모든 레벨에 노드가 포화 상태로 차 있는 바이너리 트리
• 최대 노드 개수인 (2^(h+1) -1) 의 노드를 가진 Binary Tree
• 루트를 1번으로 하여 2^(h+1) -1 까지 정해진 위치에 대한 노드 번호를 가짐

완전 이진 트리 (Complete Binary Tree)

높이가 h 이고 노드 수가 n 일때 Full binary Tree 의 노드 1번부터 n 번까지 빈자리가 없는 binary tree

 

편향 이진 트리

• 한쪽으로만 쏠려 있는 트리

Array 로 트리를 표현하기

• 자식노드 = i*2, i*2+1
• 부모노드 = i / 2
• 높이가 h 인 Binary Tree 를 위한 Array 의 크기 = 2^(h+1) -1

 

단점

• 편향 이진 트리인 경우 메모리 낭비가 심해질 수 있음
• 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 Tree
  • Tree의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 Array의 크기 변경이 어려워 비효율적임

Expression Tree

• 수식을 표현하는 Binary Tree
• 연산자는 루트노드이거나 가지노드
• 피연산자는 모두 리프노드임

 

이진 탐색 트리 (Binary search tree)

• 탐색작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 가짐
• 왼쪽 부트리 < 가운데 < 오른쪽 부트리
• 왼쪽 부트리와 오른쪽 부트리도 Binary Search Tree임
• 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음

 

삽입 연산

• 먼저 탐색 연산 수행 (같은 원소가 있는지 확인)
• 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 됨
• 탐색 실패한 위치에 원소를 삽입

시간 복잡도

• 탐색, 삽입, 삭제 시간은 Tree의 높이에 좌우 됨
• 평균의 경우 (Binary Tree) 가 균형적으로 생성되어있는 경우
  • O(log N)
• 최악의 경우
  • 한쪽으로 치우친 경사 트리인 경우
  • O(N)