프로그래머스 강의_21

이진 탐색 트리(Binary Search Trees)

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

1. 키(key)를 이용해서 노드를 찾는다.
   => 해당 키의 노드가 없으면, 삭제할 것도 없음
   => 찾은 노드의 부모 노드도 알고 있어야 함

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

인터페이스의 설계

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

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

이진 탐색 트리 구조의 유지

• 삭제되는 노드가

1. 말단(leaf)노드인 경우
   그냥 그 노드를 없애면 됨
   => 부모 노드의 링크를 조정(좌? 우?)
2. 자식을 하나 가지고 있는 경우
   삭제되는 노드 자리에 그 자식을 대신 배치
   => 자식이 왼쪽? 오른쪽?
   => 부모 노드의 링크를 조정(좌? 우?)
3. 자식을 둘 가지고 있는 경우
   삭제되는 노드보다 바로 다음(큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드 대신 삭제

우선 자식을 세어보자

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

말단(Leaf)노드의 삭제

만약 삭제되는 노드 (X)가 root node인 경우는 어떻게?
==> 트리 전체가 없어진다.

자식이 하나인 노드의 삭제

• 자식이 왼쪽에 있거나 오른쪽에 있거나 삭제해도 결과는 같다.
• 부모 노드의 왼쪽자식을 삭제하거나 오른쪽 자식을 삭제하는 것도 결과는 같다
• 삭제되는 노드(X)가 rootnode인 경우는 어떻게???
  ===> 대신 들어오는 자식이 새로 root가 됨.

자식이 둘인 노드의 삭제

• root 노드를 삭제할 때

1. 처음 오른쪽 노드를 찾아간다.
2. 다음 가장 작은 값의 노드(S)를 찾는다.
3. S를 찾은 후 S의 parent노드를 찾고 S는 삭제하려는 노드 X자리에 넣어준다.
4. parent노드의 자식노드인 S를 X자리에 넣었기 때문에 S의 자식노드를 S자리로 넣어준다.

• 노드 X를 삭제하기

1. 오른쪽 자식을 찾고 그 다음 왼쪽 노드로 가장 작은 노드를 찾는다.

이진 탐색 트리가 별로 효율적이지 못한 경우

T = BinSearchTree()
T.insert(1,'John')
T.insert(2,'Mary')
T.insert(3,'Anne')
T.insert(4,'Peter')
=> 만약 4를 찾는다면 선형탐색과 동등한 정도의 복잡도를 가지게 된다.
=> 트리의 왼쪽 오른쪽이 반반씩 갈려있으면 logn과 같은 복잡도를 가질 수 있게 되어 효율적이다.
===> 보다 나은 성능을 보이는 이진 탐색 트리들
높이의 균형을 유지함으로써 O(logn)의 탐색 복잡도 보장 삽입, 삭제 연산이 보다 복잡하다.