[알고리즘] 이진 검색 트리

이진 검색 트리에는 3가지 특징이 있다.

1. 이진 검색 트리의 각 노드는 키 값(=노드 값)을 하나씩 갖는다. 각 노드의 키 값은 모두 달라야 한다.
2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
3. 임의의 노드의 키 값은 자신의 왼쪽에 있는 모든 노드의 키 값보다 크고, 오른쪽에 있는 모든 노드의 키 값보다 작다.(!트리의 조건은 아니지만 관리를 용이하게 하기 위함)

위와 같은 형태가 되는데 보다 싶이 좌측 서브 트리포함 모든 값들은 루트 노드보다 작다.

이진 검색 트리에서 검색

이렇게 하면 검색도 용이하다.

Python코드로 짜보자면

우선 노드와 트리를 정의한다.

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

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

def treeSearch(root, key):
	if root is None || root.key == key:
    	return root is not None
    elif root.key > key:
    	treeSearch(root.left, key)
    else:
    	treeSearch(root.right, key)

Search실패하면 찾는 값이 없는 것이다.

이번에는 삽입을 해보자
최악의 검색 시간은 Θ(logn)이다.
가장 나쁘게 기울면 평균 검색 시간이 Θ(n)이 된다.

이진 검색 트리에서 삽입

[30, 20, 25, 40, 10, 35]를 순차적으로 삽입한다.

def treeInsert(root, key):
    if root is None:
    	root = Node(key) 
    elif root.key > key: 
    	treeInsert(root.left, key)
    
    else:
    	treeInsert(root.right, key)

삽입 역시도 가능한 모든 삽입 순서에 따른 이진 검색 트리를 모두 고려하면 평균 검색 시간은 Θ(logn)이다.

삽입은 실패하는 검색 후 상수 시간의 후처리를 하므로 점근적 수행 시간은 검색과 동일하다.

이진 검색 트리에서 삭제

이진 검색 트리에서 노드 r을 삭제하고자 할 때는 다음 세가지 경우에 따른 각각 다르게 처리를 해주어야 한다.

• r이 리프 노드인 경우
• r의 자식 노드가 하나인 경우
• r의 자식 노드가 두 개인 경우

1과 2는 처리가 간단하지만 3은 비교적 다소 복잡하다.

def treeDelete(root):
	if root.left == None and root.right == None: //리프 노드인 경우
    	root = None
    elif root.left == None xor root.right == None: //자식이 하나인 경우
    	if root.left is None:
        	root = root.right
        else:
        	root = root.left
    else://r의 자식 노드가 두 개인 경우
        child = root.left
    	while(child != None):
        	child = child.left
        root.key = child.key
        treeDelete(child)

• 자식이 없는 경우 삭제만 한다.
• 자식이 하나만 있는 경우 삭제하고 부모노드와 자식노드를 잇는다.
• 자식이 둘 있는 경우 우축 서브 트리의 값 중 가장 작은 값(즉 우측 서브 트리의 최좌측 leaf노드 값)을 넣고 다시 Delete메소드를 그 노드에 실행한다.