Binary Search Tree - 이진 탐색 트리

이진 탐색 트리입니다.

 

https://en.wikipedia.org/wiki/Binary_search_tree

Binary search tree - Wikipedia

이진 탐색 트리는 아래아 같은 조건을 가지고 있습니다.

• 완전이진트리이다.
• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

Go 코드는 아래 링크에서 확인했습니다. 설명이 쉽게 되어 있습니다.

https://about.sourcegraph.com/go/gophercon-2018-binary-search-tree-algorithms

GopherCon 2018 - Demystifying Binary Search Tree Algorithms

Go로 구현된 코드입니다.

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
109
110
111
112
113
114
115
116
117
package main
import "fmt"
// Node 구조체는 이진트리의 노드를 구성합니다.
type Node struct {
    Key   int
    Left  *Node // 왼쪽 노드는 현재 노드보다 작은 수를 갖습니다.
    Right *Node // 오른쪽 노드는 현재 노드보다 큰 수를 갖습니다.
}
// 이진 탐색 트리에서 값을 검색합니다.
func (n *Node) Search(searchKey int) bool {
    // 노드 구조체 n이 nil이라면 아루 값도 없는 경우 입니다.
    if n == nil {
        return false
    }
    // 찾으려는 값이 노드의 key보다 크다면 오른쪽 노드에서 다시 찾습니다.
    // 그렇지 않다면 (찾으려는 값이 노드의 key보다 작다면) 왼쪽 노드에서 다시 찾습니다.
    if n.Key < searchKey {
        return n.Right.Search(searchKey)
    } else if n.Key > searchKey {
        return n.Left.Search(searchKey)
    }
    // 위 조건에 포함하지 않는다면 n.key는 찾으려는 값입니다.
    // n.Key == key
    return true
}
// 이진 탐색 트리에 값을 추가합니다.
func (n *Node) Insert(addKey int) {
    // 추가하려는 값이 노드의 key보다 크다면 오른쪽 노드에서 다시 추가 조건을 확인합니다.
    // 그렇지 않다면 (추가하려는 값이 노드의 key보다 작다면) 왼쪽 노드에서 다시 추가 조건을 확인합니다.
    // 오른쪽 또는 왼쪽 노드가 nil이라면 새로운 노드를 추가합니다.
    if n.Key < addKey {
        if n.Right == nil {
            n.Right = &Node{Key: addKey}
        } else {
            n.Right.Insert(addKey)
        }
    } else if n.Key > addKey {
        if n.Left == nil {
            n.Left = &Node{Key: addKey}
        } else {
            n.Left.Insert(addKey)
        }
    }
    // 만약 추가하려는 노드가 있을 경우 아무런 동작을 하지 않습니다.
    // n.Key == key
}
// 이진 탐색 트리에서 가장 작은값을 찾습니다.
// 트리의 왼쪽 끝에 있는 값이 가장 작은 값입니다.
func (n *Node) Min() int {
    if n.Left == nil {
        return n.Key
    }
    return n.Left.Min()
}
// 이진 탐색 트리에서 가장 큰값을 찾습니다.
// 트리의 오른쪽 끝에 있는 값이 가장 큰 값입니다.
func (n *Node) Max() int {
    if n.Right == nil {
        return n.Key
    }
    return n.Right.Max()
}
// 노드를 삭제합니다.
func (n *Node) Delete(removeKey int) *Node {
    // 삭제하려는 값이 노드 key보다 크다면 오른쪽 노드에서 삭제 작업을 진행합니다.
    // 만약 삭제하려는 값이 노드 key보다 작다면 왼쪽 노드에서 삭제 작업을 진행합니다.
    if n.Key < removeKey {
        n.Right = n.Right.Delete(removeKey)
    } else if n.Key > removeKey {
        n.Left = n.Left.Delete(removeKey)
        // 삭제하려는 key를 찾았을 경우
        // 대상 노드의 왼쪽 노드가 없을 경우 반대쪽인 오른쪽 노드를 리턴합니다.
        // 만약 대상 노드의 오른쪽이 없을 경우 반대쪽인 왼쪽 노드를 리턴합니다.
    } else {
        if n.Left == nil {
            return n.Right
        } else if n.Right == nil {
            return n.Left
        }
        // 먄악 대상 노드의 왼쪽과 오른쪽 노드가 모두 있을 경우
        // 오른쪽 노드에서 가장 작은 값을 확인합니다.
        min := n.Right.Min()
        // 대상 key를 오른쪽에서 찾은 가장 작은값으려 변경하고
        n.Key = min
        // 오른쪽에 있는 가장 작은 값을 삭제합니다.
        n.Right = n.Right.Delete(min)
    }
    return n
}
func main() {
    tree := &Node{6, nil, nil}
    tree.Insert(5)
    tree.Insert(8)
    fmt.Println(tree.Search(8))
    tree.Insert(12)
    tree.Insert(3)
    tree.Delete(5)
    fmt.Println(tree.Search(5))
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

다른 형태의 코드도 확인해 보겠습니다.

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
package main
import "fmt"
type Comparable func(c1 interface{}, c2 interface{}) bool
type BinaryTree struct {
    node    interface{}
    left    *BinaryTree
    right   *BinaryTree
    lessFun Comparable
}
func New(compareFun Comparable) *BinaryTree {
    tree := &BinaryTree{}
    tree.node = nil
    tree.lessFun = compareFun
    return tree
}
func (tree *BinaryTree) Search(value interface{}) *BinaryTree {
    if tree.node == nil {
        return nil
    }
    if tree.node == value {
        return tree
    } else {
        if tree.lessFun(value, tree.node) == true {
            t := tree.left.Search(value)
            return t
        } else {
            t := tree.right.Search(value)
            return t
        }
    }
}
func (tree *BinaryTree) Insert(value interface{}) {
    if tree.node == nil {
        tree.node = value
        tree.right = New(tree.lessFun)
        tree.left = New(tree.lessFun)
        return
    } else {
        if tree.lessFun(value, tree.node) == true {
            tree.left.Insert(value)
        } else {
            tree.right.Insert(value)
        }
    }
}
func compare(x interface{}, y interface{}) bool {
    if x.(int) < y.(int) {
        return true
    } else {
        return false
    }
}
func main() {
    tree := New(compare)
    tree.Insert(1)
    tree.Insert(2)
    tree.Insert(3)
    findTree := tree.Search(2)
    if findTree.node != 2 {
        fmt.Println("[Error] Search error")
    }
    fmt.Println(findTree.node)
    findNilTree := tree.Search(100)
    if findNilTree != nil {
        fmt.Println("[Error] 2. Search erro")
    }
    fmt.Println(findNilTree)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Heap Sort를 먼저 봐서 그런지 이해는 빨랐습니다.