19. 이진 트리와 이진 검색 트리(1) 입력, 파이썬

트리란?

Tree는 edge와 node의 집합입니다. 

 

최상위 node를 root라 하고, 한 노드가 아래 노드와 연결되어 있을 때 위 노드를 parent, 아래 노드를 child라 합니다. 

자식노드가 없는 노드를 leaf 노드라고 합니다. 

이진트리

직접 연결되지 않은 노드라도 연결된 에지를 통해 방문할 수 있습니다. 

한 노드에서 다른 노드로 도달하는 데 사용한 에지의 모음을 경로(path)라고 합니다. 

모든 노드를 일정한 순서로 방문하는 것을 트리 순회(tree traverasal) 또는 트리 탐색이라 합니다. 

 

트리를 레벨로 구분하기도 합니다. 루트는 레벨0 그 자식들은 레벨 1이 되는 식입니다.

총 레벨을 수를 트리의 깊이라고 합니다.

 

이진트리란?

 

이진 트리(binary tree)는 모든 노드의 자식 노드가 2개 이하인 특수한 트리입니다. 

 

이진 검색 트리란?

 

이진 트리 중에 이진 검색 트리(binary search tree)라는 트리가 있습니다. 

좌측 자식 노드엔 부모보다 작은 값을 우측 자식 노드에는 부모보다 큰 값을 저장합니다. 

이렇게 미리 배치를 해두면 아주 효율적으로 검색을 할 수 있습니다. 

 

코딩하기

 

먼저 node class를 만들겠습니다. 

class Node:

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

 

이진 검색 트리 (binary search tree) class를 만들어 봅니다. 

먼저 입력 메서드까지 만들어 보겠습니다. 

class Node:

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


class BST:

    def __init__(self):
        self.root = None

    def insert(self, new_item):

        new_node = Node(new_item)

        if self.root is None:
            self.root = new_node
            return

        current = self.root  #

        while True:
            parent = current  #
            if new_item < current.item:
                current = current.left  #
                if current is None:
                    parent.left = new_node  #
                    break
            else:
                current = current.right  #
                if current is None:
                    parent.right = new_node  #
                    break


boo = BST()
boo.insert(5)
boo.insert(2)

파이썬에서 사용되는,
객체의 바인딩 개념을 가지고 보지 않으면
# 으로 마킹해둔 부분들이 혼란스러울 수 있습니다. 

 

간략하게 말씀 드리면,
파이썬에서 a객체 = b객체를 하면
값이 복사(copy)되는 것이 아니라
연결(binding)만 생깁니다. 

 

객체를 값을 담을 수 있는 상자로 보지 말고,
포스트 잇으로 생각하라는 말이 도움이 될 것 같습니다.