[자료구조] 이진 탐색 트리 with Python

Notice

Recent Posts

Recent Comments

Link

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

DOing

[자료구조] 이진 탐색 트리 with Python 본문

알고리즘

[자료구조] 이진 탐색 트리 with Python

mangdo 2021. 6. 21. 19:19

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

: 이진트리에 다음과 같은 추가적인 조건이 있는 트리

1) 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰값을 가진다.

2) 모든 노드는 오른쪽 가지에 포함되는 어떤 숫자보다도 작은값을 가진다.

해당 그림에서 볼 때 14를 예시로 들어보자.

1) 14는 왼쪽가지에 포함되는 11보다 큰값을 가진다.

2) 14는 오른쪽가지에 포함되는 15,18,19보다 작은값을 가진다.

💡 이진 탐색 트리 삽입, 탐색 동작과정

[ 탐색과정 ]

1. 찾는 숫자가 현재 노드 값과 같다면 탐색 성공!

2. 찾는 숫자가 현재 노드 값보다 작다면 왼쪽으로 간다.

3. 찾는 숫자가 현재 노드 값보다 크다면 오른쪽으로 간다.

[ 삽입과정 ]

1. 삽입할 숫자가 현재 노드 값보다 작다면 왼쪽으로 간다.

2. 삽입할 숫자가 현재 노드 값보다 크다면 오른쪽으로 간다.

3. 자식노드가 없을 때까지 1~2과정을 반복하고 자식노드가 없을 때 만들어서 연결시켜준다.

💡 이진 탐색 트리 삽입, 탐색 코드

class Node:
    def __init__(self, value):
        # double linked list
        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(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)

print(BST.search(2))
print(BST.search(5))

💡 이진 탐색 트리의 삭제 동작

이진 탐색 트리의 삭제는 어렵기 때문에 경우를 나눠서 생각해보자.

1) Leaf Node를 삭제

: parent node가 삭제할 노드를 가르키지 않도록 한다.

2) Child Node가 한개인 Node 삭제

: 삭제할 노드의 Parent Node가 삭제할 Node의 child Node를 가르키도록 한다.

3) Child Node가 두개인 Node 삭제(중요!)

: 삭제할 Node의 오른족 자식 중, 가장 작은값을 Parent Node가 가리키도록한다.

: 또는 삭제할 노드의 왼쪽 자식 중, 가장 큰값을 Parent Node가 가리키도록한다.

글로 정리하면 다음과 같다.

1. 삭제할 Node의 오른쪽자식 선택

2. 오른쪽 자식의 가장 왼쪽에 있는 Node 선택

3. 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 브랜치가 가르키게 함.

4. 해당 Node의 왼쪽 브랜치가 삭제할 Node의 왼쪽 child Node를 가르키게 함

5. 해당 Node의 오른쪽 branch가 삭제할 Node의 오른쪽 child Node를 가르키게 함

6. 만약 해당 Node가 오른쪽 child node를 가지고 있었을 경우,

해당 Node의 본래 Parent Node의 왼쪽 브랜치가 해당 Node의 오른쪽 child Node를 가르키게함

이걸 코드로 옮기면된다...^^

💡 이진 탐색 트리의 삭제 코드

아까 써넣은 NodeMgmt 클래스에 들어가는 함수라는 것을 기억해라.

다 넣으려면 너무 길어지니까!

    def delete(self, value):
        # 삭제할 노드 탐색
        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.curent_node = self.current_node.left  # 비교대상 변경
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right  # 비교대상 변경

        if searched == False:  # 그런 값을 가진 노드가 없다 = 삭제할 노드가 없다
            return False

        ## 해당노드를 찾았다. 이제 삭제를 하자!

1) Leaf Node를 삭제

: parent node가 삭제할 노드를 가르키지 않도록 한다.

# 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

2) Child Node가 한개인 Node 삭제

: 삭제할 노드의 Parent Node가 삭제할 Node의 child Node를 가르키도록 한다.

child 노드를 오른쪽에 가지고 있냐, 왼쪽에 가지고 있냐에 따라 다른 코드를 가진다.

# case2
        # 왼쪽 노드만 가지고 있다.
        elif self.current_node.left != None and self.current_node.right == None:
            # 삭제할 노드가 parent의 오른쪽에 있냐 왼쪽에 있냐
            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) Child Node가 두개인 Node 삭제

3-1. 삭제할 노드가 parent node 왼쪽에 있다.

3-1-1. 삭제할 노드의 오른쪽 자식중, 가장 작은 값을 가진 node의 chlid node가 없을때

3-1-2. 삭제할 노드의 오른쪽 자식중, 가장 작은 값을 가진 node의 오른쪽에 chlid node가 있을때

: 오른쪽에 chlid node가 있을 수 있다. 왼쪽에 있었으면 걔가 올라가겠지?

# case3 : 삭제할 노드가 두개의 자식을 가진다
        if 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

                # 가장 작은값은 무조건 left에 있다 = 일단 left 끝까지 가게
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                self.change_node = self.change_node.left

                # 3-1-2
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-1-1
                    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. 삭제할 노드가 parent node의 오른쪽에 있다.

3-2-1. 삭제할 노드의 오른쪽 자식중, 가장 작은 값을 가진 node의 chlid node가 없을때

3-2-2. 삭제할 노드의 오른쪽 자식중, 가장 작은 값을 가진 node의 오른쪽에 chlid node가 있을때

: 오른쪽에 chlid node가 있을 수 있다. 왼쪽에 있었으면 걔가 올라가겠지?

# case3-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.chage_node = self.change_node.left  # 비교 대상 변경
                # 3-2-2
                if self.chage_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-2-1
                    self.change_node_parent.left = None

                # 위로 옮긴다.
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.chage_node.right = self.current_node.right

전체 코드 보기

class Node:
    def __init__(self, value):
        # double linked list
        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):
        # 삭제할 노드 탐색
        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.curent_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:
            # 삭제할 노드가 parent의 오른쪽에 있냐 왼쪽에 있냐
            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

        # case3 : 삭제할 노드가 두개의 자식을 가진다
        if 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

                # 가장 작은값은 무조건 left에 있다 = 일단 left 끝까지 가게
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                self.change_node = self.change_node.left

                # 3-1-2
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-1-1
                    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
            # case3-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.chage_node = self.change_node.left  # 비교 대상 변경
                # 3-2-2
                if self.chage_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-2-1
                    self.change_node_parent.left = None

                # 위로 옮긴다.
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.chage_node.right = self.current_node.right


# 1부터 999 숫자 중에서 임의로 100개 추출하여 이진 트리에 입력/검색/삭제
import random

# 1~999중 100개의 숫자 랜덤 선택
bst_nums = set()  # 100개를 랜덤선택하다보면 중복이 있을 수 있는데 집합(set)으로 이를 방지
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))  # 중복이라면 아예 들어가질 않음. 그래서 반복문은 100번 이상 실행될 가능성이 높음

#print(bst_nums)

# 선택된 100개의 숫자를 이진 탐색트리에 입력, 루트노트는 500으로 임의로 지정
# 1이나 999이러면 한쪽에 치우친 트리가 될것이다. 주의하자
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)  # 인덱스로 접근하기 위해 list타입으로 변형시킨다.
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)  # 이게 사실 나오면 코드 잘못짠것임

테스트 코드

테스트 코드를 돌렸을때 아무것도 나오지 않는다면 잘 짠것이다.

# 1부터 999 숫자 중에서 임의로 100개 추출하여 이진 트리에 입력/검색/삭제
import random

# 1~999중 100개의 숫자 랜덤 선택
bst_nums = set()  # 100개를 랜덤선택하다보면 중복이 있을 수 있는데 집합(set)으로 이를 방지
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))  # 중복이라면 아예 들어가질 않음. 그래서 반복문은 100번 이상 실행될 가능성이 높음

#print(bst_nums)

# 선택된 100개의 숫자를 이진 탐색트리에 입력, 루트노트는 500으로 임의로 지정
# 1이나 999이러면 한쪽에 치우친 트리가 될것이다. 주의하자
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)  # 인덱스로 접근하기 위해 list타입으로 변형시킨다.
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)  # 이게 사실 나오면 코드 잘못짠것임

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

[ 시간 복잡도 ]

: 노드가 n개 일때 트리의 높이 h = logn이다.

: 즉, 이진 탐색트리의 시간복잡도는 O(logn)으로 리스트에서 탐색할시에는 O(n)이 걸리는 것에 비해 빠르게 처리가능하다.

[ 단점 ]

: O(logn)은 트리가 균형잡혀있을 때의 평균 시간복잡도이다.

: 위의 그림과 같이 root node를 잘못잡아서 트리가 불균형이 되어 최악의 경우, linked list와 동일한 성능을 보일 수 있다. 그래서 균형잡힌 트리를 잡는 것이 중요한데, 깊게 들어가면 이런 알고리즘도 존재한다.

출처

PENJEE.COM'S BLOG : 이진탐색트리

패스트 캠퍼스 알고리즘 올인원 강의

저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[자료구조] 스택, 큐, 데큐 (0)	2021.06.22
[자료구조] 그래프 (0)	2021.06.15
[알고리즘] Disjoint Sets(서로소 집합) (0)	2021.05.31
[알고리즘] 플로이드 워셜 with Python (0)	2021.05.23
[알고리즘] 다익스트라 최단경로 with Python (0)	2021.05.23

'알고리즘' Related Articles

DOing

[자료구조] 이진 탐색 트리 with Python 본문

[자료구조] 이진 탐색 트리 with Python

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

💡 이진 탐색 트리 삽입, 탐색 동작과정

💡 이진 탐색 트리 삽입, 탐색 코드

💡 이진 탐색 트리의 삭제 동작

💡 이진 탐색 트리의 삭제 코드

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

'알고리즘' 카테고리의 다른 글

티스토리툴바