프로그래머스 강의_20

이진 탐색 트리(Binary Search Trees)

모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리. (중복되는 데이터 원소는 없는 것으로 가정)
?! 정렬된 배열을 이용한 이진 탐색과 비슷하다.
장점 : 데이터의 원소의 추가, 삭제가 용이
단점 : 공간 소요가 큼
항상 O(logn)의 탐색복잡도를 가질까?? => 아닌 상황이 생긴다.

이진탐색 트리의 추상적 자료구조

• 데이터 표현 : 각 노드는 (key, value)의 쌍으로, 키를 이용해서 검색 가능 보다 복잡한 데이터 레코드로 확장이 가능하다.

이진 탐색 트리의 연산의 정의

• insert(key,data) : 트리에 주어진 데이터 원소를 추가
• remove(key) : 특정 원소를 트리로부터 삭제
• lookup(key) : 특정 원소를 검색
• inorder() : 키의 순서대로 데이터 원소를 나열
• min(), max : 최소 키, 최대 키를 가지는 원소를 각각 탐색

코드 구현 - 초기화

class Node:
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.rigt = None

class BinSearchTree:
    def __init__(self):
        self.root = None

class Node:
    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal
        
class BinSearchTree:
    def inorder(self):
        if self.root:
            return self.root.inorder()
        else: 
            return []

class BinSearchTree:
    def min(self):
        if self.root:
            return self.root.min()
        else:
            return self
     def max(self):
     ==> min()과 완전히 대칭 각자 구현.

코드 구현 - lookup()

• 입력 인자 : 찾으려는 대상 키
• 리턴 : 찾은 노드, 그것의 부모 노드 (각각, 없으면 None)

  class BinSearchTree:
     def lookup(self,key):
         if self.root:
             return self.root.lookup(key)
         else:
             return None, None
  class Node:
     def lookup(self, key, parent=None)
         if key < self.key:
             if self.left:
                 return self.left.lookup(key,self)
                 ## self는 self.left의 부모
             else: 
                 return None,None
                 
         elif key > self.key:
                if self.right:
                    return self.right.lookup(key,self)
                else:
                    return None, None
                
         else:
             return self, parent          
                    

코드 구현 - insert()

• 입력 인자 : 키, 데이터 원소
• 리턴 : 없음

class BinSearchTree:
    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
        # root가 없으면 insert하는 key와 data로 초기화
            self.root = Node(key, data)   

class Node:
    def insert(self,key,data):
        if key < self.key:
        elif key > self.key:
        else:
            # 값이 같은 경우 .. 에러발생하도록 
            raise KeyError('...')

==> 재귀적 방법으로 풀 수 있다.

def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key,data)
            else :
                self.left = Node(key,data)
        elif key > self.key:
            if self.right:
                self.right.insert(key,data)
            else :
                self.right = Node(key,data)
        else :
            raise KeyError('값이 같습니다.')