Home 이진 탐색 트리(Binary Search Tree, BST)
Post
Cancel

이진 탐색 트리(Binary Search Tree, BST)

Posted Sep 20, 2022 Updated Sep 21, 2022
By 김경민
13 min read

기본 시작 틀

  • 링크드 리스트와 흡사

안 보더라도 이것만은 기억하자

각 노드의 좌측에는 작은 숫자, 우측에는 큰 숫자가 저장된다.

1
2
3
4
5
6
7
8
9

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class NodeMgmt:
    def __init__(sel, value):
        self.head = head

삽입

  • case 1 : 삽입하는 데이터 값이 현재 노드의 데이터 값 보다 작고 왼쪽 값이 비어 있으면 삽입
  • case 2 : 삽입하는 데이터 값이 현재 노드의 테이터 값 보다 크고 오른쪽 값이 비어 있으면 삽입
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

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class NodeMgmt:
    def __init__(self, value):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            # 넣으려는 데이터가 현재 노드의 데이터보다 작니?
            if value < self.current_node.value:
                # 작다면 노드의 왼쪽이 None이냐
                if self.current_node.left != None:
                    #None이 아니라면 현재 노드에 현재 노드의 왼쪽 노드를 대입
                    self.current_node = self.current_node.left
                else:
                    #None이라면 현재 노드의 왼쪽에 노드를 생성하여 대입
                    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

삭제

  • 자식 노드가 없다면 그냥 삭제
  • 자식 노드가 하나라면 빼고 이어주면 된다.
  • 하지만 가지가 두 개라면?!오른쪽 자식노드의 가장 작은 놈으로 바꾸기!!(왼쪽 가장 큰 노드로도 가능)

설명을 위한 지칭

  • 타노드 : 타겟 노드
  • 타부노드 : 타겟 노드의 부모 노드
  • 오가작노드 : 타겟 노드의 오른쪽 자식 노드의 가장 작은 노드
  • 오가작부노드 : 타겟 노드의 오른쪽 자식 노드의 가장 작은 노드의 부모 노드

흐름

  1. 타겟 노드(타노드)와 타겟 노드의 부모 노드(타부노드)를 구한다

  2. case 1 : 타노드의 자식 노드가 하나도 없을 때 없을 때
    • 타부노드의 왼쪽, 오른쪽인지 판별 후 None처리
  3. case 2 : 타노드의 자식 노드가 둘 다 있을 때
    • 오른쪽 자식 노드들 중 가장 작은 노드(오가작노드)와 그 노드의 부모 노드(오가작부노드)를 찾는다
    • case2-1) 경우 1 : 오가작부노드가 head(가장 꼭대기)일 때는, 오가작부노드의 오른쪽에 오가작노드의 오른쪽을 연결.
    • case2-2) 경우 2 : 오가작부노드가 head가 아닐 때는, 오가작부노드의 왼쪽과 오가작노드의 오른쪽을 이어준다.
  4. case 3 : 타노드의 자식이 오른쪽이나 왼쪽 하나 있을 때 (위에서 둘 다 없을 때, 있을 때의 경우를 나눴으므로 무조건 왼,오 중 하나만 있음)
    • 타노드가 head인지 확인 후 처리(추가)
    • 타노드가이 타부노드의 오른쪽에 있는지 왼쪽에 있는지 판별
      • 타노드의 자식이 오른쪽에 있는지 왼쪽에 있는지 판별 후 연결

왜 case 2 에서 두 가지 경우로 나뉘나?

  • 타겟 노드의 바로 오른쪽 자식의 가장 작은 노드를 찾고(오가작노드)
  • 그 노드는 가장 작은 값이나 오른쪽으로 뻗은 가지가 있을 수 있다.
  • 이런 경우 그 오른쪽으로 뻗은 가지를 부모 노드(오가작부노드)의 왼쪽과 연결해 줘야한다.
  • 그러나 오가작부 노드가 head(가장 꼭대기)일 때, head의 왼쪽과 연결하면 데이터가 덮어씌워지고 트리의 조건이 깨진다.
  • 그래서 오가작부 노드가 head일 때를 따로 처리해주는 것

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class NodeMgmt:
    def __init__(self, value):
        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 delete(self,value):
        # 타노드와 타부노드 초기 시작 설정
        self.target_node = self.head
        self.target_parent_node = self.target_node
        # 타노드와 타부노드 찾기(데이터 값이 같을 때 까지)
        while self.target_node.value != value:
            self.target_parent_node = self.target_node
            if self.target_node.value > value:
                self.target_node = self.target_node.left
            else:
                self.target_node = self.target_node.right

        #case 1 타노드의 자식 노드가 하나도 없을 경우
        if self.target_node.left == None and self.target_node.right == None:
            # 타노드가 타부노드의 왼쪽이냐 오른쪽이냐 판별 후 타부노드에서 가지치기
            if self.target_node == self.target_parent_node.left:
                self.target_parent_node.left = None
            else:
                self.target_parent_node.right = None
            return True
        else:
            #case 2 타노드의 자식 노드가 둘 다 있을 때
            if self.target_node.left and self.target_node.right:            
                print('case3')
                # 오가작노드와 오가작부노드 초기 설정
                self.right_min_node = self.target_node.right
                self.min_parent_node = self.target_node
                # 오가작노드와 오가작부노드 찾기(가장 왼쪽 노드 찾기)
                while self.right_min_node.left:
                    self.min_parent_node = self.right_min_node
                    self.right_min_node = self.right_min_node.left
                # case 2 - 1 : 오가작부노드가 head인가요?
                if self.min_parent_node == self.head:
                    # 맞다면 오가작부노드의 오른쪽에 오가작노드의 오른쪽을 연결
                    self.min_parent_node.right = self.right_min_node.right
                    self.head.value = self.right_min_node.value
                else:
                    # 아니라면 오가작부노드의 왼쪽에 오가작노드의 오른쪽을 연결
                    self.min_parent_node.left = self.right_min_node.right
                    self.target_node.value = self.right_min_node.value
                    
                return True

            #case 3 자식이 하나만 있을 때
            # 타노드가 헤드와 같냐
            if self.target_node == self.head:
                if self.target_node.left:
                    self.head = self.target_node.left
                else:
                    self.head = self.target_node.right
            # 타겟이 부모의 오른쪽에 있는지 왼쪽에 있는지 판별
            elif self.target_parent_node.left == self.target_node:
                # 타겟이 왼쪽, 오른쪽 어느 자식이 있는지 판별하고 연결
                if self.target_node.left:
                    self.target_parent_node.left = self.target_node.left
                else:
                    self.target_parent_node.left = self.target_node.right
            else:
                if self.target_node.left:
                    self.target_parent_node.right = self.target_node.left
                else:
                    self.target_parent_node.right = self.target_node.right
            del self.target_node
            return True

검색을 추가한 코드 + 트리를 볼 수 있는 코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class NodeMgmt:
    def __init__(self, value):
        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 self.current_node.value > value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False

    def delete(self,value):
        if self.search(value) == False:
            return False

        self.target_node = self.head
        self.target_parent_node = self.target_node
        
        while self.target_node.value != value:
            self.target_parent_node = self.target_node
            if self.target_node.value > value:
                self.target_node = self.target_node.left
            else:
                self.target_node = self.target_node.right

        if self.target_node.left == None and self.target_node.right == None:
            if self.target_node == self.target_parent_node.left:
                self.target_parent_node.left = None
            else:
                self.target_parent_node.right = None
            return True
        else:
            if self.target_node.left and self.target_node.right:            
                self.right_min_node = self.target_node.right
                self.min_parent_node = self.target_node
                while self.right_min_node.left:
                    self.min_parent_node = self.right_min_node
                    self.right_min_node = self.right_min_node.left
                if self.min_parent_node == self.head:
                    self.min_parent_node.right = self.right_min_node.right
                    self.head.value = self.right_min_node.value
                else:
                    self.min_parent_node.left = self.right_min_node.right
                    self.target_node.value = self.right_min_node.value
                    
                return True

            if self.target_parent_node.left == self.target_node:
                if self.target_node.left:
                    self.target_parent_node.left = self.target_node.left
                else:
                    self.target_parent_node.left = self.target_node.right
            else:
                if self.target_node.left:
                    self.target_parent_node.right = self.target_node.left
                else:
                    self.target_parent_node.right = self.target_node.right
            return True

1
2
3
4

def view(node):
    if node == None:
        return []
    return view(node.left)+ [node.value] + view(node.right)

사용해보기

1
2
3
4
5
6
7
8
9
10
11
12

head = Node(10)
tree1 = NodeMgmt(head)
tree1.insert(5)
tree1.insert(3)
tree1.insert(7)
tree1.insert(6)
tree1.insert(15)
tree1.insert(19)
tree1.insert(18)
tree1.insert(11)
tree1.insert(13)
tree1.insert(20)

1

view(head)

1

[3, 5, 6, 7, 10, 11, 13, 15, 18, 19, 20]

1
2

tree1.delete(20)
view(head)

1

[3, 5, 6, 7, 10, 11, 13, 15, 18, 19]

1
2

tree1.delete(11)
view(head)

1

[3, 5, 6, 7, 10, 13, 15, 18, 19]

1
2

tree1.delete(10)
view(head)

1

[3, 5, 6, 7, 13, 15, 18, 19]

강의에서 나온 코드(내것 보다 더 정확할 것)

  • 혼자 생각하면서 코드를 잘 짰다고 생각했으나
  • 부족한 점은 많을 것이다. 그러므로 강의의 코드도 추가해두겠다.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

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
Algorithm, data structure
python data structure bst
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents