[프로그래머스 강의] 20강 이진탐색트리(1)

이진 탐색 트리(BST, Binary Search Tree)

---

이진 탐색 트리 정의

이진탐색 트리란 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모든 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리이며, 각 노드는 중복된 키를 허용하지 않는다. 

 

---

연산의 정의

▶ 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.right = None
        
class BinSearchTree:
    def __init__(self):
        self.root = None

---

inorder traversal

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 []

---

min(), max()

# 노드 클래스
class Node:
    
    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self
            
            
            
# 이진 탐색 트리 클래스
class BinSearchTree:
    
    def min(self):
        # 루트 노드가 존재하면
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

 

---

lookup(key)

✔ 입력 인자: 찾으려는 대상 키

✔ 리턴: 찾은 노드와 그것의 부모(Parent)노드(삭제에 이용된다)

               각각 없으면 None 으로 리턴

 

# 노드 클래스
class Node:

    # parent 인자가 주어지지않으면 None으로 생각하라는 말
    def lookup(self, key, parent=None):
        # 지금 방문된 노드(self.key)보다 탐색하려는 키가 작으면 왼쪽으로 가야함
        if key < self.key:
            # 왼쪽 자식이 있을 때
            if self.left:
                # 재귀적으로 호출
                return self.left.lookup(key, self)
            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
            
            
# 이진 탐색 트리 클래스
class BinSearchTree:

    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None

---

[문1. 이진 탐색 트리의 원소삽입 연산을 구현]

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    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


    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 __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0