[Data Structure] Binary Search Tree

이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다.

---

Tree

출처: https://yoongrammer.tistory.com/68?category=956616

• 비선형, 계층적  재귀적 자료구조
• 정점의 갯수가 N이면 간선의 수는 N-1

종류

• 편향 트리(Skew Tree): 한쪽으로 기울어진 트리
• 이진 트리(Binary Tree): 트리의 차수가 2 이하인 트리, 레벨 N의 노드의 수는 최대 2^(n-1)개이다.
• 포화 이진 트리(Perfect Binary Tree): 모든 레벨이 꽉찬 이진 트리
• 완전 이진 트리(Complete Binary Tree): 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리
• 정 이진 트리(Full Binary Tree): 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리

Binary Search Tree(BST)

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

특징

1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

• 시간 복잡도: 탐색 연산의 시간 복잡도는 O(h) = O(log n)을 가짐.
  하지만 Skewed tree가 될 경우, 탐색의 Worst case가 되고 시간 복잡도는 O(n)이 됨.
• 해결 방법: Rebalancing 기법을 사용하여 트리 재조정
  Reblancing을 구현한 트리로는 AVL Tree, Red-Black Tree 등이 있다.

---

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure

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