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

이진 탐색 트리에서 원소 삭제

1. 키(key)를 이용해서 노드를 찾는다.

• 해당 키의 노드가 없으면, 삭제할 것도 없음
• 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번 때문)

2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다.

인터페이스의 설계

입력: 키 (Key)
출력: 삭제한 경우 True / 해당 키의 노드가 없는 경우 False

class BinSearchTree:
	def remove(self, key):
    	node, parent = self.lookup(key)
        if node:
        	...
            return True
        else:
        	return False

이진 탐색 트리 구조의 유지
삭제되는 노드가
1. 말단 (leaf) 노드인 경우

• 그냥 그 노드를 없애면 됨
  -> 부모 노드의 링크를 조정 (좌? 우? None)

2. 자식을 하나 가지고 있는 경우

• 삭제되는 노드 자리에 그 자식을 대신 배치
  -> 자식이 왼쪽? 오른쪽?
  -> 부모 노드의 링크를 조정 (좌? 우?)

3. 자식을 둘 가지고 있는 경우

• 삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드를 찾아(S:오른쪽 노드의 맨 왼쪽 노드, S의 parent도 필요)
  그 노드를 삭제되는 노드 자리에 대신 배치하고
  이 노드를 대신 삭제우선 자식을 세어 보자

 class Node:
 	def countChildren(self):
    	count = 0
        if self.left:
        	count += 1
        if self.right:
        	count += 1
        return count

밀단 (Leaf) 노드의 삭제

• 삭제되는 노드 (X)가 root node인 경우는? 트리 자체가 사라진다. (self.root = None)
  자식이 하나인 노드의 삭제
• 삭제되는 노드 (X)가 root node인 경우는 어떻게? 대신 들어오는 자식이 새로 root가 된다.
  자식이 둘인 노드의 삭제
• S는 왼쪽 노드는 없음(오른쪽 노드의 min 값이기 때문)
• S가 바로 오른쪽 노드에 있는 경우 즉 제거하려는 값이 S의 parent노드인 경우 오른쪽 노드 삭제

### 이진 탐색 트리가 별로 효율적이지 못한 경우
T = BinSearchTree()
T.insert(1, 'john')
T.insert(2, 'mary')
T.insert(3, 'anne')
T.insert(4, 'peter')
-> 높이의 균형을 맞추지 못하도 한쪽으로 치우친 이진 탐색 이 경우는 선형 탐색과 동등한 정도의 복잡도
T = BinSearchTree()
T.insert(4, 'john')
T.insert(3, 'mary')
T.insert(2, 'anne')
T.insert(1, 'peter')
-> 이경우도 마찬가지

보다 나은 성능을 보이는 이진 탐색 트리들

• 높이의 균형을 유지함으로써 o(logn)의 탐색 복잡도 보장
• 삽입, 삭제 연산이 보다 복잡
• 이를 해결한 자료 구조(AVL tree, Red-Black tree)