binary-tree

Binary Tree란 무엇인가?

각 지점(노드)에서 최대 두 갈래로만 갈라지는 나무 형태의 데이터 구조다. 족보에서 각 사람이 최대 두 명의 자녀만 가질 수 있다고 제한한 것과 비슷하다.

In a binary tree, each node can have a maximum of two children linked to it.

높이 h인 Binary Tree의 레벨 h에 최대 몇 개 노드가 존재할 수 있는가?

레벨 h에는 최대 2의 h승(2^h)개의 노드가 들어갈 수 있다. 토너먼트 대진표처럼 한 단계 내려갈 때마다 자리가 두 배씩 늘어나는 원리다.

A binary tree can have at most 2^h nodes at level h.

높이 h인 Binary Tree가 가질 수 있는 최대 노드 수는?

높이 h인 이진 트리는 모든 자리를 빈틈없이 채웠을 때 최대 2^(h+1) - 1개의 노드를 가질 수 있다. 각 레벨의 최대 노드 수를 전부 합산한 결과다.

A binary tree of height h can have at most 2^(h+1) - 1 nodes.

N개 노드를 가진 Binary Tree의 최소 높이는?

N개의 노드를 가장 납작하게(넓게) 배치하면 높이는 log₂N의 올림값이 된다. 매 레벨을 꽉 채워야 높이를 최소화할 수 있기 때문이다.

The minimum possible height for N nodes is ⌈log₂N⌉.

L개의 리프 노드를 가진 Binary Tree의 최소 레벨 수는?

리프 노드(맨 끝 노드)가 L개 있으려면 최소 log₂L의 올림값만큼의 레벨이 필요하다. 한 레벨에 들어갈 수 있는 자리가 두 배씩 늘어나므로, L개를 수용하려면 그만큼의 깊이가 보장되어야 한다.

A binary tree with L leaves must have at least ⌈log₂L⌉ levels.

N개 노드를 가진 Binary Tree의 총 간선(edge) 수는?

노드가 n개이면 간선은 항상 n - 1개다. 루트를 제외한 모든 노드는 정확히 하나의 부모와 연결되므로, 노드 수에서 루트 하나를 빼면 간선 수가 된다.

In any non-empty binary tree with n nodes, the total number of edges is n - 1.

Self-Balancing BST의 활용은?

스스로 균형을 유지하는 이진 탐색 트리로, 최솟값과 최댓값 모두를 빠르게 꺼낼 수 있는 양방향 우선순위 큐를 구현할 때 사용한다. 일반 힙은 최솟값 또는 최댓값 한쪽만 빠르게 꺼낼 수 있지만, 이 구조는 양쪽 모두 효율적으로 처리한다.

A Self-Balancing Binary Search Tree is used to implement doubly ended priority queue. With a Binary Heap, we can either implement a priority queue with support of extractMin() or with extractMax(). If we wish to support both the operations, we use a Self-Balancing Binary Search Tree to do both in O(Log n).

Complete Binary Tree와 Perfect Binary Tree의 차이는?

Complete는 마지막 레벨만 비어있을 수 있되 왼쪽부터 빈틈없이 채운 트리이고, Perfect는 모든 레벨이 완전히 꽉 찬 트리다. 극장 비유로 보면 Complete는 마지막 줄만 왼쪽부터 채워진 상태이고, Perfect는 모든 좌석이 만석인 상태다.

Complete Binary Tree: A special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

Perfect Binary Tree: All levels are completely filled. The number of leaf nodes equals the number of internal nodes plus one.

Full Binary Tree란 무엇인가?

모든 노드가 자녀를 0명 또는 2명만 가지는 이진 트리다. 자녀가 1명인 노드가 하나도 없어서, 모든 갈림길이 반드시 두 갈래로 나뉘거나 끝나는 구조다.

A binary tree where every node has either 0 or 2 children.

Degenerate(Pathological) Binary Tree란 무엇이며, 왜 비효율적인가?

모든 노드가 자녀를 딱 하나씩만 가져서 한 줄로 길게 늘어진 트리다. 사실상 일직선 목록과 같아져 트리가 주는 빠른 검색 이점을 완전히 잃어버린다.

A tree in which each parent node has only one child. This essentially forms a linked list, which leads to inefficient operations.

Balanced Binary Tree란 무엇이며, 대표적인 예시는?

어느 지점에서든 왼쪽과 오른쪽 가지의 높이 차이가 최소(보통 1 이하)인 트리다. 한쪽으로 치우치지 않아 검색, 삽입, 삭제가 항상 빠르게 유지된다. 대표적으로 AVL 트리, Red-Black 트리 등이 있다.

A binary tree where the difference in heights between the left and right subtrees of any node is minimal (often defined as at most 1). Examples: AVL Tree, Red Black Tree, Splay Tree.