Array, linklist, stack, queue처럼 일직선 데이터 구조에 반해 Tree는 부모, 자식 관계 구조임. 계층이고 그룹이고! 노드가 하나 이상의 child를 갖기 때문.
- binary tree
- child node가 최대 2개까지 붙는 경우.
- 3개면 ternary tree임.
- binary search tree
- 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야하고 오른쪽 자식은 부모 값보다 큰 값을 가져야 함.
- 그래서 큰 값을 찾고 싶으면 오른쪽, 작은 값을 찾고 싶으면 왼쪽
그 외)
지나치게 치우쳐진 게 아니라면 balanced로 취급
- full) node child가 하나도 없거나 두개로 구성될 경우
- complete) 왼쪽부터 채워져있음
- perfect) 완벽한 피라미드 구조
- 트라이(Trie, "트라이"로 발음)는 각 노드가 단어의 문자를 나타내는 문자열을 저장하는 특수 트리입니다. 일반적인 트리와 달리 루트에서 시작하는 경로는 접두사를 나타냅니다.
Operation | Time |
Insert | O(m) where m = length of word |
Search | O(m) |
Prefix Match | O(m) |