[Python] 자료구조 트리 (이진 탐색 트리)

트리 구조

• 트리 : Node 와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 주로 이진 트리 형태의 구조로 탐색 알고리즘 구현에서 많이 사용 된다.

트리 용어

• Node : 데이터를 저장하는 요소
• Root Node : 최상위 노드 (레벨 0)
• Level : 노드의 깊이
• Sibling (Brother Node) : 동일한 부모를 가진 노드
• Depth : 트리에서 Node를 가질 수 있는 최대 레벨

이진트리와 이진 탐색 트리

• 이진 트리 (Binary Tree) : 최대 브랜치가 2인 트리
• 이진 탐색 트리 : BST (이진 트리에 추가적인 조건이 있는 트리)
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값
  • 장점 : 탐색 속도 개선
  • 단점 : 복잡하다.

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  

BST 실행 코드 결과

이진 탐색트리 삭제

• 복잡하기 떄문에 경우를 나누어서 이해하자.

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들을 분리해서, 코드 작성 

Leaf 노드 삭제

• 자식이 없으므로 단순 삭제 , 부모 노드의 브런취를 없앤다.

# 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

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

Child node 두개인 노드 삭제

• 삭제할 노드의 오른쪽 자식 중 , 가장 작은 값을 부모노드가 가르키도록 한다.
  • 오른쪽 자식의 가장 왼쪽에 있는 Node 선택
  • 해당 노드를 삭제할 노드의 부모 노드의 왼쪽 브랜치를 가르키게 함
  • 해당 노드의 왼쪽 브랜치가 삭제할 노드의 왼쪽 자식 노드를 가리키게 함
  • 해당 노드의 오른쪽 브랜치가 삭제할 노드의 오른쪽 자식 노드를 가리키게 함
  • 만약, 해당 노드가 오른쪽 자식을 갖고 있을 경우엔, 해당 노드의 부모의 왼쪽 브랜치가 오른쪽 자식 노드를 가리키게 함
• 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 부모노드가 가르키도록 한다.