[JS][자료구조] 이진 트리(binary tree)

트리 중 이진트리

⚡정의

각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조

📚활용 방식

• 검색과 정렬 : 이진 탐색 트리와 이진 힙 구현에 활용
• 허프만 코딩 : 연관 분기 구조 위한 데이터 표현에 활용

📚이진 트리의 종류

• 포화 이진 트리 (Perfect binary tree)
• 완전 이진 트리 (Complete binary tree)
• 정 이진 트리 (Full binary tree)
• 편향 이진 트리 (Skewed binary tree)
• 균형 이진 트리 (Balanced binary tree)

 

📎포화 이진 트리 (Perfect binary tree)

• 모든 레벨의 노드가 가득 채워져 있는 트리

특징

• Leaf 노드를 제외한 모든 자식은 2개의 노드를 보유
• 노드의 개수 : n = 2^h -1

트리 형태

 

 

 

📎완전 이진 트리(Complete binary tree)

• 마지막 레벨 전까지 노드가 가득 채워져 있고, 마지막 레벨은 왼쪽부터 순차적으로 채워져 있는 트리

특징

• 배열을 사용해 효율적 표현 가능
• 노드의 개수 : n < 2^h -1

트리 형태

 

📎정 이진 트리(Full binary tree)

• 모든 노드가 0개 또는 2개의 자식 노드만 갖는 트리

특징

• proper 또는 plane 이진 트리라고도 불림
• 노드의 개수 : n <= 2^h -1

트리 형태

 

📎편향 이진 트리(Skewed binary tree)

• 왼쪽 혹은 오른쪽으로 편향되게 치우쳐 있는 트리

특징

• 각각의 높이에 하나의 노드만 존재
• 노드의 개수 : h

트리 형태

 

📎균형 이진 트리(Balanced binary tree)

• 삽입/삭제가 이루어 질 때,왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차를 1이하로 맞추는 이진 탐색 트리

특징

• 서브 트리 높이 차이가 항상 1 이하로 유지
• 균형트리 종류 : AVL트리, Red-Black트리, B트리, B+트리, B*트리

트리 형태