Python: Binary Tree

Linear Search vs Binary Search

👉🏻 선형 탐색이나 이진탐색의 요소는 오름차순이나 내림차 순으로 되어있어야 적용할 수 있다.

Linear Search

• for문을 돌려 첫 index 부터 하나하나 찾아나가며 원하는 요소를 탐색한다.

• 배열의 길이가 길어질수록 탐색을 여러번 해야하므로 실행 속도가 느려지고 효율적이지 않은 로직이 된다.

Binary Search

• 순서대로 찾는 것이 아니라 중간부터 탐색한다.

• 오름차 순으로 정렬 되어있을 경우, 첫번째로 중간 위치의 요소를 비교하고 찾아야 할 값보다 크면 왼쪽 중간에서 다시 비교한다.

Binary Tree(이진 트리)란?

Tree란❓

• Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조.

• 최대 두개의 자식 노드를 가진 트리 형태의 자료 구조로 단순히 값을 저장하는 용도보다는 효율적인 탐색이나 정렬을 위해 사용한다.

• 주어진 값이나 이보다 작거나 큰 값들을 평균 O(log n)의 시간 복잡도로 탐색 가능하다.

✔️ 기본 용어
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node : 트리 맨 위에 있는 노드
Level : 최상위 노드를 level 0 으로 하였을 때, 하위 branch로 연결된 노드의 깊이
Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
Child Node : 어떤 노드의 상위 레벨에 연결되 노드
Leaf Node : Child Node 가 하나도 없는 노드
Sibling : 동일한 Parent Node를 가진 노드
Depth : 트리에서 Node가 가질 수 있는 최대 level

Binary Search Tree(이진 탐색 트리)

• 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하다.

• 이진 탐색 트리란 이진 트리에 특정 조건이 추가된 경우인데, 그 조건은 다음과 같다.

  👉🏻 모든 노드에 대하여 왼쪽 자식 노드들의 값이 현재 노드보다 값이 작거나 같으며, 오른쪽 자식 노느들의 값이 현재 노드의 값보다 크다는 조건을 만족하여야 한다.

• 맨 먼저 입력된 값이 root 노드가 되며 그 다음부터는 입력값과 노드 간 대소관계에 따라 입력값의 노드 위치가 달라진다.

• 이진 탐색 트리는 트리의 좌우 균형이 맞는다면 정렬된 배열보다 효과적으로 원하는 값을 탐색할 수 있다.

• 그 중 예외인 경우는 이진트리에 오름차순이던, 내림차순이던 정렬된 데이터가 입력되면 한쪽으로 치우친 (skewed) 트리가 만들어지기 때문에 최악의 경우 모든 데이터를 살펴야 할수도 있어 시간복잡도가 O(n)이 된다.

클래스 정의

• 이진 탐색 트리 구현시에는 먼저 Node 클래스를 정의해야 하는데, 노드 값인 self.data와 왼쪽 / 오른쪽 노드인 self.left, self.right의 속성을 가진다.

• 초기화시에는 데이터의 값만 주어지고 좌우 노드는 비어있게된다.

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

• Node 클래스를 사용해 이진 탐색 트리 클래스를 구현하고 여기에 원소를 추가, 삭제, 탐색할 수 있도록 insert(), delete(), find() 메서드를 추가한다.

class BinarySearchTree(object):
    def __init__(self):
        self.root = None

insert()

• 재귀를 사용하여 새로 추가할 원소의 값을 현재 노드의 값과 배교하여 왼쪽, 오른쪽 중 알맞은 위치로 노드를 옮겨가며 삽입 위치를 확인한다.

class BinarySearchTree(object):
    ...
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None

    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node

find()

• 원하는 값의 존재 유무를 확인할 수 있도록 재귀와 값의 대소 관계를 비교하여 구현한다.

class BinarySearchTree(object):
    ...
    def find(self, key):
        return self._find_value(self.root, key)

    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)

---

[ Ref ]
https://www.fun-coding.org/Chapter10-bst.html
http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html