Binary Search Tree

• 이진 탐색 트리 = 이진탐색 + 연결리스트
• 두 가지의 장점을 합쳐서 만든 것
  • 이진탐색 시 O(logN), 삽입/삭제 불가능
  • 연결리스트 삽입/삭제 시 O(1), 탐색 시 O(N)
• 각 노드의 자식이 2개 이하
• 왼쪽은 부모보다 작고, 오른쪽은 부모보다 큼
• 중복된 노드 X (검색 목적이므로 중복 존재로 느리게 만들 필요 X, 트리 삽입보다 노드가 count를 가지게 하는 것이 효율적)

순회

in-order 중위순회 방식으로 읽을 때 정렬된 순서대로 읽을 수 있음

연산

검색, 삽입, 삭제, 트리 생성, 트리 삭제

시간복잡도

• 균등 트리 : 노드 개수 N, O(logN)
• 편향 트리 : 노드 개수 N, O(N)

(편향 트리를 바로잡도록 도와주는 개선된 tree가 AVL, RedBlack Tree)

삽입

1. Root 에서 시작
2. 작으면 왼쪽, 크면 오른쪽으로 leaf 노드에 도달할 때까지 이동
3. 노드보다 작으면 왼쪽, 크면 오른쪽에 삽입

삭제

• 자식 X leaf 노드 : 그냥 삭제
• 자식 1 leaf 노드 : 지워진 노드에 자식 올리기
• 자식 2 leaf 노드 : 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값

 

References

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

이진탐색트리(Binary Search Tree) · ratsgo's blog