이진검색트리-3

delete

- case 1 : 자식 노드가 없는 경우

-case 2 : 자식노드가 1개인 경우

- case 3 : 자식노드가 2개인 경우

- 지우려는 값의 successor을 찾는다

- 지우려는 값에 successor을 복사하고 successor의 값은 지운다.

 

delete의 수도코드

 

- 처음 if는 자식이 1개 이하인 경우이다. if문안에 들어가면 y에 지우려는 값을 넣는다

- if문안에 못들어가면 y에는 지우려는 값의 successor값을 넣는다.

- 다음 if문에는 y의 왼쪽 값이 있다면 x에 왼쪽 값, 오른쪽 값이 있다면 x에 오른쪽 값을 넣는다.

- 만약 x의 값이 없다면 y의 부모를 x의 부모로 만들어준다.

- 만약 y의 부모가 null 즉 y가 루트면 x를 트리의 루트로 만들어준다.

- 만약 그렇지 않고 y가 부모의 왼쪽 값이면 x를 왼쪽 값으로 만들고 오른쪽 값이면 x를 오른쪽 값으로 만든다.

- 만약 y!=z 즉 밑에 자식이 둘일 경우 z에 y값을 복사하여 넣는다.

- y를 리턴하는데 y는 delete되는 값이다.

- 시간복잡도 : o(h)

위에서부터 

1. 자식이 0일경우

2. 자식이 하나인 경우

3. 자식이 둘인 경우

 

**시간복잡도

- 각종 연산의 시간복잡도 o(h)

- 그러나 최악의 경우 트리의 높이 h=o(n)이 될수 있다. 그렇다면 힘들게 트리 구조를 이용할 필요가 없어진다.

- 균형잡힌 트리

• 레드-블랙 트리 등
• 키의 삽입이나 삭제시 추가로 트리의 균형을 잡아줌으로써 높이를 o(logn)으로 유지

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