[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 14회차 미션

5.5.5 파이썬 전체 코드 구현

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

5.5.6 파이썬 전체 코드 테스트

   random 라이브러리 활용

   # 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)

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

   6.1 시간 복잡도 ( 탐색 시 )

       depth (트리의 높이) 를 h라고 표기한다면 O(h)

           n개의 노드를 가진다면 h = log2n 에 가까우므로 시간복잡도는 O(logn)

     

 

  6.2 이진 탐색 트리 단점

   평균 시간 복잡도는 O(logn) 이지만 이는 트리가 균형잡혀 있을 때 평균시간복잡도

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG