검색 트리

1. 레코드, 키의 정의 및 검색 트리

레코드는 개체에 대한 모든 정보를 포함한다. 예를들어 사람의 레코드이면 주민번호, 이름, 집주소등이 있다. 여기서 정보를 나타내는 부분을 필드라고 한다. 

검색트리는 이런 레코드를 저장하고 검색하는 것이다. 이러한 레코드를 전부다 저장할 수 있지만 보통은 대표레코드인 키를 두어서 이를 이용한다. 예를들어 사람의 레코드에서 키가 될 수 있는 것은 겹칠 수가 없는 주민번호가 있다. 

이러한 검색트리는 이진트리와 다진트리로 나누어진다. 이진트리는 한 노드에서 최대 두개의 자식노드를 가지고 다진 트리는 2개이상을 가질 수 있는 것을 의미한다. 

 

2. 이진 검색 트리

이진 검색트리의 특징은 아래와 같다. 

1. 이진 검색 트리의 각 노드는 키 값을 하나씩 가진다. 각 노드의 키 값은 모두 다르다.

2. 최상위 레벨에 루트 노드가 있고 각 노드는 최대 두개의 자식 노드를 가진다. 

3. 임이의 노드의 키 값은 자신의 왼쪽에 있는 모든 노드의 키 값보다 크고 오른쪽에 있는 모든 노드의 키 값보다 작다. 

 

이진 검색트리의 시작 코드는 아래와 같다. 

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

1) 이진 검색 트리에서 검색

코드는 아래와 같다. 

def search(self, x):
  #t is root of the Tree
  t = self.root       
  while True:
    if t is None:
    	return None
    elif t.key == x:
    	return t
    elif t.key > x:
    	t = t.left
    else:
    	t = t.right

검색을 하면서 현재 키에서 찾을 수 없다면 왼쪽 또는 오른쪽 서브트리에서 찾고 만일 리프노드까지 갔는데 존재하지 않는다면 None을 return한다. 

 

2) 이진 검색 트리에서 삽입

코드는 아래와 같다. 

def treeInsert(self, x, value):
        #재귀를 위해 함수안에 또다른 함수를 넣는다. 
        def add_node(node:Node, key = x, value = value):
            if key == node.key:
                return False
            elif key <node.key:
                if node.left is None:
                    node.left = Node(key, value)
                else:
                    add_node(node.left, key, value)
            else:
                if node.right is None:
                    node.right = Node(key, value)
                else:
                    add_node(node.right, key, value)
            return True
        
        if self.root is None:
            self.root = Node(x, value)
            return True
        else:
            return add_node(self.root, x, value)

검색 트리에서는 같은 키가 있으면 안된다. 우선 트리의 루트가 없다면 삽입하고자하는 노드를 루트로 한다. 그것이 아니라면 트리를 따라서 내려가는데 따라서 만약 키가 같은 것이 있다면 False를 출력한다. 그다음 현재 서브트리의 루트의 키값보다 작다면 그 루트의 왼쪽 서브트리를 보는데 만일 NULL이면 그곳에 삽입하고 아니라면 왼쪽 서브트리의 루트를 기준으로 다시 add_node를 실행한다. 그반대도 마찬가지 이다. 이를 그림으로 나타낸것이 다음과 같다.

위의 경우는 좌우 균형이 잘 맞는 경우이다. 위의 경우에서 검색을 한다면 시간복잡도는 트리의 높이인 Θ(logn)이 나올 것이다. 하지만 아래처럼 한쪽으로 치우친 트리가 나올 수 도 있다. 

이 경우는 검색시간이 Θ(n)이다. 하지만 평균적으로는 Θ(logn)이다. 삽입은 검색후에 상수시간을 걸려 노드를 달아주기만 함으로 역시 Θ(n)이다. 

그렇다면 왜 평균 높이가 Θ(logn)일까? 우선 그전에 IPL을 알아보자. IPL은 이진 트리에서 각 노드의 깊이를 더한 내부 경로 길이이다. 그 예시는 아래와 같다.

 이 총 길이를 노드의 수로 나누면 평균 깊이가 나온다. 그렇다면 일반화를 위해 D(n)을 키가 n개인 모든 이진 검색 트리의 평균 IPL이라고 하자. 그러면 아래와 같은 결과가 나오게 된다.

D(n) = O(nlogn)임으로 n개의 노드의 갯수로 나누면 평균 깊이인 O(logn)이 나오게 된다. 

 

3. 이진 검색 트리에서 삭제

이진 검색 트리에서의 삭제는 3가지 경우가 있다. 

 

1) 삭제하고자하는 노드(r)이 리프 노드인 경우

이때는 그냥 r의 parent의 right 또는 left를 None으로 바꿔주면 된다. 

 

2) 삭제하고자 하는 노드(r)의 자식 노드가 하나인 경우

위와 같이 r의 부모의 left 또는 right를 r의 자식노드와 연결을 시키면 된다.

 

3) 삭제하고자 하는 노드(r)의 자식 노드가 2개인 경우

->

우선 제거하고자하는 노드 r을 찾은다음 그곳을 대체할 수 있는 노드를 찾아야한다. 대체할 수 있는 노드는 r의 left의 키보다는 커야되고 r의 right의 키보다는 작아야한다. 이는 r의 왼쪽 서브트리에서 가장 큰 원소 또는 오른쪽 서브트리에서 가장 작은 원소인데 여기서는 후자를 택하는 방법을 선택했다. 오른쪽 서브트리에서 가장 작은 원소는 r의 right를 root로한 트리에서 왼쪽으로 리프노드일때까지 가면 된다. 그 노드를 t라고 하면 t의 키값을 r에 대입하는 것이다. 그다음 t를 제거하는데 이때 무조건 case 1또는 2가 나온다. 따라서 case 1, 2를 적용하여 t를 제거하면 된다. 

 

위를 코드로 직접 구현해본것은 아래와 같다.

def treeDelete(self, key):
        cur = self.root
        parent_node = None
        cur_is_left = True
        #삭제할 노드 찾기
        while True:
            if cur is None:
                return False
            
            if cur.key == key:
                break
            
            else:
                if cur.key > key:
                    parent_node = cur
                    cur = cur.left
                    cur_is_left = True
                else:
                    parent_node = cur
                    cur = cur.right
                    cur_is_left = False
        print(cur_is_left)            
        remove_node = cur
        remove_parent = parent_node
        #removal 1
        if remove_node.left is None and remove_node.right is None:
            if cur_is_left is True:
                remove_parent.left = None
            else:
                remove_parent.right = None
            return True
        
        #removal 2
        if remove_node.left is None and remove_node.right is not None:
            if cur_is_left is True:
                remove_parent.left = remove_node.right
            else:
                remove_parent.right = remove_node.right
            return True
        elif remove_node.left is not None and remove_node.right is None:
            if cur_is_left is True:
                remove_parent.left = remove_node.left
            else:
                remove_parent.right = remove_node.left
            return True
        
        #removal 3
        else:
            temp = remove_node.right
            while temp.left is not None:
                remove_parent = temp
                temp = temp.left
            #key change
            remove_node.key, remove_node.value = temp.key, temp.value
            #remove
            if remove_node.right == temp:
                remove_node.right = temp.right
            else:
                remove_parent.left = temp.right
                
        return True

전체 이진 검색 트리의 코드는 아래와 같다.

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

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def search(self, x):
        #t is root of the Tree
        t = self.root       
        while True:
            if t is None:
                return None
            elif t.key == x:
                return t
            elif t.key > x:
                t = t.left
            else:
                t = t.right
        
        
    def treeInsert(self, x, value):
        #재귀를 위해 함수안에 또다른 함수를 넣는다. 
        def add_node(node:Node, key = x, value = value):
            if key == node.key:
                return False
            elif key <node.key:
                if node.left is None:
                    node.left = Node(key, value)
                else:
                    add_node(node.left, key, value)
            else:
                if node.right is None:
                    node.right = Node(key, value)
                else:
                    add_node(node.right, key, value)
            return True
        
        if self.root is None:
            self.root = Node(x, value)
            return True
        else:
            return add_node(self.root, x, value)
                 
            
    def treeDelete(self, key):
        cur = self.root
        parent_node = None
        cur_is_left = True
        #삭제할 노드 찾기
        while True:
            if cur is None:
                return False
            
            if cur.key == key:
                break
            
            else:
                if cur.key > key:
                    parent_node = cur
                    cur = cur.left
                    cur_is_left = True
                else:
                    parent_node = cur
                    cur = cur.right
                    cur_is_left = False
        print(cur_is_left)            
        remove_node = cur
        remove_parent = parent_node
        #removal 1
        if remove_node.left is None and remove_node.right is None:
            if cur_is_left is True:
                remove_parent.left = None
            else:
                remove_parent.right = None
            return True
        
        #removal 2
        if remove_node.left is None and remove_node.right is not None:
            if cur_is_left is True:
                remove_parent.left = remove_node.right
            else:
                remove_parent.right = remove_node.right
            return True
        elif remove_node.left is not None and remove_node.right is None:
            if cur_is_left is True:
                remove_parent.left = remove_node.left
            else:
                remove_parent.right = remove_node.left
            return True
        
        #removal 3
        else:
            temp = remove_node.right
            while temp.left is not None:
                remove_parent = temp
                temp = temp.left
            #key change
            remove_node.key, remove_node.value = temp.key, temp.value
            #remove
            if remove_node.right == temp:
                remove_node.right = temp.right
            else:
                remove_parent.left = temp.right
                
        return True