(자료구조) 이진탐색트리

특징:
-사전 순 배열

시간복잡도:


가정: 균형트리일 경우
삽입: O(logN)
삭제: O(logN)
탐색: O(logN)

단점: 한곳으로 쏠릴 수 있다.


삭제의 경우:
1. 자식이 두 개인 경우
- 왼쪽자식에서 가장 큰 값을 가지고 오는경우와
- 오른쪽자식에서 가장 작은 값을 가지고 오는 경우 두가지가 가능하다
그렇다면 무엇을 선택하는게 좋을까? 내 생각은 두 서브트리중 더 작은 갯수의 서브트리를 선택하는 것이 낫다고 생각한다. 아마도 탐색 횟수가 줄어들기 때문에, 근데 장기적 관점에서 보면 한쪽으로 쏠린 서브트리의 자식갯수를 줄이는게 더 좋을 수 있지 않을까?

---> 이 경우 두 서브트리의 균형을 맞추기 위해 , 두 서브트리가 대칭을 이루기 위한
StdRandom.beronuii 로 접근한다. L/(L+R)로 접근.

응용:
이진트리의 경우에서 자식노드의 갯수를 3,4... 늘리는 경우를 B트리라 한다.