Python/알고리즘&자료구조

Python 자료구조&알고리즘 - 트리(Tree), 이진 탐색

code2772 2023. 1. 31. 07:50
728x90
반응형

1. 트리(Tree)

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

2. 알아둘 용어

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

 

3. 이진 트리와 이진 탐색 트리(Binary Search Tree)

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

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

  • 주요 용도: 데이터 검색(탐색)
  • 장점: 탐색 속도를 개선할 수 있음
  • 단저: 이진 탐색 트리 알고리즘 이해 후에 살펴봐야 함

5. 파이썬 객체지향 프로그래밍으로 이진 탐색 트리 구현하기

 

5-1. 노드 클래스 만들기

 
[ ]
  
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
 

5-2. 이진 탐색 트리에 데이터 넣기

  • 조건: 중복 데이터를 넣지 않음
 
[ ]
  
class NodeMgmt:
    def __init__(self, head): 
        self.head = head    # head에 head값 저장

    def insert(self, value):
        self.current_node = self.head # current_node에 head 저장
        while True:
            if value < self.current_node.value: # value값이 current_node의 값보다 작으면
                if self.current_node.left != None: # 
                    self.current_node = self.current_node.left # current_node에 current_node.left 저장
                else:
                    self.current_node.left = Node(value) # current_node.left에 값이 없으면 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(5)
 
 
[ ]
  
class NodeMgmt:
    def __init__(self, head): 
        self.head = head    # head에 head값 저장

    def insert(self, value):
        self.current_node = self.head # current_node에 head 저장
        while True:
            if value < self.current_node.value: # value값이 current_node의 값보다 작으면
                if self.current_node.left != None: # 
                    self.current_node = self.current_node.left # current_node에 current_node.left 저장
                else:
                    self.current_node.left = Node(value) # current_node.left에 값이 없으면 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(2)
BST.insert(5)
BST.insert(13)
BST.insert(19)
BST.insert(11)
BST.insert(8)
 
 
[ ]
  
BST.search(11)
  
True
 
[ ]
  
BST.search(7)
  
False
 

5-4. 이진 탐색 트리의 삭제

  • Leaf Node 삭제
    • Leaf Node: child Node가 없는 Node
    • 삭제할 Node의 Parent Node가 Node를 가리키지 않도록 함
 
  1. 삭제할 node 탐색하기
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
        self.current_node = self.current_node.left
    else:
        self.parent = self.current_node
        self.current_node = self.current_node.right
if searched == Fase:
    return False
 
  • 삭제할 node가 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가 하나면 node를 삭제
    • 삭제할 node의 Parent Node가 삭제할 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를 삭제
    • 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 함
    • 삭제할 Node가 Parent Node 왼쪽에 있을 때
      • 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
      • 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 있을 때
    • 삭제할 Node가 Parent Node 오른쪽에 있을 때
      • 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
      • 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 있을 때

가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 절대 없음! 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 존재한다는 뜻이기 때문

 
  • Child Node가 두개인 Node를 삭제하는 코드 구현하기
    • 삭제할 Node의 오른쪽 자식을 선택
    • 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
    • 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
    • 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
    • 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
    • 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함
        if 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
 

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
        # 삭제할 노드가 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가 하나인 경우
        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가 두개인 경우
        if 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
 
 

5-6 전체 코드 테스트

 
[ ]
  
# random 라이브러리
# random.randint(숫자1, 숫자2) : 숫자1부터 숫자 2사이에 있는 숫자를 랜덤하게 선택하여 리턴
import random

bst_nums = set()
while len(bst_nums) != 100:
  val = random.randint(0, 999)
  if val != 500:
    bst_nums.add(val)
print(bst_nums)
  
{4, 9, 17, 20, 35, 40, 42, 563, 568, 578, 579, 75, 592, 80, 96, 100, 106, 107, 110, 628, 631, 632, 634, 138, 655, 152, 168, 170, 684, 174, 176, 182, 183, 185, 699, 702, 703, 190, 194, 209, 728, 735, 227, 229, 230, 231, 240, 757, 250, 763, 764, 765, 766, 770, 775, 272, 789, 793, 288, 290, 805, 812, 814, 821, 309, 826, 833, 834, 836, 324, 848, 343, 857, 346, 354, 359, 369, 883, 373, 376, 896, 901, 903, 395, 910, 398, 914, 916, 920, 412, 934, 423, 936, 955, 446, 968, 972, 977, 465, 480}
 
[ ]
  
# 루트노드를 500으로 설정, 100개의 데이터를 추가
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(10,99)])
print(delete_nums)
  
{96, 376, 231, 240, 977, 465, 628, 728, 826, 190}
[ ]
  
for del_num in delete_nums:
  if binary_tree.delete(del_num) == False:
    print('삭제 실패', del_num)
  else:
     print('삭제 성공', del_num)
  
삭제 성공 96
삭제 성공 376
삭제 성공 231
삭제 성공 240
삭제 성공 977
삭제 성공 465
삭제 성공 628
삭제 성공 728
삭제 성공 826
삭제 성공 190
[ ]
 
 
 
  
False
[ ]
 
 
 
  
True
반응형

'Python > 알고리즘&자료구조' 카테고리의 다른 글

Python 자료구조 & 알고리즘 - 복잡도  (0) 2023.02.20
Python 자료구조&알고리즘 - 힙(Heap)  (0) 2023.02.01
Python 자료구조&알고리즘 - 해쉬 테이블(Hash Table)  (0) 2023.01.30
Python 알고리즘&자료구조 더블 링크드 리스트(Doubly Linked List)  (0) 2023.01.29
Python 자료구조&알고리즘 - 링크드리스트(Linked List)  (0) 2023.01.28

'Python/알고리즘&자료구조'의 다른글

  • 현재글Python 자료구조&알고리즘 - 트리(Tree), 이진 탐색

관련글

티스토리툴바