자료구조 - 이진 트리와 이진 검색 트리

이진 트리

 

: 노드가 left child와 right child만을 갖는 트리를 이진트리(binay tree)라고 한다. 이때 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다.

이진 트리의 구조

 

이진 트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 예를 들어 노드 B의 left child는 D이고, right child는 E이다.

또 왼쪽 자식을 루트로 하는 서브 트리를 왼쪽 서브트리(left subtree), 오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브 트리라고 한다. 

 

 

완전 이진 트리

 

루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리(complete binary tree)라고 한다.

 

노드를 채우는 법은 다음과 같다.

-  마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차 있습니다.

-  마지막 레벨에 한해서 왼쪽부터 오른쪽 노드를 채우되 반드시 끝까지 채우지 않아도 됩니다.

 

높이가 K인 완전 이진 트리가 가진 수 있는 노드의 수는 최대 2^k+1 - 1개이므로, n개의 노드를 저장할 수 있는 완전 트리의 높이는 log n이다.

스캔하는 순서대로 각 노드에 0,1,2..의 같을 주면 인덱스와 일대일로 대응시킬 수 있다.

 

 

이진 검색 트리 (binary search tree)

 

이진 검색 트리는 다음 조건을 만족해야 한다.

-  왼쪽 서브 트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.

-  오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.

 

따라서 키값이 같은 노드는 복수로 존재하지 않는다. 예를 들어 노드 5의 왼쪽 서브 트리인 노드 4, 1은 모두 5보다 작고, 오른쪽 서브 트리의 노드 7, 6, 9는 모두 5보다 크다.

이진 검색 트리를 중위 순회의 깊이 우선 검색으로 스캔하면 다음과 같이 노드의 키값을 오름차순으로 얻을 수 있다.

1 -> 4 -> 5 -> 6 -> 7 -> 9 -> 11 -> 1 -> 2 -> 13 -> 14 -> 15 -> 18 

 

이진 검색 트리는 다음과 같은 특징 때문에 알고리즘에서 폭넓게 사용되고 있다.-  구조가 단순하다.-  중위 순회의 깊이 우선을 통하여 노드 값을 오름차순으로 얻을 수 있다.-  이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다.-  노드를 삽입하기 쉽다.

 

 

<code>

 

 

from __future__ import annotations
from typing import Any, Type

class Node:
    '''이진 검색 트리의 노드'''
    def __init__(self, key: Any, value: Any, left: Node = None, right: Node = None):
        #생성자(construcotr). 4개의 매개변수로 전달받은 값을 각 필드에 대입한다.
        self.key = key # 키
        self.value = value # 값
        self.left = left # 왼쪽 포인터
        self.right = right # 오른쪽 포인터
        
class BinarySearchTree:
    '''이진 검색 트리'''
    def __init__(self):
        '''클래스의 유일한 필드로 루트에 대한 참조를 유지하는 root. 
        빈 상태의 이진 검색 트리 생성'''
        self.root = None  
        
    def search(self, key: Any):
        '''키가 key인 노드를 검색'''
        p = self.root
        while True:
            if p is None: # 더 이상 진행할 수 없으면 
                return None  # 검색 실패
            if key == p.key: 
                return p.value # 검색 성공
            elif key < p.key:
                p = p.left
            else:
                p = p.right
                
    def add(self, key: Any, value: Any):
        
        def add_node(node: Node, key: Any, value: Any):
            '''node를 루트로 하는 서브트리에 키가 key이고 값이 value인 노드를 삽입'''
            if key == node.key:
                return False # key가 이진 검색 트리에 이미 존재
            elif key < node.key:
                if node.left is None:
                    node.left = Node(key, value, None, None)
                else:
                    add_node(node.left, key, value)
            else:
                if node.right is None:
                    node.right = Node(key, value, None, None)
                else:
                    add_node(node.rigt, key, value)
            return True
        
        if self.root is None:
            self.root = Node(key, value, None, None)
            return True
        
        else:
            return add_node(self.root, key, value)
        
    def remove(self, key: Any):
        '''키가 key인 노드를 삭제'''
        p = self.root # 스캔 중인 노드
        parent = None # 스캔 중인 노드의 부모 노드
        is_left_child = True # p는 parent의 왼쪽 자식 노드인지 확인
        
        while True:
            if p is None: # 더 이상 진행할 수 없으면
                return False # 그 키는 존재하지 않음
            
            if key == p.key:
                break # 검색 성공
            
            else:
                parent = p # 가지를 내려가기 전에 부모를 설정
                if key < p.key: # key쪽이 작으면
                    is_left_child = True # 여기서 내려가는 것은 왼쪽 자식
                    p = p.left # 왼쪽 서브트리에서 검색

                else: # key쪽이 크면
                    is_left_child = False # 여기서 내려가는 것은 오른쪽 자식
                    p = p.right # 오른쪽 서브트리에서 검색
    
        if p.left is None: # p에 왼쪽 자식이 없으면
            if p is self.root:
                self.root = p.right
            elif is_left_child:
                parent.left = p.right # 부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
            else:
                parent.right = p.right # 부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
        elif p.right is None: # p에 오른쪽 자식이 없으면
            if p is self.root:
                self.root = p.left
            elif is_left_child:
                parent.left = p.left
            else:
                parent.right = p.left
                
        else: 
            parent = p
            left = p.left # 서브트리 안에서 가장 큰 노드
            is_left_child = True
            while left.right is not None: # 가장 큰 노드 left를 검색
                parent = left
                left = left.right
                is_left_child = False
                
            p.key = left.key # left의 키를 p로 이동
            p.value = left.value # left의 데이터를 p로 이동
            if is_left_child:
                parent.left = left.left # 포인터를 옮겨서 left를 삭제
            else:
                parent.right = left.left # 포인터를 옮겨서 left를 삭제

 

 

키의 대소 관계를 판단하여 검색하는 search() 함수 알고리즘 
1. 루트에 주목한다. (주목하는 노드를 p라고 하겠다.)
2. p가 None이면 검색을 실패하고 종료한다.
3. 검색하는 key와 주목 노드 p의 키를 비교한다.
  -  key = p : 검색을 성공하고 종료 
  -  key < p : 주목 노드를 왼쪽 자식 노드를 옮긴다.
  -  key > p : 주목 노드를 오른쪽 자식 노드로 옮김
4. 2번 과정으로 되돌아간다.

 

노드를 삽입하는 add() 함수 알고리즘
1. 루트에 주목한다. (주목하는 노드를 node라고 하겠다.)
2. 삽입하는 key와 주목 노드 node의 키를 비교한다.
  -  key = node : 삽입을 실패하고 종료.
  -  key < node : 왼쪽 자식 노드가 없으면 그 자리에 삽입 후 종료 / 있으면, 주목 노드를 왼쪽 자식 노드로 옮긴다.
  -  key > node : 오른쪽 자식 노드가 없으면 그 자리에 삽입 후 종료 / 있으면, 주목 노드를 오른쪽으로 자식 노드로 옮긴다.
3. 2번 과정으로 되돌아간다.

 

노드를 삭제하는 remove() 함수 알고리즘 

노드를 삭제할 때 다음과 같은 3가지 경우가 있다.
A. 자식 노드가 없는 노드를 삭제하는 경우
B. 자식 노드가 1개인 노드를 삭제하는 경우
C. 자식 노드가 2개인 노드를 삭제하는 경우

A : 
삭제할 노드가 부모 노드의 왼쪽(오른쪽) 자식이면 왼쪽(오른쪽) 포인터를 None으로 한다.

B : 
삭제할 노드가 부모 노드의 왼쪽(오른쪽) 자식인 경우 부모의 왼쪽(오른쪽) 포인터가 삭제할 노드의 자식을 가리키도록 업데이트한다. 

C : 
1. 삭제할 노드의 왼쪽 서브 트리에서 키값이 가장 큰 노드를 검색한다.
2. 검색한 노드를 삭제 위치로 옮긴다. 즉, 검색한 노드의 데이터를 삭제할 노드 위치에 복사한다.
3. 옮긴 노드를 삭제한다. 이때 자식 노드의 개수에 따라 다음을 수행한다.
  -  자식이 없으면 A 
  -  자식이 1개만 있으면 B  

 

 

---

균형 검색 트리

 

이진 검색 트리는 키의 오름차순으로 노드가 삽입되면 트리의 높이가 깊어지는 단점이 있다. 예를 들어 이진 검색 트리에 1, 2, 3, 4, 5순으로 노드를 삽입하면 직선 모양의 트리가 된다. (실제로 선형 리스트처럼 되어 빠른 검색을 수행할 수 없다.)

이와 같이 높이를 O(log n)으로 제한하여 고안된 검색 트리를 균형 검색 트리(self-balancing search)라고 한다.

 

다음과 같은 종류가 있다.

-  AVL 트리 

-  레드/블랙 트리

 

이진이 아닌 균형 검색 트리로는 다음과 같은 종류가 있다.

- B 트리

- 2-3 트리