자료구조 마스터: 연결 리스트, 트리, 힙, 트라이 핵심 개념 완벽 정리!
by DD
6개월 전
조회수 16
자료구조의 핵심 개념인 노드를 중심으로 연결 리스트, 트리, 힙, 트라이 구조를 설명
연결 리스트의 단점 보완을 위해 이중 연결 리스트를 소개하고, BST의 삭제 과정 상세 분석
트라이의 장단점 분석 및 검색 엔진, 자동 완성 기능 구현에 활용
연결 리스트, 왜 배열보다 좋을까?
배열은 인덱스 접근이 빠르지만, 중간 삽입/삭제 시 O(n) 시간 복잡도를 가진다. 따라서 연결 리스트는 삽입/삭제 시 O(1)의 시간 복잡도를 제공한다. 구체적으로, 노드의 포인터만 변경하면 되기 때문이다. 반면, 임의 접근은 O(n)으로, 처음부터 순회해야 한다.
이진 탐색 트리(BST) 삭제 알고리즘 분석
BST 삭제는 삭제할 노드의 자식 유무에 따라 다른 방식으로 처리된다. 자식이 없는 경우는 간단히 삭제, 자식이 하나인 경우는 자식 노드를 연결한다. 따라서 자식이 둘인 경우, 오른쪽 서브트리에서 최소값을 찾아 대체하고, 해당 노드를 삭제하는 재귀적 과정을 거친다.
트라이(Trie)의 활용: 자동 완성 & 검색
트라이는 접두어 기반 검색에 특화되어, 자동 완성 기능 구현에 최적화되어 있다. 구체적으로, O(m) 시간 복잡도로 검색이 가능하며, m은 검색어의 길이이다. 따라서 검색 엔진 및 모바일 키보드 등에서 활용된다. 반면, 메모리 사용량이 높다는 단점이 있다.
