트리 (Tree) (2)

6. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

이진 탐색 트리의 구조 안에서 구현을 하려면, 노드가 있고, 각 노드마다 왼쪽 Branch, 오른쪽 Branch를 지칭하는 주솟값을 가지고 있다. 이러한 구조는 내부 구현은 링크드 리스트로 하면 편리하다. 

 

6.1. 노드 클래스 만들기

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

 

클래스로 해서 노드라는 구조를 만드는데, 하나의 노드는 사실 더블 링크드 리스트와 비슷하다. 두 개의 주소를 가지고 있는 것이다. 왼쪽, 오른쪽의 주소를 하나씩 가지고 있는 것이다. 주소를 넣을 때부터 Branch를 가지고 있는 노드를 넣을 필요는 없으니, self.left, self.right에 default 값을 받을 필요는 없고 바로 None으로 주솟값을 없애도 된다.

 

6.2. 이진 탐색 트리에 데이터 넣기

위에서 만든 노드 클래스를 사용해 이진 탐색 트리에 데이터를 넣으려면, 노드를 관리할 수 있는 NodeMgmt 클래스를 하나 만들어야 한다.

 

class NodeMgmt:
    def __init__(self, head):
        self.head = head	# NodeMgmt에 처음 들어가는 노드는 root node (=head)가 되는 것

    def insert(self, value):
        self.current_node = self.head	# 노드가 트리를 순회를 해야 한다. 순회할 때 현재 노드를 알고 있어야 해서 current_node이다. 우선 head로 설정한다.
        while True:
            if value < self.current_node.value:	# 새로 들어오는 데이터가 현재 노드보다 작다면 (즉, 왼쪽으로 가야 한다는 것)
                if self.current_node.left != None: # 왼쪽으로 갔는데 왼쪽에 노드가 이미 있다면
                    self.current_node = self.current_node.left	# 비교할 대상을 바꾸고 끝내는 것. 그리고 다시 돌아가서 처음부터 시작하는 것이다.
                else:	# 왼쪽으로 갔는데 왼쪽에 Branch가 생성이 아직 안 되었다면
                    self.current_node.left = Node(value)	# 그냥 데이터를 Branch를 만들어서 연결한다.
                    break	# 트리를 만들었으니 break를 하고 while 문을 나온다.
            else:	# 가져온 값이 원래 노드보다 작지 않다면 (즉, 오른쪽으로 가야 한다는 것. 같을 때에도 오른쪽으로 넣게 구성한 것이라고 볼 수 있다)
                if self.current_node.right != None:	# 오른쪽으로 갔는데 오른쪽에 노드가 이미 있다면
                    self.current_node = self.current_node.right	# 다시 순회하기 위해 비교할 대상을 바꾼다.
                else:	# 오른쪽으로 갔는데 오른쪽에 노드가 없다면
                    self.current_node.right = Node(value)	# 그냥 데이터를 Branch를 만들어서 연결한다.
                    break	# 트리를 만들었으니 break를 하고 while 문을 빠져나온다.

 

이진 탐색 트리에 데이터를 넣는 코드는 위와 같다.

 

6.3. 이진 탐색 트리 탐색

앞서 만든 이진 탐색 트리에 데이터를 넣는 코드가 잘 작동하는지 확인할 겸 탐색 코드를 만들어볼 것이다.

 

search라는 메서드를 만들 것인데, 이 메서드는 이진 탐색 트리에 특정 데이터를 저장하고 있는 노드가 있는지 없는지 확인하는 것이다.

 

class NodeMgmt:
    def __init__(self, head):
        self.head = head

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

    def search(self, value):
        self.current_node = self.head	# 순회를 하기 위해 head를 먼저 설정
        while self.current_node:	# while 구문으로 self.current_node가 있는지 확인한다. 이것이 None이 되면 while 구문은 종료된다.
            if self.current_node.value == value:
                return True	# 현재 노드의 값이 내가 찾고자 하는 값과 동일하다면 그냥 True를 리턴한다.
            elif value < self.current_node.value:	# 값이 현재 노드보다 작다면
                self.current_node = self.current_node.left	# current_node를 왼쪽에 있는 노드로 바꿔준다.
            else:	# 값이 현재 노드보다 크다면
                self.current_node = self.current_node.right	# current_node를 오른쪽에 있는 노드로 바꿔준다.
        return False	# while문을 전부 돌았는데 이진 탐색 트리에 찾는 노드가 없다면 그냥 False를 리턴한다.

 

탐색 코드는 위와 같다. 이제 지금까지 작성한 이진 탐색 트리가 잘 작동하는지 테스트 해보겠다.

 

head = Node(1)	# root node 생성
BST = NodeMgmt(head)	# NodeMgmt에 헤드 넣는다
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)

print(BST.search(8))
print(BST.search(-1))

 

 

 

이렇게 생성한 이진 탐색 트리 BST에 8이 있으니 True, -1이 없으니 False가 출력되는 것을 확인할 수 있다.

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료