6. 트리

# **1. 트리**
* Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조
* 트리 중 이진 트리(binary tree)형태의 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

# **2. 알아둘 용어**
* Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보를 포함)
* Root Node: 트리 맨 위에 있는 노드
* Level: 최상위 노드를 레벨0으로 했을 때 하위 Branch로 연결된 노드의 깊이를 나타냄
* Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
* Child Node: 어떤 노드의 하위 레벨에 연결된 노드
* Leaf Node: Child Node가 하나도 없는 노드
* Sibling Node: 동일 Parent Node를 가진 노드



3-1. hash table 만들기
hash_table = list([i for i in range(10)])
print(hash_table)
-->
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

# 3. 이진 트리와 이진 탐색 트리
* 이진 트리: 노드의 최대 Branch가 2개인 트리
* 이진 탐색 트리: 이진 트리에 아래와 같은 조건이 추가된 트리
    * 조건: 왼쪽 노드는 부모 노드 보다 작은 값, 오른쪽 노드는 부모 노드보다 큰 값을 가짐!

 

# 4. 자료구조 이진 탐색 트리의 장점과 주요 용도

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

 

# 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

head = Node(10)
BST = NodeMgmt(head)

BST.insert(4)
BST.insert(9)
BST.insert(13)
BST.insert(11)

 

# 문제1
* 이진 탐색 트리의 탐색(Search) 메서드를 만들어보자
* 단, 결과는 bool 타입으로 반환

```
def search(self, value):
    pass
```

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


head = Node(10)
BST = NodeMgmt(head)
BST.insert(4)
BST.insert(9)
BST.insert(13)
BST.insert(11)

print(BST.search(9))
print(BST.search(100))
-->
True
False

 

# 이진 탐색 트리 삭제
# Leaf Node 삭제
# 삭제할 Node의 Parent Node가 Node를 가리키지 않도록 함

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

        # 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

        return True

 

# child node가 하나인 Node를 삭제
# 삭제할 node의 parent node가 삭제할 node의 child node를 가리키게 함

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

        # 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

        # child node가 하나인 경우
        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

        return True

 

 

# child node가 두개인 Node를 삭제
# 1. 삭제할 node의 오른쪽 자식 중, 가장 작은 값을 삭제할 node의 parent node가 가리키도록 함
# 2. 삭제할 node의 왼쪽 자식 중, 가장 큰 값을 삭제할 node의 parent node가 가리키도록 함

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

        # 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

        # child node가 하나인 경우
        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

        # child node가 두개인 경우
        elif self.current_node.left != None and self.current_node.right != None:
            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.current_node.left
            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

# **6. 전체 코드 테스트**

import random

bst_nums = set()
while len(bst_nums) != 100:
    value = random.randint(0, 999)
    if value != 500:
        bst_nums.add(value)
print(bst_nums)


head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
    binary_tree.insert(num)

for num in bst_nums:
    if binary_tree.search(num) == False:
        print('검색 실패! ', num)

delete_nums = set()
bst_nums = list(bst_nums)

while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0, 99)])
print(delete_nums)

for del_num in delete_nums:
    if binary_tree.delete(del_num) == False:
        print('삭제 실패! ', del_num)
    else:
        print('삭제 성공! ', del_num)

-->

삭제 성공!
709
삭제 성공!
389
삭제 성공!
968
삭제 성공!
622
삭제 성공!
975
삭제 성공!
529
삭제 성공!
402
삭제 성공!
151
삭제 성공!
696
삭제 성공!
90


binary_tree.search(8)
-->
False


binary_tree.delete(8)
-->
False