1-8. [자료구조이론] 트리

Shy·2023년 8월 3일
0

자료구조 ＆ 알고리즘(Python)

목록 보기
8/24

트리(Tree)구조

트리(tree)는 계층적 관계를 표현하는 자료구조다. 용어만 들으면 복잡해 보일 수 있지만, 사실 우리 일상 생활에서도 트리 구조를 많이 접하고 있다. 가족 트리나 조직도 등이 대표적인 예이다.

트리 구조는 노드(node)들의 집합으로, 노드들은 부모-자식 관계를 갖는다. 특히 다음과 같은 특징을 가진다.

  1. 루트 노드(Root Node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  2. 단말 노드(Leaf node): 자식이 없는 노드, '리프', '잎' 등으로도 불립니다.
  3. 내부(Intermediate) 노드: 루트와 단말 노드를 제외한 나머지 노드입니다.
  4. 간선(Edge): 노드를 연결하는 선입니다. 부모 노드와 자식 노드를 연결한다.
  5. 형제(Sibling): 같은 부모를 가진 노드들이다.
  6. 노드의 차수(Degree): 하나의 노드에 연결된 자식 노드의 수다.
  7. 트리의 차수: 트리의 노드 중에서 차수가 가장 많은 값이다.
  8. 레벨(Level): 트리에서 노드의 위치를 나타냅니다. 루트 노드부터 시작하여 아래로 내려가면서 증가한다.
  9. 높이(Height): 트리의 최대 레벨이다.
  10. Depth: 트레이서 노드가 가질 수 있는 최대 Level

트리는 노드의 추가, 검색, 삭제 등의 연산을 효율적으로 수행할 수 있도록 설계되어 있다. 이진 트리, 이진 검색 트리, AVL 트리, 레드-블랙 트리, B트리 등 다양한 종류의 트리가 존재하며, 각각의 트리는 특별한 목적에 맞게 설계되어 있다.

이진 트리와 이진 탐색 트리(Binary Search Tree)

  1. 이진 트리(Binary Tree): 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조를 말한다. 이 두 개의 노드는 각각 '왼쪽 자식 노드'와 '오른쪽 자식 노드'라고 불린다. 루트 노드에서 시작해서 아래로 내려갈수록 레벨이 증가하고, 이진 트리의 높이는 최대 레벨과 같다. 이진 트리의 종류로는 완전 이진 트리, 포화 이진 트리, 균형 이진 트리 등이 있다.
  2. 이진 탐색 트리(Binary Search Tree, BST): 이진 탐색 트리는 이진 트리의 일종이지만, 좀 더 특별한 속성을 가진다. 각 노드의 키 값은 그 노드의 왼쪽 서브트리에 있는 모든 노드의 키 값들보다 크고, 오른쪽 서브트리에 있는 모든 노드의 키 값들보다 작다. 이런 속성으로 인해, 이진 탐색 트리에서는 키를 사용해 노드를 효율적으로 검색할 수 있다. 이진 탐색 트리의 연산 시간 복잡도는 O(logN)입니다. 하지만 트리가 편향된 경우(예: 오른쪽으로만 노드가 이어진 경우) 최악의 경우 선형 시간 복잡도인 O(N)이 될 수 있다. 이 문제를 해결하기 위해 균형 이진 탐색 트리(AVL Tree, Red-Black Tree 등)가 사용된다

자료 구조 이진 탐색 트리의 장점과 주요 용도

  • 주요 용도: 데이터 검색(탐색)
  • 장점: 탐색 속도를 개선할 수 있다.

이진 탐색 트리(Binary Search Tree, BST)는 자료의 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있어, 다양한 상황에서 활용된다.

장점

  1. 탐색 효율성: BST의 구조는 키를 기준으로 왼쪽 자식 노드는 키가 작고, 오른쪽 자식 노드는 키가 크다는 규칙을 가진다. 이 규칙에 따라 데이터를 저장하므로, 탐색시 O(logN)의 시간복잡도를 가진다. 따라서, BST는 큰 데이터 집합에서 특정 항목을 빠르게 찾는 데 매우 효율적이다.
  2. 동적 크기 조정: BST는 동적으로 크기를 조정할 수 있다. 즉, 노드를 삽입하거나 삭제할 때마다 새로운 메모리를 할당하거나 해제하여 트리의 크기를 조정할 수 있다. 따라서, 사용하지 않는 메모리를 최소화하고 필요에 따라 크기를 조정할 수 있다.

주요 용도

  1. 데이터베이스: BST는 데이터베이스 시스템에서 인덱싱을 구현하는 데 널리 사용된다. 이를 통해 레코드를 빠르게 찾을 수 있다.
  2. 파일 시스템: BST는 디스크 기반의 탐색 및 검색 작업을 처리하는 파일 시스템에서도 사용된다.
  3. 정렬된 리스트 생성: BST를 중위 순회(in-order traversal)하면 저장된 모든 데이터를 정렬된 상태로 얻을 수 있다.
  4. 균형 탐색 트리: BST는 AVL 트리, 레드-블랙 트리 등의 균형 탐색 트리를 만드는 기반으로도 사용된다. 이러한 트리는 최악의 경우의 성능을 개선하기 위해 사용된다.

이진트리와 정렬된 배열간의 탐색 비교

파이썬 객체지향 프로그래밍으로 링크드 리스트를 활용해서 이진 탐색 트리 구현해보기

노드 클래스 만들기

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

이 코드에서는 이진 탐색 트리를 구현하는데 필요한 노드 클래스를 정의하고 있다.

각 노드는 세 가지 속성을 가진다.

  1. value: 노드의 값으로, 이진 탐색 트리에서 노드의 위치를 결정하는데 사용된다. 노드의 값은 키로 생각할 수 있으며, 검색, 삽입, 삭제 등의 연산을 수행할 때 이 값을 기준으로 한다.
  2. left: 왼쪽 자식 노드를 가리킨다. 왼쪽 자식 노드의 값은 부모 노드의 값보다 작아야 한다.
  3. right: 오른쪽 자식 노드를 가리킨다. 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야 한다.

노드의 init 메서드는 노드를 초기화합니다. 새 노드는 값이 주어지고, 처음에는 양쪽 자식 노드가 없다 (left와 right는 None). 이것이 이진 탐색 트리를 구성하는 기본 블록이다. 이제 이 노드들을 사용하여 이진 탐색 트리를 구성할 수 있다.

이진 탐색 트레이 데이터 넣기

class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)

이 코드는 이진 탐색 트리(Binary Search Tree, BST)를 관리하는 NodeMgmt 클래스를 정의하고 있습니다. NodeMgmt 클래스는 이진 탐색 트리에 노드를 삽입하는 기능을 제공한다.

NodeMgmt 클래스의 init 메서드는 트리의 루트 노드(head)를 초기화한다.

insert 메서드는 트리에 새 노드를 삽입한다. 삽입하려는 값이 현재 노드의 값보다 작으면 현재 노드를 왼쪽 자식 노드로 이동하고, 그렇지 않으면 오른쪽 자식 노드로 이동한다. 이 작업을 삽입하려는 위치를 찾을 때까지 반복한다.

삽입하려는 위치를 찾으면, 새 노드를 생성하고 현재 노드의 적절한 자식 노드로 설정한다. 만약 삽입하려는 값이 현재 노드의 값보다 작다면 왼쪽 자식 노드로, 크다면 오른쪽 자식 노드로 설정한다.

이 코드는 새로운 NodeMgmt 객체를 생성하고, insert 메서드를 사용하여 이진 탐색 트리에 새 노드를 삽입하는 방법을 보여준다. 이 과정에서 먼저 노드를 하나 생성하여 이를 헤드(루트 노드)로 설정하고, 그 후 insert 메서드를 통해 새로운 값을 가진 노드를 이진 탐색 트리에 추가하고 있다.

이진 탐색 트리 탐색

class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)

BST.search(-1)

이 코드는 이진 탐색 트리에서 특정 값을 가진 노드를 찾는 search 메서드를 추가한 NodeMgmt 클래스를 정의하고 있다.

search 메서드는 이진 탐색 트리에서 주어진 값을 가진 노드를 찾는다. 메서드는 루트 노드에서 시작하여, 찾고자 하는 값과 현재 노드의 값을 비교한다. 만약 찾고자 하는 값이 현재 노드의 값과 같다면, True를 반환한다.

찾고자 하는 값이 현재 노드의 값보다 작으면, 현재 노드를 왼쪽 자식 노드로 이동시키고, 그렇지 않으면 오른쪽 자식 노드로 이동시킨다. 이 과정을 트리를 통해 찾고자 하는 값이 나올 때까지 반복한다. 만약 트리의 모든 노드를 검사한 후에도 찾고자 하는 값이 없다면, False를 반환한다.

이 코드는 새로운 NodeMgmt 객체를 생성하고, 여러 개의 값을 가진 노드를 이진 탐색 트리에 삽입한 후, search 메서드를 사용하여 특정 값을 가진 노드를 이진 탐색 트리에서 찾는 방법을 보여준다. BST.search(-1)은 이진 탐색 트리에서 값 -1을 가진 노드를 찾는 것을 시도하고, 해당 값이 트리 내에 없으므로 False를 반환한다.

이진 탐색 트리 삭제

매우 복잡함으로, 경우를 나누어서 이해하는 것이 좋다.
이진 탐색 트리에서 노드를 삭제할 때, 그 노드가 어떤 자식 노드를 가지고 있는지에 따라서 처리 방식이 달라진다.

Leaf Node 삭제

Leaf Node는 Chuld Node가 없는 Node이다.
삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 해야 한다.

Child Node가 하나인 Node 삭제

삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.

Child Node가 두개인 Node 삭제

  1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우

  • 삭제할 Node의 오른쪽 자식 선택
  • 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
  • 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
  • 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
  • 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
  • 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

이진 탐색 트리 삭제 코드 구현과 분석

삭제할 Node 탐색

삭제할 Node가 없는 경우도 처리해야 한다. 이를 위해선, 삭제할 Node가 없는 경우는 False를 리턴하고 함수를 종료시킨다.

# def delete(self, value):
    searched = False
    self.current_node = self.head
    self.parent = self.head
    while self.current_node:
        if self.current_node.value == value:
            searched = True
            break
        elif value < self.current_node.value:
            self.parent = self.current_node
            self.current_node = self.current_node.left
        else:
            self.parent = self.current_node
            self.current_node = self.current_node.right
    
    if searched == False:
        return False
    
    ### 이후부터 Case들을 분리해서, 코드 작성

이 코드는 이진 탐색 트리에서 주어진 값을 가진 노드를 찾아 삭제하는 과정의 일부다. 먼저 삭제하려는 노드를 찾는 과정이다.

삭제하려는 노드의 값을 value라는 매개변수로 받아서 삭제하려는 노드가 있는지 탐색한다. 이를 위해 루트 노드에서 시작하여 각 노드의 값을 비교한다. 만약 찾으려는 노드의 값이 현재 노드의 값과 같으면 searched를 True로 변경하고 루프를 종료한다.

만약 찾으려는 값이 현재 노드의 값보다 작다면, 현재 노드의 부모 노드를 갱신하고 현재 노드를 왼쪽 자식 노드로 이동한다. 반대로 찾으려는 값이 현재 노드의 값보다 크다면, 현재 노드의 부모 노드를 갱신하고 현재 노드를 오른쪽 자식 노드로 이동한다. 이 과정을 찾으려는 값을 가진 노드를 찾을 때까지 반복한다.

만약 찾으려는 값을 가진 노드가 없다면 searched가 False인 상태로 루프가 종료되므로, 함수는 False를 반환하고 종료한다. 이후의 삭제 과정은 ### 이후부터 Case들을 분리해서, 코드 작성 부분에 작성하면 된다.

이 코드는 이진 탐색 트리에서 삭제하려는 노드가 있는지 확인하는 과정을 담당한다. 노드가 있으면 노드와 그 노드의 부모 노드에 대한 정보를 기록하여 삭제 작업을 계속 진행할 수 있다.

Case1. 삭제할 Node가 Leaf Node인 경우

# self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
    if  self.current_node.left == None and self.current_node.right == None:
        if value < self.parent.value:
            self.parent.left = None
        else:
            self.parent.right = None
        del self.current_node

이 코드는 삭제하려는 노드가 리프 노드(Leaf Node, 자식 노드가 없는 노드)인 경우를 처리한다. 리프 노드는 자식 노드가 없기 때문에 간단하게 삭제할 수 있다.

삭제하려는 노드인 self.current_node의 왼쪽과 오른쪽 자식 노드가 모두 None인 경우에 이 코드가 실행된다. self.current_node는 삭제하려는 노드이고, self.parent는 삭제하려는 노드의 부모 노드를 참조하고 있다.

삭제하려는 노드의 값이 부모 노드의 값보다 작다면, 삭제하려는 노드는 부모 노드의 왼쪽 자식 노드임을 의미한다. 이 경우 self.parent.left를 None으로 설정하여 부모 노드와의 연결을 끊는다.

반대로 삭제하려는 노드의 값이 부모 노드의 값보다 크다면, 삭제하려는 노드는 부모 노드의 오른쪽 자식 노드임을 의미합니다. 이 경우 self.parent.right를 None으로 설정하여 부모 노드와의 연결을 끊는다.

마지막으로 del self.current_node를 통해 삭제하려는 노드를 메모리에서 제거한다. 이렇게 해서 리프 노드의 삭제 과정이 완료된다.

Case2. 삭제할 Node가 Child Node를 한 개 가지고 있을 경우

    if self.current_node.left != None and self.current_node.right == None:
        if value < self.parent.value:
            self.parent.left = self.current_node.left
        else:
            self.parent.right = self.current_node.left
    elif self.current_node.left == None and self.current_node.right != None:
        if value < self.parent.value:
            self.parent.left = self.current_node.right
        else:
            self.parent.right = self.current_node.right

이 코드는 삭제하려는 노드가 하나의 자식 노드만 가지고 있는 경우를 처리한다. 두 가지 하위 케이스로 나뉘는데, 삭제하려는 노드가 왼쪽 자식 노드만 가지고 있을 때와 오른쪽 자식 노드만 가지고 있을 때이다.

첫 번째 if 문은 삭제하려는 노드가 왼쪽 자식 노드만 가지고 있는 경우를 다룬다. self.current_node.left는 존재하고 self.current_node.right는 존재하지 않는다. 이 경우, 삭제하려는 노드의 부모 노드를 삭제하려는 노드의 자식 노드와 연결해준다. 삭제하려는 노드가 부모 노드의 왼쪽에 있을 경우(value < self.parent.value)는 self.parent.left를 삭제하려는 노드의 왼쪽 자식 노드와 연결해주고, 반대로 삭제하려는 노드가 부모 노드의 오른쪽에 있을 경우는 self.parent.right를 삭제하려는 노드의 왼쪽 자식 노드와 연결해준다.

두 번째 elif 문은 삭제하려는 노드가 오른쪽 자식 노드만 가지고 있는 경우를 다룬다. self.current_node.left는 존재하지 않고 self.current_node.right는 존재한다. 이 경우도 마찬가지로, 삭제하려는 노드의 부모 노드를 삭제하려는 노드의 자식 노드와 연결해준다. 삭제하려는 노드가 부모 노드의 왼쪽에 있을 경우는 self.parent.left를 삭제하려는 노드의 오른쪽 자식 노드와 연결해주고, 반대로 삭제하려는 노드가 부모 노드의 오른쪽에 있을 경우는 self.parent.right를 삭제하려는 노드의 오른쪽 자식 노드와 연결해준다.

Case3-1. 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)

  • 기본 사용 가능 전략
    1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
    2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  • 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
    • 경우의 수가 또다시 두가지가 있음
      • Case3-1-1: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
      • Case3-1-2: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
        • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

    if self.current_node.left != None and self.current_node.right != None: # case3
        if value < self.parent.value: # case3-1
            self.change_node = self.current_node.right
            self.change_node_parent = self.current_node.right
            while self.change_node.left != None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            if self.change_node.right != None:
                self.change_node_parent.left = self.change_node.right
            else:
                self.change_node_parent.left = None
            self.parent.left = self.change_node
            self.change_node.right = self.current_node.right
            self.change_node.left = self.change_node.left

이 코드는 삭제하려는 노드가 두 개의 자식 노드를 모두 가지고 있고, 삭제하려는 노드가 부모 노드의 왼쪽에 위치한 경우를 처리한다.

삭제하려는 노드가 두 개의 자식 노드를 모두 가지고 있다면, 가장 까다로운 상황이다. 이럴 경우에는 삭제하려는 노드의 오른쪽 자식 중 가장 작은 값을 삭제하려는 노드의 부모 노드가 가리키도록 하는 전략을 사용한다.

이를 위해서 self.change_node라는 변수를 설정하여 삭제하려는 노드의 오른쪽 자식을 가리키게 한다. 이 노드는 우리가 교체하려는 노드다. 그리고 이 노드의 부모 노드를 self.change_node_parent에 저장한다.

그 다음 while 문을 통해 self.change_node의 왼쪽 자식 노드를 탐색한다. 왜냐하면 노드의 왼쪽 자식 노드가 노드의 오른쪽 자식 노드보다 항상 작기 때문이다. 따라서 왼쪽 자식 노드가 없을 때까지 self.change_node와 self.change_node_parent를 계속해서 왼쪽으로 이동시킨다.

이제 가장 작은 값을 가진 노드를 찾았으니, 이 노드를 삭제하려는 노드와 교체해야 한다. 하지만 이 노드가 오른쪽 자식 노드를 가지고 있을 수도 있으므로 이 경우를 처리해야 한다. 이 노드가 오른쪽 자식 노드를 가지고 있다면 self.change_node_parent의 왼쪽 자식 노드를 self.change_node의 오른쪽 자식 노드로 바꾸고, self.change_node가 오른쪽 자식 노드를 가지고 있지 않다면 self.change_node_parent의 왼쪽 자식 노드를 None으로 설정하여 노드를 삭제한다.

마지막으로 self.parent의 왼쪽 자식 노드를 self.change_node로 바꾸고, self.change_node의 오른쪽과 왼쪽 자식 노드를 각각 삭제하려는 노드의 오른쪽과 왼쪽 자식 노드로 설정하여 노드를 교체한다.

Case3-2. 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)

  • 기본 사용 가능 전략
    1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
    2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
  • 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
    • 경우의 수가 또다시 두가지가 있음
      • Case3-2-1: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
      • Case3-2-2: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
        • 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임

        else:
            self.change_node = self.current_node.right
            self.change_node_parent = self.current_node.right
            while self.change_node.left != None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            if self.change_node.right != None:
                self.change_node_parent.left = self.change_node.right
            else:
                self.change_node_parent.left = None
            self.parent.right = self.change_node
            self.change_node.left = self.current_node.left
            self.change_node.right = self.current_node.right

이 코드는 삭제하려는 노드가 두 개의 자식 노드를 모두 가지고 있고, 삭제하려는 노드가 부모 노드의 오른쪽에 위치한 경우를 처리한다.

이전의 경우와 비슷하게 이 경우에도 삭제하려는 노드의 오른쪽 자식 중 가장 작은 값을 삭제하려는 노드의 위치로 이동시키는 전략을 사용한다.

self.change_node를 설정하여 삭제하려는 노드의 오른쪽 자식을 가리키게 하고, 이 노드의 부모 노드를 self.change_node_parent에 저장한다.

while 문을 통해 self.change_node의 왼쪽 자식 노드를 탐색한다. 왼쪽 자식 노드가 없을 때까지 self.change_node와 self.change_node_parent를 계속해서 왼쪽으로 이동시키면, 가장 작은 값을 가진 노드를 찾을 수 있다.

이 노드를 삭제하려는 노드와 교체하려면, 이 노드가 오른쪽 자식 노드를 가지고 있는지를 확인해야 한다. 만약 오른쪽 자식 노드를 가지고 있다면, self.change_node_parent의 왼쪽 자식 노드를 self.change_node의 오른쪽 자식 노드로 설정합니다. 만약 오른쪽 자식 노드를 가지고 있지 않다면, self.change_node_parent의 왼쪽 자식 노드를 None으로 설정하여 노드를 삭제한다.

마지막으로 self.parent의 오른쪽 자식 노드를 self.change_node로 설정하고, self.change_node의 왼쪽과 오른쪽 자식 노드를 각각 삭제하려는 노드의 왼쪽과 오른쪽 자식 노드로 설정한다. 이렇게 하면, 삭제하려는 노드와 self.change_node가 교체된다.

파이썬 전체 코드 구현

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

        
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        
    
    def delete(self, value):
        # 삭제할 노드 탐색
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        if searched == False:
            return False    

        # case1
        if  self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        
        # case2
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right        
        
        # case 3
        elif self.current_node.left != None and self.current_node.right != None:
            # case3-1
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left
            # case 3-2
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

        return True

파이썬 전체 코드 테스트

  • random 라이브러리 활용
    • random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴
      • 예: random.randint(0, 99): 0에서 99까지 숫자중 특정 숫자를 랜덤하게 선택해서 리턴해줌
# 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
import random

# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))
# print (bst_nums)

# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
    binary_tree.insert(num)
    
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
    if binary_tree.search(num) == False:
        print ('search failed', num)

# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0, 99)])

# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
    if binary_tree.delete(del_num) == False:
        print('delete failed', del_num)

이진 탐색 트리의 시간 복잡도와 단점

시간 복잡도 (탐색시)

  • depth (트리의 높이) 를 h라고 표기한다면, O(h)
  • n개의 노드를 가진다면, h=log2nh = log_2{n} 에 가까우므로, 시간 복잡도는 O(logn)O(log{n})
    • 참고: 빅오 표기법에서 lognlog{n} 에서의 log의 밑은 10이 아니라, 2입니다.
      • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

이진 탐색 트리 단점

  • 평균 시간 복잡도는 O(logn)O(log{n}) 이지만,
    • 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
  • 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( O(n)O(n) )

profile
Shy
스벨트 자바스크립트 익히는중...
이전 포스트

1-7. [자료구조이론] 해쉬 테이블

다음 포스트

1-9. [자료구조이론] 힙

0개의 댓글