스터디 - 이진 탐색 트리

속성

• 각 노드에 값이 있다.
• 값들에 전순서가 있다.
• 어떤 노드의 왼쪽 서브트리의 모든 값은 그 노드보다 값이 작다.
• 어떤 노드의 오른쪽 서브트리의 모든 값은 그 노드보다 값이 크다.

탐색

어떤 키 X를 찾는다고 할 때,
1. 현재노드를 루트로 설정한다.
2. X보다 현재노드가 작으면 왼쪽노드로 이동한다. 아니라면 오른쪽 노드로 이동한다.
3. 현재노드를 업데이트 한다.
4. 현재 노드의 키가 X이거나, 현재 노드가 null이면 종료한다.

삽입

탐색과 같이 반복문을 돌린다. 현재 노드를 키가 X인 노드로 업데이트한다.(현재 노드는 null이다.)

예시

삭제

• 삭제하려는 노드가 리프노드: 해당 노드를 삭제한다.
• 삭제하려는 노드의 자식이 1개: 해당 노드를 삭제하고 그 위치에 자식노드를 놓는다.
• 삭제하려는 노드의 자식이 2개: 해당 노드의 왼쪽서브트리에서 가장 큰 노드 혹은 오른쪽서브트리에서 가장 작은 노드를 해당 노드의 자리에 놓고 해당 노드를 삭제한다.

예시

시간복잡도

BST에서의 모든 연산은 O(h)의 시간복잡도를 가진다.(h = 트리의 높이)

트리의 높이는

• 최악의 경우: N (모든 노드가 한 줄로 이어져 있음)
• 최고의 경우: logN(트리가 완전이진트리이다)

자료출처

이진탐색트리-위키피디아