[알고리즘] 이진검색트리(BST)

이진검색트리란?

 

• 이진트리이면서 각 노드에 하나의 키(데이터)를 가지고있으며 임의의 노드v에 대하여 왼쪽 부트리에 있는 키들은 key[v] 보다 작고 오른쪽부트리에 있는 값은 크거나 같다.
• dynamic set 을 효과적으로 지원하기위한 자료구조(search, insert, delete)
• 예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 𝑂(log𝑛)O(log⁡n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 𝑂(1)로 효율적이지만 탐색하는 데에는 𝑂(𝑛)의 계산복잡성이 발생. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적.
• 이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 씁니다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회) 이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다. 
• 최솟값은 트리의 맨 왼쪽, 최댓값은 트리의 맨 오른쪽이다.

 

이진검색트리의 search

이진검색트리의 코드

 

SUCCESSOR

노드 x의 successor란 key[x] 보다 크면서 가장 작은 키를 가진 노드, 모든 키들이 서로 다르다고 가정.

• 노드x의 오른쪽 부트리가 존재 할 경우, 오른쪽 부트리의 최솟값 
• 노도 x의 오른쪽 부트리가 없을 경우, 어떤노드 y의 왼쪽부트리의 최댓값이 x가 되는 y가 x의 최댓값.(루트를 타고 올라가다가 해당루트가 처음으로 왼쪽부트리가 된 경우)
• 그런 y가 없을경우 x가 최댓값

 

PREDECESSOR

노드 x의 predecessor란 key[x]보다 작으면서 가장 큰 키를 가진 노드

successor랑 반대 

 

 

INSERT

• 값이 추가될 때 기존의 노드는 변경되지 않음.
• 위치를 찾는 x와, 연결시켜줄 y를 설정.

 

DELETE

• 자식노드가 없는경우 - 그냥삭제.
• 자식노드가 1개인 경우 - 삭제 후 자신의 자식노드를 연결
• 자식노드가 2개인 경우 - 값을 삭제후 successor의 값을 대입, successor은 왼쪽 노드가 없기때문에 노드가 0~1개, 위의 경우를 실행.