트라이
문자열 검색을 빠르게 할 수 있도록 설계한 트리
- N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. (알파벳 N == 26)
- 루트 노드는 항상 ' ' (공백)
이진 트리
모든 노드의 자식 노드의 개수가 2 이하인 트리
편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.
세그먼트 트리
데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조
구간 합, 최대 값, 최소 값 등을 구할 때 이용할 수 있다!
[참고]
주홍철, <면접을 위한 CS 전공지식 노트>, 길벗(2022), p426, 435