코딩고치

[파이썬][자료구조] 트리 (Tree) 본문

파이썬/자료구조

[파이썬][자료구조] 트리 (Tree)

코딩고치 2020. 4. 23. 23:53

트리 (Tree) 구조

  • 트리는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조이다.
  • 이진트리 (Binary Tree) 형태로 탐색 알고리즘에서 많이 사용된다.

용어

  • Node: 데이터를 저장하는 기본 요소 (branch 요소 포함)
  • Root Node: 맨 위에 있는 노드
  • Level: 노드의 깊이
  • Parent Node: 어떤 노드의 상위 노드
  • Child Node: 어떤 노드의 하위 노드
  • Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
  • Sibling (Brother Node): 동일한 Parent Node를 가진 노드
  • Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진트리와 이진 탐색 트리

  • 이진트리는 노드의 최대 branch가 2인 트리 구조이다.
  • 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 추가적인 조건이 있다.
    • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 갖는다.

https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

 

이진 탐색 트리의 장점

  • 탐색 속도가 빠르다.

링크드 리스트를 이용한 트리

노드 클래스 만들기

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

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

class NodeMgmt:
    def __init__(self, head):
        self.head = head

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

이진 탐색 트리 탐색

class NodeMgmt:
    def __init__(self, head):
        self.head = head

    def insert(self, data):
        self.current = self.head
        while True:
            if data < self.current.data:
                if self.current.left != None:
                    self.current = self.current.left
                else:
                    self.current.left = Node(data)
                    break
            else:
                if self.current.right != None:
                    self.current = self.current.right
                else:
                    self.current.right = Node(data)
                    break

    def search(self, data):
        self.current = self.head
        while self.current:
            if self.current.data == data:
                return True
            elif data < self.current.data:
                self.current = self.current.left
            else:
                self.current = self.current.right
        return False
head = Node(4)
BST = NodeMgmt(head)
BST.insert(8)
BST.insert(2)
BST.insert(3)
BST.insert(12)
BST.insert(29)
BST.search(8)
True
BST.search(0)
False

이진 탐색 트리 삭제

  • 각각의 경우를 따져서 생각해야 한다.

1. Leaf Node 삭제

  • Parent Node가 삭제할 Node를 가리키지 않도록 한다.

2. Child Node가 하나인 Node 삭제

3. Child Node가 두 개인 Node 삭제

아래 둘 중 하나로 코드를 작성한다.

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

1번의 경우

  1. 삭제할 Node의 오른쪽 자식 선택한다.
  2. 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택한다.
  3. 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 한다.
  4. 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 한다.
  5. 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 한다.
  6. 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 한다.

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

def delete(self, data):
    searched = False
    self.current = self.head #삭제할 Node 지칭하게끔
    self.parent = self.head # 삭제할 Node의 parent를 지칭하게끔
    while self.current:
        if self.current.data == data:
            searched = True
            break
        elif data < self.current.data:
            self.parent = self.current
            self.current = self.current.left
        else:
            self.parent = self.current
            self.current = self.current.right

    if searched == False:
        return False

    # 삭제할 Node가 Leaf Node 일 때
    if self.current.left == None and self.current.right == None:
        if data < self.parent.data:
            self.parent.left = None
        else:
            self.parent.right = None

    #삭제할 Node가 Child Node 한 개 가지고 있을 경우
    #삭제할 node의 child가 왼쪽에 있을 때
    if self.current.left != None and self.current.right == None:
        #current가 parent의 왼쪽인지 오른쪽인지
        if data < self.parent.data:
            self.parent.left = self.current.left
        else:
            self.parent.right = self.current.left
    #삭제할 node의 child가 오른쪽에 있을 때
    elif self.current.left == None and self.current.right != None:
        #current가 parent의 왼쪽인지 오른쪽인지
        if data < self.parent.data:
            self.parent.left = self.current.right
        else:
            self.parent.right = self.current.right

    #삭제할 Node의 child가 2개인 경우
    if self.current.left != None and self.current.right != None:
        #삭제할 Node가 parent의 왼쪽에 있을 때
        if data < self.parent.data:
            self.change = self.current.right
            self.change_parent = self.current.right
            while self.change.left != None: # 삭제할 node의 오른쪽 child의 가장 왼쪽 숫자 찾기
                self.change_parent = self.change
                self.change = self.change.left
            if self.change.right != None: # change_node의 right가 있을 경우
                self.change_parent.left = self.change.right
            else: #right가 없을 경우   
                self.change_parent.left = None # parent와의 고리 끊기
            self.parent.left = self.change # current 자리에 change node 넣기
            self.change.right = self.current.right #change node와 current node 의 right. left와 연결
            self.change.left = self.current.left
        else: # 삭제할 Node가 parent의 오른쪽에 있을 때
            self.change = self.current.right
            self.change_parent = self.current.right
            while self.change.left != None:
                self.change_parent = self.change
                self.change = self.change.left
            if self.change.right != None:
                self.change_parent.left = self.change.right
            else:
                self.change_parent.left = None
            self.parent.right = self.change
            self.change.left = self.current.left
            self.change.right = self.current.right

    return True

이진 탐색 트리 전체 코드

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

class NodeMgmt:
    def __init__(self, head):
        self.head = head

    def insert(self, data):
        self.current = self.head
        while True:
            if data < self.current.data:
                if self.current.left != None:
                    self.current = self.current.left
                else:
                    self.current.left = Node(data)
                    break
            else:
                if self.current.right != None:
                    self.current = self.current.right
                else:
                    self.current.right = Node(data)
                    break

    def search(self, data):
        self.current = self.head
        while self.current:
            if self.current.data == data:
                return True
            elif data < self.current.data:
                self.current = self.current.left
            else:
                self.current = self.current.right
        return False

    def delete(self, data):
        searched = False
        self.current = self.head #삭제할 Node 지칭하게끔
        self.parent = self.head # 삭제할 Node의 parent를 지칭하게끔
        while self.current:
            if self.current.data == data:
                searched = True
                break
            elif data < self.current.data:
                self.parent = self.current
                self.current = self.current.left
            else:
                self.parent = self.current
                self.current = self.current.right

        if searched == False:
            return False

        # 삭제할 Node가 Leaf Node 일 때
        if self.current.left == None and self.current.right == None:
            if data < self.parent.data:
                self.parent.left = None
            else:
                self.parent.right = None

        #삭제할 Node가 Child Node 한 개 가지고 있을 경우
        #삭제할 node의 child가 왼쪽에 있을 때
        if self.current.left != None and self.current.right == None:
            #current가 parent의 왼쪽인지 오른쪽인지
            if data < self.parent.data:
                self.parent.left = self.current.left
            else:
                self.parent.right = self.current.left
        #삭제할 node의 child가 오른쪽에 있을 때
        elif self.current.left == None and self.current.right != None:
            #current가 parent의 왼쪽인지 오른쪽인지
            if data < self.parent.data:
                self.parent.left = self.current.right
            else:
                self.parent.right = self.current.right

        #삭제할 Node의 child가 2개인 경우
        if self.current.left != None and self.current.right != None:
            #삭제할 Node가 parent의 왼쪽에 있을 때
            if data < self.parent.data:
                self.change = self.current.right
                self.change_parent = self.current.right
                while self.change.left != None: # 삭제할 node의 오른쪽 child의 가장 왼쪽 숫자 찾기
                    self.change_parent = self.change
                    self.change = self.change.left
                if self.change.right != None: # change_node의 right가 있을 경우
                    self.change_parent.left = self.change.right
                else: #right가 없을 경우   
                    self.change_parent.left = None # parent와의 고리 끊기
                self.parent.left = self.change # current 자리에 change node 넣기
                self.change.right = self.current.right #change node와 current node 의 right. left와 연결
                self.change.left = self.current.left
            else: # 삭제할 Node가 parent의 오른쪽에 있을 때
                self.change = self.current.right
                self.change_parent = self.current.right
                while self.change.left != None:
                    self.change_parent = self.change
                    self.change = self.change.left
                if self.change.right != None:
                    self.change_parent.left = self.change.right
                else:
                    self.change_parent.left = None
                self.parent.right = self.change
                self.change.left = self.current.left
                self.change.right = self.current.right

        return True

코드 테스트

import random

#1 ~ 10000 중, 100 개의 숫자 랜덤 선택
nums = set() # 집합은 중복 데이터 입력 x
while len(nums) != 100:
    nums.add(random.randint(0, 10000))
#print(nums)

# 이진 탐색 트리에 입력, rootnode는 임의로 설정
head = Node(5000)
bst = NodeMgmt(head)
for num in nums:
    bst.insert(num)

# 검색
for num in nums:
    if bst.search(num) == False: 
        print('search failed', num) # 출력 되면 tree 잘못 짠 것

# 10개의 숫자 랜덤 선택
delete_nums = set()
nums = list(nums)
while len(delete_nums) != 10:
    delete_nums.add(nums[random.randint(0, 99)])

# 10개의 숫자 삭제
for del_num in delete_nums:
    if bst.delete(del_num) == False:
        print('delete failed', del_num) # 출력 되면 tree 잘못 짠 것

시간 복잡도

  • 시간 복잡도는 depth와 관련되어 있다.
    • depth가 h라면 시간 복잡도는 O(h)이다
  • node가 n 개라면 $h=log_2 {n}$이므로 시간 복잡도는 $O(log {n})$이다
    • $h=log_2 {n}$은 한번 실행할 때마다 계산할 데이터가 절반씩 제거된다.

이진 탐색 트리 단점

  • 트리가 한쪽으로만 전부 입력이 된 경우 링크드 리스트와 동일한 시간 복잡도를 (O(n)) 갖는다.

저작자표시

'파이썬 > 자료구조' 카테고리의 다른 글

[파이썬][자료구조] 힙 (Heap)  (0) 2020.04.25
[파이썬][자료구조] 해쉬 테이블(Hash Table)  (1) 2020.04.22
[파이썬][자료구조] 시간 복잡도  (0) 2020.04.16
[파이썬][자료구조] 링크드 리스트 (Linked List)  (0) 2020.04.15
[파이썬][자료구조] 스택 (Stack)  (0) 2020.04.15
'파이썬/자료구조' Related Articles more
Comments