[입문] 이분 탐색 나무를 해설하면서 자력 실장해 보았다

목적

데이터 구조를 일차원 목록에 컨볼 루션하면 구현이 쉬울 수 있지만 트리 데이터 구조에 대한 이해를 높이기 위해 노드 클래스를 정의하여 이진 검색 트리를 구현합니다.

내용

이진 탐색 트리 정의

2분 탐색 트리란, 순서 관계가 정의되고 있는 노드의 값(수치나 순열의 정의된 문자 등)을 가지는 2분 트리 데이터 구조이다.
　
나무 구조에 관해서는 여기를 참조

각 노드는 0,1,2 개의 자식 노드를 가지며, 스스로보다 값이 작은 것을 왼쪽 자식 노드, 큰 것을 오른쪽 자식 노드로 정의된다.

동치의 노드에 관해서는 필자가 조사한 한 엄밀한 정의를 확인할 수 없었기 때문에, 본 기사에서는 우자 노드에 포함한다.

경우에 따라서는 중복은 삭제하는 수법도 있으므로, 주의되고 싶다.

이진 탐색 트리의 본질

상기 정의를 위해 정점 노드보다 작은 값이 왼쪽 분목에, 큰 값이 오른쪽 분목에 저장되어있다. 이 구조는 이분 탐색 트리의 어느 위치를 잘라도 유지된다.

또한, 나무의 좌단이 집합의 최소치, 우단이 최대치가 되는 성질을 가지고 있다.

더 가는 순서 횡단(inoder traversal)으로 노드의 값을 출력하면, 집합이 오름차순 정렬되어 출력된다.


Wiki 이분 탐색 트리 참조

※오해하지 않도록 주석하지만 이 그림의 13은 오른쪽 끝이 아니다. 오른쪽 끝은 14이다.
13은 14 노드의 왼쪽 자식이므로 오른쪽 자식 노드가 아닙니다.

구현

이진 탐색 트리의 데이터 구조 구현을 위해 Node 클래스를 정의했습니다.

Node 클래스는 노드의 값으로서, self.data 와 왼쪽 아이 self.left 오른쪽 아이 self.right 의 값을 갖는다.
디폴트의 ​​좌자와 우자는 None 이다.

이진 탐색 트리 구현을 위해 BST 클래스를 정의했습니다.

constructor 으로, self.root 를 정의해 디폴트를 None 로 했다.
또한 새 노드를 추가하기 위해 self.insert(val)를 실행하고 있습니다.
방법의 소개는 아래에 나와 있습니다.

메소드로서 다음을 구현했다.
자세한 내용은 코드를 참조하십시오.
* 노드 추가
* 특정 값의 노드가 있는지 확인
* 최소값 얻기
* 최대값 얻기
* inoder로 값 출력

이하의 점이 이 데이터 구조의 재미라고 느꼈다.

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


class BST:
    def __init__(self, arr):
        self.root = None

        for val in arr:
            self.insert(val)

    def insert(self, val):
        if self.root is None:
            self.root = Node(val)

        else:
            node = self.root
            flag = True

            while flag:
                if node.data > val:
                    if node.left is None:
                        node.left = Node(val)
                        flag = False 
                        # whileを終了させるためにFalseをセットする
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(val)
                        flag = False
                    else:
                        node = node.right


    def find(self, node, val):
        if node is not None:
            if node.data == val:
                return True

            else:
                flag_left = self.find(node.left, val) 
                flag_right = self.find(node.right, val)

                if flag_left or flag_right:
                    return True

        return False

    def bst_min(self, node):
        if node.left is None:
            return node.data
        else:
           return self.bst_min(node.left) 
           #再帰で行きついた先の値を返したいときはreturn のあとに再帰関数を書く。traversalのときと用法が異なるので注意。

    def bst_max(self, node):
        if node.right is None:
            return node.data
        else:
            return self.bst_max(node.right)

    def inoder_traverse(self, node):
        if node is not None:
            self.inoder_traverse(node.left)
            print(node.data)
            self.inoder_traverse(node.right)

실행

import random

arr = [random.randint(1, 100) for _ in range(12)]
ins = BST(arr)
print('insert node list =>', arr)
print('Is there No.4 ->', ins.find(ins.root, 4))
print('root', ins.root.data)
print('min', ins.bst_min(ins.root))
print('max', ins.bst_max(ins.root))
print('--------------------------')
print('通りがけ順で出力するとsortされる')
ins.inoder_traverse(ins.root)

결과

insert node list => [48, 10, 21, 58, 61, 12, 5, 87, 35, 2, 7, 39]
Is there No.4 -> False
root 48
min 2
max 87
--------------------------
通りがけ順で出力するとsortされる
2
5
7
10
12
21
35
39
48
58
61
87

참고문헌