# 이진 트리 이진 트리(binary tree)는 '조상'과 '후손' 사이의 파생 관계를 나타내는 비선형 자료 구조로, '하나를 둘로 나누는' 분할 정복의 논리를 보여 준다. 연결 리스트처럼 기본 단위는 노드이며, 각 노드는 값과 왼쪽 자식 참조, 오른쪽 자식 참조를 포함한다. === "Python" ```python title="" class TreeNode: """이진 트리 노드 클래스""" def __init__(self, val: int): self.val: int = val # 노드 값 self.left: TreeNode | None = None # 왼쪽 자식 노드 참조 self.right: TreeNode | None = None # 오른쪽 자식 노드 참조 ``` === "C++" ```cpp title="" /* 이진 트리 노드 구조체 */ struct TreeNode { int val; // 노드 값 TreeNode *left; // 왼쪽 자식 노드 포인터 TreeNode *right; // 오른쪽 자식 노드 포인터 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` === "Java" ```java title="" /* 이진 트리 노드 클래스 */ class TreeNode { int val; // 노드 값 TreeNode left; // 왼쪽 자식 노드 참조 TreeNode right; // 오른쪽 자식 노드 참조 TreeNode(int x) { val = x; } } ``` === "C#" ```csharp title="" /* 이진 트리 노드 클래스 */ class TreeNode(int? x) { public int? val = x; // 노드 값 public TreeNode? left; // 왼쪽 자식 노드 참조 public TreeNode? right; // 오른쪽 자식 노드 참조 } ``` === "Go" ```go title="" /* 이진 트리 노드 구조체 */ type TreeNode struct { Val int Left *TreeNode Right *TreeNode } /* 생성자 */ func NewTreeNode(v int) *TreeNode { return &TreeNode{ Left: nil, // 왼쪽 자식 노드 포인터 Right: nil, // 오른쪽 자식 노드 포인터 Val: v, // 노드 값 } } ``` === "Swift" ```swift title="" /* 이진 트리 노드 클래스 */ class TreeNode { var val: Int // 노드 값 var left: TreeNode? // 왼쪽 자식 노드 참조 var right: TreeNode? // 오른쪽 자식 노드 참조 init(x: Int) { val = x } } ``` === "JS" ```javascript title="" /* 이진 트리 노드 클래스 */ class TreeNode { val; // 노드 값 left; // 왼쪽 자식 노드 포인터 right; // 오른쪽 자식 노드 포인터 constructor(val, left, right) { this.val = val === undefined ? 0 : val; this.left = left === undefined ? null : left; this.right = right === undefined ? null : right; } } ``` === "TS" ```typescript title="" /* 이진 트리 노드 클래스 */ class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { this.val = val === undefined ? 0 : val; // 노드 값 this.left = left === undefined ? null : left; // 왼쪽 자식 노드 참조 this.right = right === undefined ? null : right; // 오른쪽 자식 노드 참조 } } ``` === "Dart" ```dart title="" /* 이진 트리 노드 클래스 */ class TreeNode { int val; // 노드 값 TreeNode? left; // 왼쪽 자식 노드 참조 TreeNode? right; // 오른쪽 자식 노드 참조 TreeNode(this.val, [this.left, this.right]); } ``` === "Rust" ```rust title="" use std::rc::Rc; use std::cell::RefCell; /* 이진 트리 노드 구조체 */ struct TreeNode { val: i32, // 노드 값 left: Option>>, // 왼쪽 자식 노드 참조 right: Option>>, // 오른쪽 자식 노드 참조 } impl TreeNode { /* 생성자 */ fn new(val: i32) -> Rc> { Rc::new(RefCell::new(Self { val, left: None, right: None })) } } ``` === "C" ```c title="" /* 이진 트리 노드 구조체 */ typedef struct TreeNode { int val; // 노드 값 int height; // 노드 높이 struct TreeNode *left; // 왼쪽 자식 노드 포인터 struct TreeNode *right; // 오른쪽 자식 노드 포인터 } TreeNode; /* 생성자 */ TreeNode *newTreeNode(int val) { TreeNode *node; node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = val; node->height = 0; node->left = NULL; node->right = NULL; return node; } ``` === "Kotlin" ```kotlin title="" /* 이진 트리 노드 클래스 */ class TreeNode(val _val: Int) { // 노드 값 var left: TreeNode? = null // 왼쪽 자식 노드 참조 var right: TreeNode? = null // 오른쪽 자식 노드 참조 } ``` === "Ruby" ```ruby title="" ### 이진 트리 노드 클래스 ### class TreeNode attr_accessor :val # 노드 값 attr_accessor :left # 왼쪽 자식 노드 참조 attr_accessor :right # 오른쪽 자식 노드 참조 def initialize(val) @val = val end end ``` 각 노드는 두 참조(포인터)를 가지며, 각각 왼쪽 자식 노드(left-child node)와 오른쪽 자식 노드(right-child node)를 가리킨다. 해당 노드는 두 자식의 부모 노드(parent node)라고 한다. 어떤 노드의 왼쪽 자식과 그 아래 노드들이 이루는 트리를 그 노드의 왼쪽 서브트리(left subtree)라고 하며, 같은 방식으로 오른쪽 서브트리(right subtree)를 정의한다. **이진 트리에서 리프 노드를 제외한 모든 노드에는 자식 노드와 비어 있지 않은 서브트리가 있다**. 아래 그림에서 '노드 2'를 부모로 보면 왼쪽과 오른쪽 자식은 각각 '노드 4', '노드 5'다. 왼쪽 서브트리는 '노드 4와 그 아래 노드들이 이루는 트리', 오른쪽 서브트리는 '노드 5와 그 아래 노드들이 이루는 트리'다. ![부모 노드, 자식 노드, 서브트리](binary_tree.assets/binary_tree_definition.png) ## 이진 트리의 주요 용어 이진 트리에서 자주 쓰는 용어는 아래 그림과 같다. - 루트 노드(root node): 이진 트리의 최상위 노드로, 부모가 없다. - 리프 노드(leaf node): 자식이 없는 노드로, 두 포인터가 모두 `None`을 가리킨다. - 간선(edge): 두 노드를 잇는 선으로, 노드 참조(포인터)에 해당한다. - 노드의 레벨(level): 위에서 아래로 증가하며 루트의 레벨은 1이다. - 노드의 차수(degree): 자식 노드의 수다. 이진 트리에서는 0, 1, 2 중 하나다. - 이진 트리의 높이(height): 루트에서 가장 먼 리프까지 거치는 간선 수다. - 노드의 깊이(depth): 루트에서 해당 노드까지 거치는 간선 수다. - 노드의 높이(height): 해당 노드에서 가장 먼 리프와 해당 노드 사이에 있는 간선 수다. ![이진 트리의 주요 용어](binary_tree.assets/binary_tree_terminology.png) !!! tip "참고" 보통 '높이'와 '깊이'를 '거치는 간선 수'로 정의하지만, 일부 문제나 교재는 '거치는 노드 수'로 정의하기도 한다. 그런 경우에는 높이와 깊이에 각각 1을 더해야 한다. ## 이진 트리의 기본 연산 ### 이진 트리 초기화 연결 리스트처럼 먼저 노드를 초기화하고 참조(포인터)를 연결한다. === "Python" ```python title="binary_tree.py" # 이진 트리 초기화 # 노드 초기화 n1 = TreeNode(val=1) n2 = TreeNode(val=2) n3 = TreeNode(val=3) n4 = TreeNode(val=4) n5 = TreeNode(val=5) # 노드 사이의 참조(포인터) 연결 n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 ``` === "C++" ```cpp title="binary_tree.cpp" /* 이진 트리 초기화 */ // 노드 초기화 TreeNode* n1 = new TreeNode(1); TreeNode* n2 = new TreeNode(2); TreeNode* n3 = new TreeNode(3); TreeNode* n4 = new TreeNode(4); TreeNode* n5 = new TreeNode(5); // 노드 사이의 참조(포인터) 연결 n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; ``` === "Java" ```java title="binary_tree.java" // 노드 초기화 TreeNode n1 = new TreeNode(1); TreeNode n2 = new TreeNode(2); TreeNode n3 = new TreeNode(3); TreeNode n4 = new TreeNode(4); TreeNode n5 = new TreeNode(5); // 노드 사이의 참조(포인터) 연결 n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; ``` === "C#" ```csharp title="binary_tree.cs" /* 이진 트리 초기화 */ // 노드 초기화 TreeNode n1 = new(1); TreeNode n2 = new(2); TreeNode n3 = new(3); TreeNode n4 = new(4); TreeNode n5 = new(5); // 노드 사이의 참조(포인터) 연결 n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; ``` === "Go" ```go title="binary_tree.go" /* 이진 트리 초기화 */ // 노드 초기화 n1 := NewTreeNode(1) n2 := NewTreeNode(2) n3 := NewTreeNode(3) n4 := NewTreeNode(4) n5 := NewTreeNode(5) // 노드 사이의 참조(포인터) 연결 n1.Left = n2 n1.Right = n3 n2.Left = n4 n2.Right = n5 ``` === "Swift" ```swift title="binary_tree.swift" // 노드 초기화 let n1 = TreeNode(x: 1) let n2 = TreeNode(x: 2) let n3 = TreeNode(x: 3) let n4 = TreeNode(x: 4) let n5 = TreeNode(x: 5) // 노드 사이의 참조(포인터) 연결 n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 ``` === "JS" ```javascript title="binary_tree.js" /* 이진 트리 초기화 */ // 노드 초기화 let n1 = new TreeNode(1), n2 = new TreeNode(2), n3 = new TreeNode(3), n4 = new TreeNode(4), n5 = new TreeNode(5); // 노드 사이의 참조(포인터) 연결 n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; ``` === "TS" ```typescript title="binary_tree.ts" /* 이진 트리 초기화 */ // 노드 초기화 let n1 = new TreeNode(1), n2 = new TreeNode(2), n3 = new TreeNode(3), n4 = new TreeNode(4), n5 = new TreeNode(5); // 노드 사이의 참조(포인터) 연결 n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; ``` === "Dart" ```dart title="binary_tree.dart" /* 이진 트리 초기화 */ // 노드 초기화 TreeNode n1 = new TreeNode(1); TreeNode n2 = new TreeNode(2); TreeNode n3 = new TreeNode(3); TreeNode n4 = new TreeNode(4); TreeNode n5 = new TreeNode(5); // 노드 사이의 참조(포인터) 연결 n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; ``` === "Rust" ```rust title="binary_tree.rs" // 노드 초기화 let n1 = TreeNode::new(1); let n2 = TreeNode::new(2); let n3 = TreeNode::new(3); let n4 = TreeNode::new(4); let n5 = TreeNode::new(5); // 노드 사이의 참조(포인터) 연결 n1.borrow_mut().left = Some(n2.clone()); n1.borrow_mut().right = Some(n3); n2.borrow_mut().left = Some(n4); n2.borrow_mut().right = Some(n5); ``` === "C" ```c title="binary_tree.c" /* 이진 트리 초기화 */ // 노드 초기화 TreeNode *n1 = newTreeNode(1); TreeNode *n2 = newTreeNode(2); TreeNode *n3 = newTreeNode(3); TreeNode *n4 = newTreeNode(4); TreeNode *n5 = newTreeNode(5); // 노드 사이의 참조(포인터) 연결 n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; ``` === "Kotlin" ```kotlin title="binary_tree.kt" // 노드 초기화 val n1 = TreeNode(1) val n2 = TreeNode(2) val n3 = TreeNode(3) val n4 = TreeNode(4) val n5 = TreeNode(5) // 노드 사이의 참조(포인터) 연결 n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 ``` === "Ruby" ```ruby title="binary_tree.rb" # 이진 트리 초기화 # 노드 초기화 n1 = TreeNode.new(1) n2 = TreeNode.new(2) n3 = TreeNode.new(3) n4 = TreeNode.new(4) n5 = TreeNode.new(5) # 노드 사이의 참조(포인터) 연결 n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 ``` ??? pythontutor "실행 시각화" https://pythontutor.com/render.html#code=class%20TreeNode%3A%0A%20%20%20%20%22%22%22%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC%20%EB%85%B8%EB%93%9C%20%ED%81%B4%EB%9E%98%EC%8A%A4%22%22%22%0A%20%20%20%20def%20__init__%28self%2C%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EA%B0%92%0A%20%20%20%20%20%20%20%20self.left%3A%20TreeNode%20%7C%20None%20%3D%20None%20%20%23%20%EC%99%BC%EC%AA%BD%20%EC%9E%90%EC%8B%9D%20%EB%85%B8%EB%93%9C%20%EC%B0%B8%EC%A1%B0%0A%20%20%20%20%20%20%20%20self.right%3A%20TreeNode%20%7C%20None%20%3D%20None%20%23%20%EC%98%A4%EB%A5%B8%EC%AA%BD%20%EC%9E%90%EC%8B%9D%20%EB%85%B8%EB%93%9C%20%EC%B0%B8%EC%A1%B0%0A%0A%22%22%22%EC%8B%A4%ED%96%89%20%EC%BD%94%EB%93%9C%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC%20%EC%B4%88%EA%B8%B0%ED%99%94%0A%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EC%B4%88%EA%B8%B0%ED%99%94%0A%20%20%20%20n1%20%3D%20TreeNode%28val%3D1%29%0A%20%20%20%20n2%20%3D%20TreeNode%28val%3D2%29%0A%20%20%20%20n3%20%3D%20TreeNode%28val%3D3%29%0A%20%20%20%20n4%20%3D%20TreeNode%28val%3D4%29%0A%20%20%20%20n5%20%3D%20TreeNode%28val%3D5%29%0A%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EC%82%AC%EC%9D%B4%EC%9D%98%20%EC%B0%B8%EC%A1%B0%28%ED%8F%AC%EC%9D%B8%ED%84%B0%29%20%EC%97%B0%EA%B2%B0%0A%20%20%20%20n1.left%20%3D%20n2%0A%20%20%20%20n1.right%20%3D%20n3%0A%20%20%20%20n2.left%20%3D%20n4%0A%20%20%20%20n2.right%20%3D%20n5&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false ### 노드 삽입과 삭제 연결 리스트와 마찬가지로 이진 트리에서도 포인터를 수정하여 노드를 삽입하고 삭제할 수 있다. 아래 그림은 그 예다. ![이진 트리의 노드 삽입과 삭제](binary_tree.assets/binary_tree_add_remove.png) === "Python" ```python title="binary_tree.py" # 노드 삽입과 삭제 p = TreeNode(0) # n1 -> n2 사이에 노드 P 삽입 n1.left = p p.left = n2 # 노드 P 삭제 n1.left = n2 ``` === "C++" ```cpp title="binary_tree.cpp" /* 노드 삽입과 삭제 */ TreeNode* P = new TreeNode(0); // n1 -> n2 사이에 노드 P 삽입 n1->left = P; P->left = n2; // 노드 P 삭제 n1->left = n2; // 메모리 해제 delete P; ``` === "Java" ```java title="binary_tree.java" TreeNode P = new TreeNode(0); // n1 -> n2 사이에 노드 P 삽입 n1.left = P; P.left = n2; // 노드 P 삭제 n1.left = n2; ``` === "C#" ```csharp title="binary_tree.cs" /* 노드 삽입과 삭제 */ TreeNode P = new(0); // n1 -> n2 사이에 노드 P 삽입 n1.left = P; P.left = n2; // 노드 P 삭제 n1.left = n2; ``` === "Go" ```go title="binary_tree.go" /* 노드 삽입과 삭제 */ // n1 -> n2 사이에 노드 P 삽입 p := NewTreeNode(0) n1.Left = p p.Left = n2 // 노드 P 삭제 n1.Left = n2 ``` === "Swift" ```swift title="binary_tree.swift" let P = TreeNode(x: 0) // n1 -> n2 사이에 노드 P 삽입 n1.left = P P.left = n2 // 노드 P 삭제 n1.left = n2 ``` === "JS" ```javascript title="binary_tree.js" /* 노드 삽입과 삭제 */ let P = new TreeNode(0); // n1 -> n2 사이에 노드 P 삽입 n1.left = P; P.left = n2; // 노드 P 삭제 n1.left = n2; ``` === "TS" ```typescript title="binary_tree.ts" /* 노드 삽입과 삭제 */ const P = new TreeNode(0); // n1 -> n2 사이에 노드 P 삽입 n1.left = P; P.left = n2; // 노드 P 삭제 n1.left = n2; ``` === "Dart" ```dart title="binary_tree.dart" /* 노드 삽입과 삭제 */ TreeNode P = new TreeNode(0); // n1 -> n2 사이에 노드 P 삽입 n1.left = P; P.left = n2; // 노드 P 삭제 n1.left = n2; ``` === "Rust" ```rust title="binary_tree.rs" let p = TreeNode::new(0); // n1 -> n2 사이에 노드 P 삽입 n1.borrow_mut().left = Some(p.clone()); p.borrow_mut().left = Some(n2.clone()); // 노드 p 삭제 n1.borrow_mut().left = Some(n2); ``` === "C" ```c title="binary_tree.c" /* 노드 삽입과 삭제 */ TreeNode *P = newTreeNode(0); // n1 -> n2 사이에 노드 P 삽입 n1->left = P; P->left = n2; // 노드 P 삭제 n1->left = n2; // 메모리 해제 free(P); ``` === "Kotlin" ```kotlin title="binary_tree.kt" val P = TreeNode(0) // n1 -> n2 사이에 노드 P 삽입 n1.left = P P.left = n2 // 노드 P 삭제 n1.left = n2 ``` === "Ruby" ```ruby title="binary_tree.rb" # 노드 삽입과 삭제 _p = TreeNode.new(0) # n1 -> n2 사이에 노드 _p 삽입 n1.left = _p _p.left = n2 # 노드 삭제 n1.left = n2 ``` ??? pythontutor "실행 시각화" https://pythontutor.com/render.html#code=class%20TreeNode%3A%0A%20%20%20%20%22%22%22%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC%20%EB%85%B8%EB%93%9C%20%ED%81%B4%EB%9E%98%EC%8A%A4%22%22%22%0A%20%20%20%20def%20__init__%28self%2C%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EA%B0%92%0A%20%20%20%20%20%20%20%20self.left%3A%20TreeNode%20%7C%20None%20%3D%20None%20%20%23%20%EC%99%BC%EC%AA%BD%20%EC%9E%90%EC%8B%9D%20%EB%85%B8%EB%93%9C%20%EC%B0%B8%EC%A1%B0%0A%20%20%20%20%20%20%20%20self.right%3A%20TreeNode%20%7C%20None%20%3D%20None%20%23%20%EC%98%A4%EB%A5%B8%EC%AA%BD%20%EC%9E%90%EC%8B%9D%20%EB%85%B8%EB%93%9C%20%EC%B0%B8%EC%A1%B0%0A%0A%22%22%22%EC%8B%A4%ED%96%89%20%EC%BD%94%EB%93%9C%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC%20%EC%B4%88%EA%B8%B0%ED%99%94%0A%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EC%B4%88%EA%B8%B0%ED%99%94%0A%20%20%20%20n1%20%3D%20TreeNode%28val%3D1%29%0A%20%20%20%20n2%20%3D%20TreeNode%28val%3D2%29%0A%20%20%20%20n3%20%3D%20TreeNode%28val%3D3%29%0A%20%20%20%20n4%20%3D%20TreeNode%28val%3D4%29%0A%20%20%20%20n5%20%3D%20TreeNode%28val%3D5%29%0A%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EC%82%AC%EC%9D%B4%EC%9D%98%20%EC%B0%B8%EC%A1%B0%28%ED%8F%AC%EC%9D%B8%ED%84%B0%29%20%EC%97%B0%EA%B2%B0%0A%20%20%20%20n1.left%20%3D%20n2%0A%20%20%20%20n1.right%20%3D%20n3%0A%20%20%20%20n2.left%20%3D%20n4%0A%20%20%20%20n2.right%20%3D%20n5%0A%0A%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20%EC%82%BD%EC%9E%85%EA%B3%BC%20%EC%82%AD%EC%A0%9C%0A%20%20%20%20p%20%3D%20TreeNode%280%29%0A%20%20%20%20%23%20n1%20-%3E%20n2%20%EC%82%AC%EC%9D%B4%EC%97%90%20%EB%85%B8%EB%93%9C%20P%20%EC%82%BD%EC%9E%85%0A%20%20%20%20n1.left%20%3D%20p%0A%20%20%20%20p.left%20%3D%20n2%0A%20%20%20%20%23%20%EB%85%B8%EB%93%9C%20P%20%EC%82%AD%EC%A0%9C%0A%20%20%20%20n1.left%20%3D%20n2&cumulative=false&curInstr=37&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false !!! tip "참고" 노드 삽입은 이진 트리의 기존 논리 구조를 바꿀 수 있으며, 노드 삭제는 보통 해당 노드와 그 모든 서브트리를 삭제한다는 뜻이다. 따라서 의미 있는 작업을 수행하려면 이진 트리의 삽입과 삭제는 보통 여러 연산을 조합하여 이루어진다. ## 주요 이진 트리 종류 ### 포화 이진 트리 아래 그림의 포화 이진 트리(perfect binary tree)는 모든 레벨에 노드가 가득 차 있다. 리프 노드의 차수는 $0$, 나머지 노드의 차수는 모두 $2$다. 높이가 $h$이면 전체 노드 수는 $2^{h+1} - 1$로 전형적인 지수 관계를 보이며, 자연에서 흔히 볼 수 있는 세포 분열 현상을 반영한다. !!! tip "참고" 중국어권에서는 포화 이진 트리를 흔히 满二叉树라고 부른다. ![포화 이진 트리](binary_tree.assets/perfect_binary_tree.png) ### 완전 이진 트리 아래 그림의 완전 이진 트리(complete binary tree)는 맨 아래 레벨만 가득 차 있지 않아도 되며, 그 레벨의 노드는 왼쪽부터 오른쪽으로 빈틈없이 채워져야 한다. 포화 이진 트리도 완전 이진 트리다. ![완전 이진 트리](binary_tree.assets/complete_binary_tree.png) ### 정 이진 트리 아래 그림의 정 이진 트리(full binary tree)는 리프를 제외한 모든 노드가 자식 노드를 두 개씩 가진다. ![정 이진 트리](binary_tree.assets/full_binary_tree.png) ### 균형 이진 트리 아래 그림의 균형 이진 트리(balanced binary tree)는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차의 절댓값이 1을 넘지 않는다. ![균형 이진 트리](binary_tree.assets/balanced_binary_tree.png) ## 이진 트리의 퇴화 아래 그림은 이진 트리의 이상적인 구조와 퇴화한 구조를 보여 준다. 모든 레벨이 가득 차면 '포화 이진 트리'가 되고, 모든 노드가 한쪽으로 치우치면 '연결 리스트'로 퇴화한다. - 포화 이진 트리는 이상적인 경우로, 이진 트리의 '분할 정복' 이점을 충분히 발휘할 수 있다. - 연결 리스트는 다른 극단으로, 모든 연산이 선형 연산이 되어 시간 복잡도가 $O(n)$으로 저하된다. ![이진 트리의 최선 구조와 최악 구조](binary_tree.assets/binary_tree_best_worst_cases.png) 아래 표와 같이 최선 및 최악 구조에서 이진 트리의 리프 수, 전체 노드 수, 높이 등이 최댓값이나 최솟값에 도달한다.

표   이진 트리의 최선 구조와 최악 구조

| | 포화 이진 트리 | 연결 리스트 | | --------------------------- | ------------------ | ------- | | $i$ 번째 레벨의 노드 수 | $2^{i-1}$ | $1$ | | 높이 $h$인 트리의 리프 수 | $2^h$ | $1$ | | 높이 $h$인 트리의 전체 노드 수 | $2^{h+1} - 1$ | $h + 1$ | | 전체 노드 수가 $n$인 트리의 높이 | $\log_2 (n+1) - 1$ | $n - 1$ |