Published 2021. 7. 20. 15:34

트리

🕶 Algorithm/자료구조

트리 (Tree) 구조

트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

실제로 어디에 많이 사용되나?

트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

알아둘 용어

Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
Root Node : 트리 맨 위에 있는 노드
Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
Child Node : 어떤 노드의 상위 레벨에 연결된 노드
Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
Depth : 트리에서 Node가 가질 수 있는 최대 Level

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

이진 트리 : 노드의 최대 Branch가 2인 트리
이진 탐색 트리 (Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
- 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!

이진 탐색 트리의 장점과 주요 용도

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

단점은 이진 탐색 트리 알고리즘 이해 후에 살펴보기로 함

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

파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

노드 클래스 만들기

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

이진 탐색 트리에 데이터 넣기

이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함

class NodeMgnt:
    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 != None: # 만약 왼쪽에 가지가 존재한다면 
                    self.current_node = self.current_node.left # 현재 노드를 비교할 대상노드와 바꾼다. 다시 while문
                else: # 만약 왼쪽에 가지가 없다면
                    self.current_node.left = Node(value) # 현재 노드에 새로운 노드를 만들어서 연결시킨다.
                    break
            
            else: # 새로 들어온 데이터가 원래 있던 노드보다 크거나 같다면? 오른쪽으로 가야한다.
                if self.current_node != None: # 만약 오른쪽 가지가 존재한다면
                    self.current_node == self.current_node.right # 현재 노드를 오른쪽 노드로 바꾼다. 다시 순회
                else : # 만약 오른쪽에 가지가 없다면
                    self.current_node.right = Node(value)
                    break

head = Node(1) # 루트 노드는 그냥 강제로 만들고
BST = NodeMgmt(head) # 루트 노드를 넣어줌으로써 BST 구조 객체를 하나 만들어준다.
BST.insert(2)

이진 탐색 트리 탐색

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 # 해당 노드가 없다면 False

head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)

BST.search(8)
True

BST.search(7)
False

이진 탐색 트리 삭제

매우 복잡함. 경우를 나누어서 이해하는 것이 좋음

Leaf Node 삭제

Leaf Node : Child Node 가 없는 Node
삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

1. Leaf Node 삭제

2. Leaf Node와 연결된 Branch 삭제

Child Node 가 하나인 Node 삭제

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

1. 노드를 삭제

2. 삭제한 노드의 Parent Node가 삭제한 노드의 Child Node를 가리키게 해준다.

Child Node 가 두 개인 Node 삭제

삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
삭제할 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 # 찾았다면 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
    # while문이 끝나면 노드를 찾은 것이고 current_node는 삭제할 노드가 된다.
    # parent 에는 삭제할 노드의 부모 노드가 들어가 있을 것이다.
    
    if searched == False: # 삭제할 노드를 찾지 못했다면
        return False
        
    # 이후부터는 케이스를 분류해서 작성한다.

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 # 삭제할 노드의 부모 노드의 왼쪽을 None으로

        else: # 삭제할 노드가 오른쪽 자식 노드일 떄
            self.parent.right = None # 삭제할 노드의 부모 노드의 오른쪽을 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.right != None and self.current_node.left == None:
        
        # 삭제할 노드가 부모 노드의 왼쪽 자식 노드일 때
        if value < self.parent.value:
            self.parent.left = self.current_node.right # 삭제할 노드의 왼쪽 자식노드에 연결해준다.
            
        # 삭제할 노드가 부모 노드의 오른쪽 자식 노드일 때
        else:
            self.parent.right = self.current_node.right # 삭제할 노드의 오른쪽 자식노드에 연결해준다.

그림을 그려서 작성해야 안 헷갈린다. 왼쪽 오른쪽

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

기본 사용 가능 전략

삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
삭제할 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: # case 3
        if value < self.parent.value: # case 3-1
            self.changenode

'🕶 Algorithm > 자료구조' 카테고리의 다른 글

그래프 (0)	2021.08.08
공간복잡도 (0)	2021.07.22
해쉬 테이블 (0)	2021.07.19
시간복잡도 (0)	2021.07.16
연결 리스트 (Linked List) (0)	2021.07.16

트리