이진검색트리-2

최솟값

- 이진 검색트리의 최솟값은 루트에서 계속 왼쪽으로 갔을 때 마지막 노드이다

- 시간복잡도 : o(h)

최댓값

- 이진 검색트리의 최댓값은 루트에서 가장 오른쪽 노드이다.

- 시간복잡도 : o(h)

successor

- 노드 x의 successor란 key[x]보다 크면서 가장 작은 키를 가진 노드

- 모든 키들이 서로 다르다고 가정

successor를 찾는 3가지 경우

1. 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최솟값

2. 오른쪽 부트리가 없을 경우, 부모를 따라 루트까지 올라가면서 처음으로 누군가의 왼쪽 자식이 되는 노드

3. 그런 노드 y가 존재하지 않을 경우 successor가 존재하지 않음 (즉, x가 최댓값)

- 오른쪽 서브트리가 존재하면 그 서브트리에서 최솟값을 찾는다

- 아니면 y에 x의 부모노드를 넣고 부모노드가 null이 되거나 x가 왼쪽자식이 될때까지 while을 반복한다.

 

insert

- 현재 트리의 노드들은 변하지 않는다. -> 삽입하려는 값이 지금 비교하는 값보다 작으면 왼쪽 크면 오른쪽에 넣는다

-> 마지막까지 반복한 뒤 삽입한다.

- 13밑에 마지막 노드에 14가 들어간다.

insert 수도코드

- z라는 새로운 값을 갖고 들어간다.

- y에는 null 값을 넣고 x에는 tree의 주소를 넣는다.

- x가 null이 될때까지 반복한다. y에 x의 값을 넣고 y랑 z를 비교하고 z가 작으면 x에 왼쪽 노드의 값을 넣고, 크면 오른쪽 노드의 값을 넣는다.

- while문이 끝나면 z의 부모의 값에 y를 넣는다.

- y가 null일 경우는 트리가 비어있는 경우이므로 root에 z값을 넣는다.

- 마지막으로 y와 z를 비교하여 크면 왼쪽에 작으면 오른쪽에 삽입한다.

-시간복잡도 : o(h)

 

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.