🌳자료구조
Trees Algorithms
Branching structures that grow in hierarchy. Learn the 4 topics below step by step with interactive visualizations.
🌳트리 순회 (Tree Traversal)
트리의 모든 노드를 한 번씩 방문하는 방법입니다. 방문 시점에 따라 전위(루트 먼저)·중위(왼쪽→루트→오른쪽, BST에서 정렬 순)·후위(루트 마지막)·레벨 순회로 나뉩니다.
O(n)🌳AVL 트리 (AVL Tree)
모든 노드의 좌우 서브트리 높이 차를 1 이하로 유지하는 자가 균형 이진 탐색 트리입니다. 삽입·삭제 후 회전(rotation)으로 균형을 복구해 항상 O(log n)을 보장합니다.
O(log n)🌳세그먼트 트리 (Segment Tree)
구간의 합·최솟값 등을 빠르게 구하기 위한 트리입니다. 각 노드가 한 구간을 담당하며, 점 갱신과 구간 질의를 모두 O(log n)에 처리해 누적 합 배열의 갱신 약점을 보완합니다.
질의·갱신 O(log n)🌳트라이 (Trie)
문자열을 글자 단위로 가지에 저장하는 접두사 트리입니다. 공통 접두사를 공유해 자동완성·사전·접두사 검색을 문자열 길이 O(m)에 처리합니다.
O(m) (문자열 길이)