이진탐색트리(노드 구현, 삽입, 탐색)

이번 글에서는 탐색 기법 중 이진탐색트리에 대해 알아본 후

이진탐색트리에 사용되는 노드를 구현, 삽입, 탐색에 대해 알아보고 구현해보도록 하겠습니다.

 

 

 

 

why?

설명하기에 앞서 이진탐색트리라는 기법은

왜 사용하는 걸까요?

 

---

1. 구조가 단순하다.

2. 쉽게 노드의 키들의 정렬된 결과를 얻을 수 있다.

3. 이진 검색과 비슷한 방식으로 아주 빠르게 탐색 할 수 있다.

---

 

 

 

 

 

 

 

 

 

 

이진탐색트리

"이진탐색트리"란

이진탐색(binary search)의 개념을 트리 형태의 구조에 접목한 자료 구조

를 의미합니다.

 

또한 이 기법을 사용하기 위해서는 지켜야 할 조건이 있는데

 

각 노드의 키가 왼쪽 서브트리에 있는 키들보다는 커야하며,

오른쪽 서브트리에 있는 키들보다는 작아야 합니다.

첫 번째 그림처럼 키 30 기준 오른쪽 노드의 키는 30보다 커야하지만

20으로 30보다 작기 때문에 이진탐색트리의 조건에 충족되지 않습니다.

 

세 번째 그림은 키가 80인 노드의 왼쪽 자식노드의 키가 10인데

루트 키 값이 50이므로 루트 노드의 오른쪽 서브트리의 키 값은 50을 넘어야합니다.

하지만 10은 50보다 작으므로 이진탐색트리의 조건에 충족되지 않습니다.

 

 

 

 

 

 

 

 

 

 

이진탐색트리의 구조

이진탐색트리의 구조를 크게 살펴보자면 다음과 같습니다.

특정 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있습니다.

반대로 오른쪽 서브트리에는 그 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있습니다.

 

또한 루트의 왼쪽 서브트리와 오른쪽 서브트리는 이진탐색트리입니다.

 

 

 

 

 

 

 

 

 

 

 

노드 구현

이진탐색트리는 기본적으로 노드를 이용하여 구현됩니다.

 

이때 사용되는 노드는 총 4가지의 정보를 담고 있습니다.

 

---

'key' : 탐색에 사용할 키 값을 저장

'value' : 값을 저장

'left' : 왼쪽자식 참조

'right' : 오른쪽 자식 참조

---

class Node:
	def __init__(self, key, value):
    	self.key = key   # 키
        self.value = value   # 값
        self.left = None   # 왼쪽자식
        self.right = None   # 오른쪽자식

 

 

 

 

 

 

 

 

 

 

 

노드 삽입

기존의 이진탐색트리에 새로운 노드를 삽입합니다.

 

이때 노드를 삽입한 후 트리의 형태가 이진탐색트리의 조건을 계속 만족해야합니다.

 

 

 

삽입 연산이란 이진탐색트리에 새로운 노드를 삽입하는 것을 의미합니다.

---

먼저 삽입하는 키를 k라고 하면,

k가 루트 키보다 작으면 왼쪽서브트리에 삽입하고,

k가 루트 키보다 크면 오른쪽서브트리에 삽입합니다.

 

만약, k가 루트의 키와 같다면 루트의 value를 교체합니다.

 

위 과정을 서브트리에서 반복하여 삽입 위치를 정하였다면

새로운 노드를 삽입 위치에 추가합니다.

---

 

 

 

 

예시로 1을 이진탐색트리에 삽입하는 과정입니다.

 

 

 

 

 

 

그렇다면 재귀적 방법으로 노드를 삽입해보겠습니다.

---

먼저 서브트리의 루트노드를 sroot라 합니다.

 

sroot의 키 보다 삽입할 키가 작으면, 

sroot의 왼쪽 서브트리에 노드 삽입하는 재귀함수를 호출하고

 

반대로 sroot의 키보다 삽입할 키가 크다면,

sroot의 오른쪽 서브트리에 노드 삽입하는 재귀함수를 호출합니다.

 

 

---

 

 

 

 

 

 

 

 

 

 

노드 삽입 구현

삽입 연산에 사용되는 메소드는 2가지입니다.

---

insert() : 전체트리에 노드를 삽입

insert_to_subtree() : 서브트리에 노드를 삽입

---

class BinarySearchTree:
    def __init__(self):
        self.root = None
        
    def insert(self, key, value):
        if self.root:  # 루트노드 존재
            self.insert_to_subtree(key, value, self.root)
        else:  # 루트노드 없음
            self.root = Node(key, value)
            
    def insert_to_subtree(self, key, value, sroot):
        
        if key < sroot.key:  # key가 서브트리의 루트의 키보다 작다면
            if sroot.left:  
                # sroot의 왼쪽자식이 있으면, sroot의 왼쪽서브트리에 노드 삽입
                self.insert_to_subtree(key, value, sroot.left)
            else:
                # sroot의 왼쪽자식이 없으면, sroot의 왼쪽자식으로 노드 삽입
                sroot.left = Node(key, value)
                
            elif key > sroot.key:  # key가 서브트리의 루트의 키보다 크면
                if sroot.right:
                    # sroot의 오른쪽 자식이 있으면, sroot의 오른쪽서브트리에 노드 삽입
                    self.insert_to_subtree(key, value, sroot.right)
                else:
                    # sroot의 오른쪽자식이 없으면, sroot의 오른쪽자식으로 노드 삽입
                    sroot.right = Node(key, value)

 

 

 

 

 

 

 

 

 

 

노드 탐색

탐색연산이란 키 값으로 노드를 탐색하는 함수를 의미합니다.

---

탐색하는 키를 k라고 할때, k와 루트의 키를 비교합니다.

 

k == 루트키

탐색에 성공했으므로 루트의 값을 리턴

 

k < 루트키

왼쪽 서브트리에서 k를 탐색

만약 서브트리가 없다면 탐색 실패

 

k > 루트키

오른쪽 서브트리에서 k를 탐색

만약 서브트리가 없다면 탐색 실패

---

 

 

 

 

 

탐색 성공 예시

주어진 이진탐색트리에서 4를 탐색

 

 

탐색 실패 예시

주어진 이진탐색트리에서 3을 탐색

 

 

 

 

 

 

 

 

 

 

노드 탐색 구현

노드 탐색에 사용되는 메소드는 2가지입니다.

---

find() : 전체트리에서 노드를 탐색

find_in_subtree() : 서브트리에서 노드를 탐색

---

def find(self, key):
    # 전체트리에서 노드 탐색 후 값 리턴
    return self.find_in_subtree(key, self.root)

def find_in_subtree(self, key, sroot):
    # 서브트리에서 노드 탐색 후 값 리턴
    if not sroot:
        return None
    elif key == sroot.key:
        return sroot.value
    elif key < sroot.key:
        return self.find_in_subtree(key, sroot.left)
    else:
        return self.find_in_subtree(key, sroot.right)