Computer Science/Algorithm

[책] 누구나 자료구조와 알고리즘 - 15장 이진 탐색 트리로 속도 향상 (1/2) 검색, 삽입

지안22 2024. 1. 22. 18:01

데이터를 자주 정렬해야 한다면 항상 정렬된 순서로 유지하는 것이 좋다.

- 정렬 알고리즘은 아무리 빨라도 O(NlogN)의 시간이 걸리기 때문이다.

정렬된 배열은 읽기에는 O(1), (이진)검색에는 O(logN)으로 우수한 성능을 낸다.

- 하지만 삽입, 삭제 시에는 O(N)이 걸리기 때문에 비교적 느리다.

해시 테이블은 O(1)로 전반적으로 빠른 속도를 내지만, 순서를 유지하지는 못한다.

 

순서를 유지하면서도 빠른 검색, 삽입, 삭제가 가능한 자료구조를 알아보자.

트리

노드 기반 자료구조이고, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.

트리에 쓰이는 용어

  • 가장 상위 노드를 루트(root) 노드라고 부른다. - 가장 꼭대기의 "j"
  • "j"를 "m"과 "b"의 부모(parent)라 한다. 반대로 "m"과 "b"은 "j"의 자식이다.
  • 패밀리 트리에서는 노드에 자손(descendant)과 조상(ancestor)이 있을 수 있다.
    • 한 노드의 자손은 그 노드에서 생겨난 모든 노드이며, 한 노드의 조상은 그 노드를 생겨나게 한 모든 노드다.
    • 모든 노드는 "j"의 자손이다.
  • 트리에는 레벨(level)이 있다. 각 제벨은 트리에서 같은 줄(row)이다.
  • 트리의 프로퍼티(property)는 균형 잡힌 정도를 말한다.
    • 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리다.

균형 이진 트리
불균형 이진 트리

이진 탐색 트리 (binary search tree)

 

트리에 이진(binary)과 탐색(search)이라는 수식어 두 개가 붙는다.

 

이진 트리: 각 노드에 자식이 0, 1, 2개다.

이진 탐색 트리: 다음의 규칙이 추가된 트리다.

  • 각 노드의 자식은 최대 "왼쪽"에 하나, "오른쪽"에 하나다.
  • 한 노드의 "왼쪽" 자손은 그 노드보다 작은 값만 포함할 수 있다. 
  • 한 노드의 "오른쪽" 자손은 그 노드보다 큰 값만 포함할 수 있다.

이진 트리 & 이진 탐색 트리
이진 트리 O, 이진 탐색 트리 X

# 파이썬 코드
class TreeNode:
    def __init__(self,val,left=None,right=None):
    	self.value = self
        self.leftChild = left
        self.rightChild = right
node1 = TreeNode(25)
node2 = TreeNode(75)
root = TreeNode(50, node1, node2)

검색

  1. 노드를 현재 노드로 지정한다. (루트 노드 부터 시작)
  2. 현재 노드의 값을 확인한다.
  3. 찾고 있는 값이 현재 값보다 작으면 왼쪽 하위 트리를 검색한다.
  4. 찾고 있는 값이 현재 값보다 크면 오른쪽 하위 트리를 검색한다.
  5. 찾고 있는 값을 찾았거나, 트리의 바닥에 닿을 때 까지(=못찾을 경우) 1단계부터 반복한다.

61을 찾을 때, 총 4단계가 걸린다.

각 단계마다 검색할 대상이 남은 노드의 반으로 줄어든다.

오른쪽 자식을 검색하기로 결정하는 순간 왼쪽 자식과 그 자식의 모든 자손은 검색에서 제외된다.

이진 탐색 트리는 검색은 O(logN)이 걸린다. (최선의 시나리오인 균형 포화 이진 탐색 트리에서만)

  • 균형 포화 이진 탐색 트리: 균형 트리 + 포화 트리 + 이진 탐색 트리
    • 균형 트리: 모든 노드의 자식 노드가 0 아니면 2개인 트리
    • 포화 트리: 왼쪽 하위 노드와 오른쪽 하위 노드의 높이차가 최대 1인 트리
    • 그림 참고 : https://wonit.tistory.com/198

이진 트리에 노드가 N개면 레벨(=줄, 높이)이 약 logN개이다.

예시) 레벨이 4인 이진 트리가 완전히 채워져 있을 때 노드는 15개다.

따라서 노드가 N개인 트리에서 모든 자리마다 노드를 두려면 log(N)레벨이 필요하다.

이진 탐색 트리의 검색은 정렬된 배열의 이진 검색과 효율성이 같다.

 

이진 트리 탐색 연산에는 재귀가 많이 활용된다.

  • 재귀는 임의의 깊이 만큼 들어가야하는 자료구조를 다룰 때 필요하다. (= 레벨이 무한한 트리)
def search(searchValue, node):
	# 기저 조건: 노드가 없거나, 찾고 있던 값이면
    if node is None or node.value == searchValue:
    	return node
        
    # 찾고 있는 값이 현대 노드보다 작으면, 왼쪽 자식을 검색한다.
    elif searchValue < node.value:
    	return search(searchValue, node.leftChild)
    
    # 찾고 있는 값이 현재 노드보다 크면, 오른쪽 자식을 검색한다.
    else: # searchValue < node.value
    	return search(searchValue, node.rightChild)

삽입

이진 탐색 트리는 삽입에 가장 뛰어나다.

검색 후에 삽입이 일어난다.

'45' 삽입

검색 4단계 + 삽입 1단계가 걸렸다.

즉, (logN) + 1 단계이며, 빅 오는 상수는 무시하므로 총 O(logN) 단계가 걸렸다.

 

정렬된 배열에서는 삽입에 O(N)이 걸린다.

  • 검색 O(logN) + (삽입 될 공간 마련을 위해 데이터 오른쪽으로 시프트 +) 삽입 O(N) 의 과정을 거친다.

반면, 이진 트리는 검색과 삽입 모두 O(logN)이므로 매우 효율적이다.

def insert(value, node):
    if value < node.value:
    
    	# 왼쪽 자식이 없으면 왼쪽 자식으로서 값을 삽입한다.
    	if node.leftChild is None: 
        	node.leftChild = TreeNode(value)
        else:
        	insert(value, node.leftChild)
            
    elif value >  node.value:
    
    	# 오른쪽 자식이 없으면 오른쪽 자식으로서 값을 삽입한다.
        if node.rightChild is None:
        	node.rightChild = TreeNode(value)
        else:
        	insert(value, node.rightChild)

 

무작위로 정렬된 데이터로 트리를 생성해야 대개 균형 잡힌 트리가 생성된다.

정렬된 데이터로 트리를 생성하면 불균형이 심하고, 덜 효율적일 수 있다.

무작위 정렬된 데이터로 트리 생성. 검색 시 O(logN) 소요
정렬된 데이터로 트리 생성. 검색 시 O(N) 소요