노트

이진 탐색 트리

Binary Search Tree

CS#algorithm · 연결된 개념 6개

쉽게 말하면

이진 탐색 트리는 갈림길마다 '작으면 왼쪽, 크면 오른쪽' 팻말이 선 길이에요. 갈림길을 지날 때마다 한쪽을 버리니까 정렬된 값을 빨리 찾고 넣을 수 있어요.

비유가 깨지는 곳 팻말 규칙만으로는 길이 고르게 갈라진다는 보장이 없어요. 정렬된 값을 차례로 넣으면 한쪽으로만 자라 O(n)이 되기 때문에, 실제로는 AVL·레드블랙 같은 자가 균형 트리를 써요.

각 노드가 자식을 최대 둘 가지고, 왼쪽 서브트리의 모든 값은 노드보다 작고 오른쪽은 크다는 규칙을 지키는 트리. 비교할 때마다 한쪽 가지를 버리므로 정렬된 데이터를 빠르게 찾고 넣을 수 있다.

트리 용어

  • 루트(Root): 맨 위 노드. 잎(leaf): 자식이 없는 노드
  • 부모·자식·형제(Parent, Child, Sibling), 간선(Edge): 노드를 잇는 연결
  • 트리는 루트가 하나이고 경로에 순환이 없는 그래프다. HTML DOM, 파일 시스템, JSON, AST(Abstract Syntax Tree)가 모두 트리다
type TreeNode = { val: number; left?: TreeNode; right?: TreeNode }
 
function insert(node: TreeNode | undefined, val: number): TreeNode {
  if (!node) return { val }
  if (val < node.val) node.left = insert(node.left, val)
  else node.right = insert(node.right, val)
  return node
}

복잡도

  • 균형이 잡혀 있으면 탐색·삽입이 O(log n)이다. 이진 탐색을 구조로 옮긴 셈이다
  • 정렬된 값을 차례로 넣으면 한쪽으로만 자라 연결 리스트처럼 되고 O(n)이 된다. 그래서 실제로는 AVL·레드블랙 트리 같은 자가 균형 트리(Self-Balancing Tree)를 쓴다
  • 데이터베이스 인덱스는 한 노드에 많은 키를 담는 B-트리(B-Tree) 계열을 쓴다(DB 인덱스와 트레이드오프)

모든 노드를 방문하는 방법은 트리 순회, 부모가 자식보다 항상 크거나 작은 다른 규칙의 트리는 이진 힙이다.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 연결 리스트

    각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.

  • 역색인과 검색 엔진

    역색인(inverted index)은 "각 문서에 어떤 단어가 있나" 대신 거꾸로 "이 단어가 어느 문서들에 있나"를 미리 만들어 둔 자료구조다. 책 뒤의 찾아보기와 같다. OpenSearch·Elasticsearch 같은 검색 엔진은 이 구조로 전문 검색(full-text search)을 빠르게 한다.

  • 정렬 알고리즘

    컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

  • 트리 셰이킹

    트리 셰이킹(Tree Shaking)은 번들러가 import/export를 정적으로 분석해, 어디서도 쓰지 않는 export를 최종 번들에서 빼는 최적화다. 빌드 단계의 죽은 코드 제거라고 보면 된다.

  • SEO

    SEO(Search Engine Optimization)는 검색 엔진이 페이지를 잘 찾고(크롤링, crawling), 이해해서 저장하고(색인, indexing), 알맞은 검색어로 노출하도록(순위, ranking) 사이트를 다듬는 일이다. 개발자가 맡는 부분은 대부분 앞의 두 단계, 즉 "검색 엔진이 읽을 수 있게 만드는 것"이다.

보기 옵션