Binary Search Tree (BST)

# 이진 탐색 트리

트리구조는 그 자체만으로 데이터의 특성에 아무런 제약이 없습니다. 그래서 어떤 특정한 값을 찾기 위해서는 트리의 모든 데이터를 탐색해야합니다. 데이터 N개만큼의 탐색이 이루어져야하기 때문에 시간복잡도에 있어 별다른 이점이 없게 됩니다. 이진 탐색 트리는 데이터 특성에 제약을 줌으로써 탐색 속도를 binary search처럼 O(logN)까지 줄여줍니다.

이진탐색 트리는 기본적으로 왼쪽과 오른쪽 자식노드를 가질 수 있는 이진트리의 구조입니다. 일반적인 이진트리와의 차이는 데이터값에 제약이 생긴다는 것인데, 이진탐색트리에서 루트노드를 기준으로 왼쪽서브트리에는 루트노드보다 작은값, 오른쪽 서브트리에는 루트노드보다 큰값으로 이루어져있습니다.(중복된 값은 없어야 합니다) 또 이 서브트리들은 이진탐색트리로 구성되어 있어야 합니다.

이진 탐색 트리의 최솟값은 트리의 레벨에 상관없이 트리의 제일 왼쪽끝에 위치한 노드가 가지고 있게 됩니다.  반대로 트리의 최댓값은 트리의 레벨에 상관없이 트리의 제일 오른쪽 끝에 위치한 노드가 가지고 있습니다.

그래서 이진탐색트리는 루트데이터의 값이 왼쪽값보다 크고, 오른쪽보다 작기 때문에 왼쪽-루트-오른쪽으로 방문하는 중위탐색을 할 경우에는 모든 데이터 값을 정렬된 순서로 가져올 수 있다는 특징이 있습니다.

 

# 코드 구현 (Python)

Binary Search Tree는 서브트리들도 재귀적인 특성을 가지고 있기 때문에, 연산들도 모두 재귀함수로 구현합니다.

데이터 삽입 연산에서 쓰일 Node생성 클래스를 만들어주고, BST 클래스를 만들어서 기본값을 설정해줍니다.

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

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

[ insert ] 

기본적으로 이진탐색트리에는 중복된 값을 삽입하지 않기 때문에 데이터의 삽입이나 삭제가 이루어져도 그 특성은 유지되어야합니다. 그래서 데이터가 삽입될 때에는 자신이 들어가야할 위치부터 찾아야하는데, 트리에 중복데이터가 있을 경우 삽입을 하지 않고 그대로 연산이 종료하게 됩니다. 추가된 노드는 트리의 leaf노드에 추가 되어야합니다. 그래서 값비교를 하기 위해서 루트노드부터 타고 들어가서 값비교를 해야합니다.

def insert(self, value):
    self.root = self.insert_node(self.root, value)
    self.size += 1

# 연산은 모두 재귀호출로 이루어지기 때문에 insert_node메서드를 정의해줍니다.
def insert_node(self, node, value):
    if node is None:
        return Node(value)
        
    if value < node.data:
        node.left = self.insert_node(node.left, value)
    elif value > node.data:
        node.right = self.insert_node(node.right, value)
    return node

self.root = self.insert_node(self.root, value)

우선 insert메서드 호출될 때, 제일 먼저 insert_node에는 루트노드가 들어오게 됩니다.

if node is None:
    return Node(value)

그리고 루트가 None인 경우, 삽입할 위치를 찾은 것이기 때문에 우리가 추가해줄 value노드를 새로 생성해서 바로 반환을 하고, 이 생성된 노드가 루트에 들어가게 됩니다.

if value < node.data:
    node.left = self.insert_node(node.left, value)
elif value > node.data:
    node.right = self.insert_node(node.right, value)

루트가 비어있지 않은 경우 if문을 통해 값비교를 하면서 왼쪽 혹은 오른쪽을 찾아서 들어가게 됩니다. 들어가서 또 insert_node를 재귀호출해서 위의 과정을 반복하면서 쭉쭉 타고 내려오게 됩니다.

return node

그리고 위치를 찾게 되면 그 위치에 노드를 새로 생성해서 반환합니다. 이 반환된 값이 left/ right에 각각 들어가게 되고 호출이 종료되는 시점에는 우리가 제일 먼저 호출했던 루트가 반환되면서 그 새로운 루트값이 다시 들어가게 됩니다.

 

[ delete ] 

삭제 연산에서는 leaf노드 뿐만아니라 중간에 위차한 노드가 삭제될 수 있습니다. 그래서 삭제할 데이터의 위치를 찾은 다음에 삭제할 데이터가 leaf노드에 있을 경우, 한개의 자식 노드를 가질경우, 두개의 자식노드를 가질 경우를 다 생각해봐야합니다.

1. leaf노드인 경우

null을 부모노드에게 return시켜서 자신을 가리키는 자식 포인터를 null로 바꿔줍니다.

2. 한 개의 자식노드를 가질 경우

하나 있는 자식노드를 부모노드로 보내주면 됩니다(자식노드가 왼쪽이든 오른쪽이든 동일하게 적용)

3. 두 개의 자식노드를 가질 경우

왼쪽 서브트리의 최댓값과 교체 혹은 오른쪽 서브트리의 최솟값과 교체 후 기존 노드를 삭제합니다. (위의 경우 왼쪽 서브트리에 자식노드가 없으므로 오른쪽 서브트리에서의 비교를 통해서 값을 교체해줍니다)

def delete(self, value):
    return self.delete_node(self.root, value)

def delete_node(self, node, value):
    if node is None:
        return None

    if value < node.data:
        node.left = self.delete_node(node.left, value)
    elif value > node.data:
        node.right = self.delete_node(node.right, value)
    else:
        self.size -= 1
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        node.data = self.min_node(node.right)
        node.right = self.delete_node(node.right, node.data)
    return node

if value < node.data:
    node.left = self.delete_node(node.left, value)
elif value > node.data:
    node.right = self.delete_node(node.right, value)

지워야할 데이터가 있는 위치를 찾기 위해서 if문을 통해 값비교를 해가면서 찾아나갑니다. value가 노드의 값보다 작으면 왼쪽 어딘가에 위치가 있을 것이고, 크다면 오른쪽 어딘가에 위치가 있을 것입니다

else:
    self.size -= 1

타깃을 찾은 경우에 이 노드를 지워줘야 하는데,

    if node.left is None:
        return node.right
    elif node.right is None:
        return node.left

지워줄 위치가 leaf노드인 경우(left와 right가 모두 None인 경우), None을 부모노드에 리턴시켜서 더 이상 leaf노드가 자신을 가리키지 않게 하고, 한 개의 자식을 갖는 경우 하나 있는 자식노드를 부모노드로 보내주면 됩니다

위의 두 경우가 아닐 떄는 두 개의 자식노드를 가질 때인데, 두 경우로 나뉘어서 오른쪽 서브트리의 최솟값을 가져오는 것과왼쪽 서브트리의 최대값을 가져오는 것입니다

    node.data = self.min_node(node.right)
    node.right = self.delete_node(node.right, node.data)

그래서 min_node메서드를 사용해서 오른쪽 서브트리의 최솟값을 가져오는데 그냥 두면 값이 중복되니까 delete_node메소드를 재귀호출하여 삭제해줍니다 (*min_node메서드는 깃허브를 참고해주세요)

return node

그리고 마지막에 노드를 반환함으로써 함수를 종료시킬 수 있습니다.

if node is None:
    return None

원하는 타겟을 찾지 못한경우 None을 반환합니다

 

# 전체 코드

전체 코드와 다른 기능 함수들(contains, min_node 등), 테스트 코드는 깃허브를 참고하시면 됩니다.

GitHub - sonzwon/TIL: Today I Learned