알고리즘 기초 - 이진 탐색 트리(Binary Search Tree)

🌈 이진 탐색 트리(Binary Search Tree)

🔥 트리 구조란?

🔥 이진 탐색 트리 : Node 생성 기능 구현

🔥 이진 탐색 트리 : Node 조회 기능 구현

🔥 이진 탐색 트리 : Node 삭제 기능 구현

🔥 이진 탐색 트리 모든 기능 구현

1. 트리 구조란?

• Node와 Branch를 이용해서 싸이클을 이루지 않도록 구성하는 데이터 구조를 트리라고 함
• 이진 트리(노드의 최대 Branch가 2개인 트리)가 탐색 알고리즘 구현을 위해 주로 사용
• 이진 탐색 트리는 부모를 기준으로 왼쪽 자식은 작은 값, 오른쪽 자식은 높은 값으로 구성된 데이터 구조임(반대의 경우도 가능)
• 즉, 이진 탐색 트리는 이진 트리의 포함된 개념이나, 왼쪽 Child Node는 Parent Node 보다 작은 값, 오른쪽 Child Node는 Parent Node 보다 큰 값으로 구성된다는 차이가 있음
• 트리 관련 용어
  • Node : 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
  • Root Node : 트리 맨 위에 있는 노드
  • Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
  • Parent Node : 어떤 노드 다음 레벨에 연결된 노드
  • Child Node : 어떤 노드 상위 레벨에 연결된 노드
  • Leaf Node : Child Node가 하나도 없는 노드
  • Sibiling Node : 동일한 Parent Node를 가진 노드(Brother Node)
  • Depth : 트리에서 Node가 가질 수 있는 최대 Level

2. 이진 탐색 트리 : Node 생성 기능 구현

1) 이진 탐색 트리 란?

• 이진 탐색 트리는 배열보다 속도가 빠르다는 장점이 있음
• 이진 탐색 트리의 시간 복잡도는 O(logn) : (한번 실행될 때 마다, 탐색할 대상이 50%씩 줄어든다는 의미)
• 이진 트리에 아래 조건이 추가된 것이 이진 탐색 트리라로 생각하면 됨
  • 조건 : 작은 값은 왼쪽 아래, 크거나 같은 값은 오른쪽 아래로 branch를 통해 Node 생성

2) 이진 탐색 트리 생성 기능 구현

• 값이 들어왔을 때, RooT Node부터 시작하여 값이 크고 작은지 비교하고 들어온 값이 작을 땐 왼쪽으로 높을 땐 오른쪽 branch로 이동하여 생성
• 값을 비교한 후, 오른쪽 또는 왼쪽 Node에 이미 Node가 위치해 있다면 비교 대상(current_Node)을 업데이트한 뒤 값을 비교해서 빈 공간을 찾아 위치시킴

# 이진 탐색 트리 구현
class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
class NodeMgmt:
    def __init__(self, head):
        self.head = head # Root Node
    def insert(self, value):
        self.current_node = self.head # 비교는 Root 부터 시작
        while True:
            if value < self.current_node.value: # 입력된 값이 현재 노드값보다 작을 때(왼쪽 영역)
                if self.current_node.left != None: # 왼쪽 아래에 Node가 이미 존재할 때,
                    self.current_node = self.current_node.left
                else: # 왼쪽 아래에 Node가 없으면 바로 추가
                    self.current_node.left = Node(value)
                    break
            else: # 입력된 값이 현재 노드값보다 크거나 같을 때(오른쪽 영역)
                if self.current_node.right != None: # 오른쪽 아래에 Node가 이미 존재할 때,
                    self.current_node = self.current_node.right
                else: # 오른쪽 아래에 노드가 없으면 바로 추가
                    self.current_node.right = Node(value)
                    break
head = Node(1) # 루트노드를 우선 생성
BST = NodeMgmt(head) # 루트노드를 넣어 객체 생성
BST.insert(2)

3. 이진 탐색 트리 : Node 조회 기능 구현

1) 이진 탐색 트리 조회 기능 구현

• search 매서드를 작성하여 트리 검색 구현
• 검색 요청된 값을 head의 값부터 비교하여, 검색 요청된 값이 그 보다 더 작다면, 왼쪽 아래 Node로 이동하고, 크거나 같으면 오른쪽 아래 Node로 이동하면서 계속 비교
• 동일한 값을 찾으면 True를 반환하고, while문을 끝까지 돌았는데도 같은 값을 찾지 못햇을 때는 False를 반환

# Tree
# 이진 탐색 트리 구현
class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
class NodeMgmt:
    def __init__(self, head):
        self.head = head # Root Node
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value: # 입력된 값이 현재 노드값보다 작을 때(왼쪽 영역)
                if self.current_node.left != None: # 왼쪽 아래에 Node가 이미 존재할 때,
                    self.current_node = self.current_node.left
                else: # 왼쪽 아래에 Node가 없으면 바로 추가
                    self.current_node.left = Node(value)
                    break
            else: # 입력된 값이 현재 노드값보다 크거나 같을 때(오른쪽 영역)
                if self.current_node.right != None: # 오른쪽 아래에 Node가 이미 존재할 때,
                    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 # 왼쪽 아래 Node로 변경
            else: # 찾고자하는 값이 현재 노드의 값보다 크거나 같을 때,
                self.current_node = self.current_node.right # 오른쪽 아래 Node로 변경
        return False # while문에서 반복하며 값을 찾았는데도 실패했을 때는 False 반환
# 이진 탐색 트리
head = Node(1) # 루트노드를 우선 생성
BST = NodeMgmt(head) # 루트노드를 넣어 객체 생성
# 데이터 삽입(노드 생성)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)
# 데이터 검색
print(BST.search(8)) # True
print(BST.search(5)) # False
print(BST.search(4)) # True
print(BST.search(2)) # True

4. 이진 탐색 트리 : Node 삭제 기능 구현

0) 삭제할 Node가 Tree 내에 존재하는지 확인

• 삭제할 Node가 Tree안에 있는지 먼저 확인을 한 후 삭제를 구현

    def delete(self, value):
        searched = False # 없을 때를 대비해서 Default로 False를 줌
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value: # 찾았을 경우 True를 반환
                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: # 못찾았을 경우에는 False 반환
            return False

1) 삭제할 Node가 Leaf Node인 경우

• 삭제할 Node의 Parent Node가 삭제할 Node를 가르키지 않도록 하면 됨(None으로 만듬)

    def delete(self, value):
        searched = False # 없을 때를 대비해서 Default로 False를 줌
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value: # 찾았을 경우 True를 반환
                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: # 못찾았을 경우에는 False 반환
            return False
        ## 1) 삭제할 Node가 Leaf Node인 경우
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value: # 삭제할 노드 값이 부모의 노드 값보다 작으면, 왼쪽 아래를 None으로 변경
                self.parent.left = None
            else: # 삭제할 노드 값이 부모의 노드 값보다 크거나 같으면, 오른쪽 아래를 None으로 변경
                self.parent.right = None
            # del self.current_node # value 삭제

2) 삭제할 Node가 Child Node를 1개 가진 경우

• 제거 대상(삭제할 Node)의 Parent Node가 제거 대상(삭제할 Node)의 Child Node를 가르키도록 함

    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
        ## 1) 삭제할 Node가 Leaf Node인 경우(코드 생략)
        ## 2) 삭제할 Node가 Child Node를 1개 가진 경우
        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

3) 삭제할 Node가 Child Node를 2개 가진 경우

• 아래 2가지 중 1가지 전략을 택함
  • 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가르키도록 함
  • 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가르키도록 함
• 위 전략 중 첫번째 방법을 사용할 때, 세부 방법
  • 삭제할 Node의 오른쪽 Node의 자식들 중, 가장 왼편에 있는 마지막 Node를 선택
  • 해당 Node를 삭제할 Node의 위치로 교체함
  • 가장 왼쪽의 마지막 Node이기 때문에 해당 Node의 왼쪽 자식은 없기 때문에 해당 Node의 왼쪽 자식을 원래 삭제할 Node의 왼쪽 자식과 연결시킴
  • 해당 Node의 오른쪽 자식 Node를 삭제할 Node의 오른쪽 Node와 연결시킴
  • 만일, 해당 Node의 오른쪽 자식 Node를 가지고 있었을 경우, 해당 Node의 원래 부모 노드의 왼쪽 Branch가 해당 Node의 오른쪽 Node를 가르키게함

    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
        ## 1) 삭제할 Node가 Leaf Node인 경우(코드 생략)
        ## 2) 삭제할 Node가 Child Node를 1개 가진 경우(코드 생략)
        ## 3) 삭제할 Node가 Child Node를 2개 가진 경우
        elif self.current_node.left != None and self.current_node.right != None:
            ## 3-1-1) 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 없을 때
            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
            ## 3-1-2) 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 있을 때
                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
            ## 3-2-1) 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 없을 때
            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
            ## 3-2-2) 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 Child Node가 없을 때
                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.left = self.current_node.left
                self.change_node.right = self.current_node.right
        return True 

5. 이진 탐색 트리 모든 기능 구현

• insert 메서드 : node 생성 기능
• search 메서드 : node 조회 기능
• delete 메서드 : node 삭제 기능
  0. 데이터 존재하는지 확인
  1. 삭제할 Node(target)가 Leaf Node인 경우
  2. 삭제할 Node(target)가 Child Node를 1개 갖고 있는 경우
  • 2-1. 삭제할 Node가 왼쪽 Child Node(self.current_node.left)만 갖고 있는 경우
  • 2-2. 삭제할 Node가 오른쪽 Child Node(self.current_node.right)만 갖고 있는 경우
  3. 삭제할 Node(target)가 Child Node를 2개 갖고 있는 경우
  • 3-1. taget이 Parent Node의 왼쪽에 있는 경우
    ⇢ 3-1-1. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있는 경우
    ⇢ 3-1-2. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없는 경우
  • 3-2. taget이 Parent Node의 오른쪽에 있는 경우
    ⇢ 3-2-1. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있는 경우
    ⇢ 3-2-2. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없는 경우

class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    # 1.데이터 삽입
    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
    # 2.데이터 조회
    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
    # 3.데이터 삭제
    def delete(self, value):
        # 3-0. 데이터 존재하는지 확인
        serached = False
        self.current_node = self.head # self.current_node : target(삭제할 Node)
        self.parent = self.head # self.parent : target의 부모 노드
        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
        # while이 종료되었는데도, searched가 False라면 일치하는 value가 없는 것        
        if searched == False: 
            return False
        # ⭐️ 이 아래의 코드가 실행된다는 의미는 삭제할 Node가 Tree안에 존재한다는 의미이며, 이에 삭제 기능을 구현
        # ⭐️ 이 상태에서 self.current_node는 삭제할 Node이고, self.parent는 삭제할 node의 Parent Node가 됨
        # 3-1. 삭제할 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
            # None을 만들어주기만해도, Tree에서 연결이 끊겨 조회되지 않으나 명확히 하기 위해 삭제해주는 것이 좋음    
            del self.current_node 
        # 3-2. 삭제할 Node가 Child Node를 1개 갖고 있는 경우
        # 3-2-1. 삭제할 Node가 왼쪽 Child Node(self.current_node.left)만 갖고 있는 경우
        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
        # 3-2-2. 삭제할 Node가 오른쪽 Child Node(self.current_node.right)만 갖고 있는 경우        
        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
        # 3-3. 삭제할 Node(target)가 Child Node를 2개 갖고 있는 경우
        if self.current_node.left != None and self.current_node.right != None:
            # 3-3-1. taget이 Parent Node의 왼쪽에 있는 경우, target의 오른쪽 Node 중 가장 작은 값 찾음
            if value < self.parent.value:
                self.change_node = self.current_node.right # change_node : 아래쪽에서 끌어올릴 Node
                self.change_node_parent = self.current_node.right
                while self.change_node_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                # 3-3-1-1. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있는 경우       
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                # 3-3-1-2. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없는 경우        
                else:
                    self.change_node_parent.left = None
                # ⭐️ change_node를 위로 끌어올림
                # ⭐️ 3-0이 끝난 시점에서 self.current_node는 target 이고 self.parent는 target의 부모인 상태임
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            # 3-3-2. taget이 Parent Node의 오른쪽에 있는 경우
            else: # 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
                # 3-3-2-1. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있는 경우       
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                # 3-3-2-2. target이 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없는 경우        
                else:
                    self.change_node_parent.left == None
                # ⭐️ change_node를 위로 끌어올림
                # ⭐️ 3-0이 끝난 시점에서 self.current_node는 target 이고 self.parent는 target의 부모인 상태임
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right
# Node 생성 Test
import random
# 1~999 숫자 중 임의로 100개를 랜덤으로 추출해서 이진 탐색 Tree 생성
head = Node(500)
binary_tree = NodeMgmt(head)
bst_nums = set() # 중복 제거
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0,999))
for num in bst_nums:
    binary_tree.insert(num)
# Node 조회 Test
for num in bst_nums:
    if binary_tree.search(num) == False:
        print('search fasli', num) # 아무것도 출력안되면 search 기능 정상       
# Node 삭제 Test
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0,99)])
for del_num in delete_nums:
    if binary_tree.delete(del_num) == False:
        print('delete failed', del_num)