자료구조 : 트리(tree), 이진탐색트리 파이썬으로 구현하기

트리 구조

- 루트 노드(A)를 시작으로 줄기를 뻗어 나가듯 원소를 추가해 나가는 비선형 구조

- 계층 구조로 방향이 있다.

 

 

 

루트노드 : 가장 꼭대기의 노드

트리는 루트노드가 1개이다.

 

 

자식 노드 : 노드의 바로 하위에 인접한 노드 (간선으로 연결된)

부모 노드 : 노드의 바로 상위에 인접한 노드

모든 자식의 부모는 단 하나이다.

 

 

자손 노드 : 노드로부터 단말노드까지 하위로 이어지는 모든 노드의 집합

조상 노드 : 노드로부터 루트 노드까지 상위로 이어지는 모든 노드의 집합

 

 

단말노드(leaf node, 잎사귀 노드) : 자식이 없는 노드 (I, J, K, L, G, M, N)

 

 

서브 트리 : 자식과의 간선을 끊었을 때 생길 하위트리 

자식노드의 개수와 서브트리의 개수는 동일하다.

 

 

차수(degree) : 노드의 하위 간선의 개수 ( 자식의 개수, 서브트리의 개수)

트리 전체의 차수는 노드 중 최대 차수로 표현한다.

 

 

깊이, 레벨(depth, level) : 루트에서 어떤 노드까지의 경로 길이

루트노드를 레벨 0으로 하고 아래로 하나씩 늘어난다. 루트노드를 레벨 1로 보기도 한다.

 

 

높이 (height) :트리의 깊이 중 제일 큰 깊이

 

 

 

이진탐색트리(BST : Binary Search Tree)

트리의 차수가 2인 트리, 모든 노드의 자식이 최대 2개인 트리

 

- 완전 이진 트리 : 끝부분 (마지막레벨)을 제외하고 모든 노드가 채워진 이진트리

- 포화 이진 트리 : 모든 단말 노드의 깊이가 같은 완전이진트리

- 균형 이진 트리 : 좌우의 높이차가 같거나 최대 1인 트리

 

 

 

1. 이진탐색트리의 삽입

- 루트부터 삽입을 시작

- 부모 노드보다 작을 경우 왼쪽, 클 경우 오른쪽에 추가

- 중복된 원소는 삽입하지 않음

 

 

단순구현방법으로 이진탐색트리를 구현해본다.

from mimetypes import init

class Node: #노드 생성
    def __init__(self,value): 
        self.value=value
        self.right = None
        self.left = None

class Tree: #이진탐색트리 노드삽입
    def __init__(self,root):
        self.root=root #루트노드
    def insert(self,value):
        self.current_node = self.root #현재노드
        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

값이 현재노드의 값보다 작으면 왼쪽자식을 확인한다.

왼쪽자식의 값이 있으면 왼쪽자식을 현재노드로 하여, 반복문을 다시 돌린다.

왼쪽자식의 값이 없으면 그 값을 왼쪽자식에 넣는다.

 

값이 현재노드보다 크면 오른쪽자식을 확인한다.

오른쪽자식의 값이 있으면 오른쪽자식을 현재노드로 하여, 반복문을 돌린다.

오른쪽자식의 값이 없으면 그 값을 오른쪽 자식에 넣는다.

 

 

2. 이진탐색트리 조회

    def search(self,value): #노드에 입력한 값이 있으면 True, 없으면 False
        self.current_node=self.root
        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

해당 트리구조에 입력한 값이 존재하면 True, 존재하지 않으면 False를 출력하도록 하는 메서드이다.

찾는 값이 현재노드의 값보다 작으면 현재노드의 왼쪽자식을 현재노드로 변경하여 반복문을 돌리고,

찾는 값이 현재노드의 값보다 크면 현재노드의 오른쪽 자식을 현재노드로 변경하여 반복문을 돌린다.

 

 

 

3. 이진탐색트리 삭제

    def delete(self,value):
        self.current_node = self.root
        self.parent = self.root
        if self.search(self,value) == False:
            return False
        #1. 삭제할 노드가 leaf 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
        #2. 삭제할 노드가 왼쪽자식노드만 가지고 있음
        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
    
        #3. 오른쪽자식노드만 가지고 있음
        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   

        #4. 자식 노드를 두 개 가지고 있을 때
        if self.current_node.left != None and self.current_node.right != None:
            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
                
            if value < self.parent.value:
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            else:
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
        return True

 

노드 제거 함수는 위와 같이 작성할 수 있다.

 

 

root = Node(3)
bst = BST(root)
bst.insert(1)
bst.insert(3)
bst.insert(7)

print(bst.search(1)) # True
print(bst.search(7)) # True
print(bst.search(4)) # False
print(bst.delete(0)) # False
print(bst.delete(7)) # True
print(bst.search(7)) # False

이진탐색트리가 잘 구현된 것을 확인하였다.

 

 

 

4. 재귀로 이진탐색트리 생성, 조회, 삭제 구현

# 노드 생성과 삽입
class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data
        
class BinarySearchTree(Node):
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None

    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node
 

# 노드 탐색
    def find(self, key):
        return self._find_value(self.root, key)

    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)
 
    def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted

    def _delete_value(self, node, key):
        if node is None:
            return node, False

        deleted = False
        # 해당 노드가 삭제할 노드일 경우
        if key == node.data:
            deleted = True
            # 삭제할 노드가 자식이 두개일 경우
            if node.left and node.right:
                # 오른쪽 서브 트리에서 가장 왼쪽에 있는 노드를 찾고 교체
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            # 자식 노드가 하나일 경우 해당 노드와 교체
            elif node.left or node.right:
                node = node.left or node.right
            # 자식 노드가 없을 경우 그냥 삭제
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted