[바미] Go - BTS가 아닌 BST에 대해 알아보자!

안녕하세요. 오늘은 이진트리에 대해 알아보고자 합니다.

위의 그림 같이 자식이 두 개 밖에 없는 것을 이진트리라고 합니다. 

 

기존의 트리는

Type TreeNode struct {
  childs []*TreeNode
}

형태로 슬라이스 형태로 가졌는데 이진트리는 자식이 두 개 밖에 없기 때문에 슬라이스 형태로 가질 필요가 없습니다.

Type TreeNode Struct {
  left *TreeNode
  right *TreeNode
}

이 부분을 코딩해보죠.

package dataStruct

type BinaryTreeNode struct {
    Val   int
    left  *BinaryTreeNode
    right *BinaryTreeNode
}

이 부분을 먼저 짚고 가는 이유는 다음에 설명할 BST(Binary Search Tree) 때문입니다.

BST는 이진 검색 트리가 Binary Tree로 되어 있기 때문입니다.

1~10까지 숫자가 있고, 5가 root라 가정할 때

 

left쪽은 root보다 작은 수, right쪽은 root보다 큰 수가 정렬 되어 있다. 이 규칙은 root에만 적용 되는게 아니라

모든 Node에 적용된다. 보면 2를 보면 2의 왼쪽값은 2보다 작은 수, 오른쪽은 2보다 큰 수가 있으며 8 또한 마찬가지 입니다.

left <= Parent <= right

이런 규칙을 띄는 것을 알 수 있습니다.

이런 것을 이진 검색 트리 라고 할 수 있습니다.

이게 중요한 이유는 어떤 트리에서 어떤 값을 찾는다고 가정 했을 때

가령 위의 트리로 6이라는 값이 존재하는지 알아 볼 때 모든 트리를 다 검색하는 DFS나 BFS방법을 사용한 순회를 해야 합니다.

 

근데 BTS를 만들었다 가정했을 때

위 트리 안에 6이 있는지 찾으려 한다면 모든 노드를 다 가볼 필요가 없습니다.

먼저 현재 노드인 5와 비교를 먼저 합니다. 6은 root 노드인 5보다 크므로 6이라는 값이 있다면 오른쪽에 있을 것이며 왼쪽에 있는 트리는 볼 필요가 없습니다.

그 다음이 8인데 8은 6보다 작으므로 만약에 6이 존재한다면 왼쪽에 있을 것이므로 오른쪽 부분은 검사 대상에 제외 됩니다.

그 후 7이 나오는데 7은 6보다 작으므로 또 왼쪽으로 가게 되어 6을 찾게 됩니다.

 

그래서 이진검색트리는 어떤 값을 찾을 때 반절씩 버리며 가기 때문에 훨씬 빠르게 탐색 할 수 있습니다.

 

이제 속도를 살펴보죠.
일반적인 트리를 보았을 때 어떤 값이 있는지 찾으려면 모든 노드를 돌아보아야 한다고 했는데

 

여기서 6을 찾으려면 모든걸 다 거쳐 가봐야 합니다. 물론 운이 좋게 중간에 발견할 수 도 있겠지만 최악의 경우로 6이 아래와 같이 트리 안에 없다고 가정해보죠.

이 트리 안에 없다 쳐도 없는지 확인하려면 모든 노드들을 다 거쳐서 진짜 없는지 확인해야 합니다.
그렇다 했을 때 노드의 개수가 7개 이므로 반복문을 7번 돌아야 합니다.

항목의 개수만큼 반복문이 돌아야 하기 때문에 이 때는 O(N)의 속도를 갖게 됩니다.

그런데 이진 검색 트리를 살펴보자.

위의 트리에서 6을 찾는다 했을 때 3번 만에 6을 찾을 수 있습니다.

위의 노드의 개수가 7개인데 3번만에 찾았기 때문에 O(N)은 아닙니다.

그러면 6이 없을 때는 어떨까요?

5보다 크므로 오른쪽에 가고, 8보다 작으므로 왼쪽으로 가고, 7보다 작으므로 다음 노드로 갈 때 다음 노드가 없으므로 6이 없는 것을 알 수 있습니다. 이 때도 마찬가지로 3번에 알아냅니다.

그래서 이 때는 O(log2^N)이 됩니다.

 

아래의 화면은 그래프를 그리는 사이트에서 O(N)의 속도와 O(log2^N)의 속도를 측정해보기 위해 그린 그래프인데

첫번째 그래프(빨간색)은 y(갯수)가 늘어나면 x(시간)도 늘어나는 O(N)의 형태의 그래프이고, 두번째 그래프(파란색)은 O(log2^N)형태의 그래프인데 이를 통해 O(log2^N)은 O(N)에 비해 훨씬 빠르다는 것을 알 수 있습니다.

이제 이 부분을 코딩해보죠!

binaryTree.go

package dataStruct

import "fmt"

type BinaryTreeNode struct {
    Val   int
    left  *BinaryTreeNode
    right *BinaryTreeNode
}

type BinaryTree struct { // 1
    Root *BinaryTreeNode
}

func NewBinaryTree(v int) *BinaryTree { // 3
    tree := &BinaryTree{}
    tree.Root = &BinaryTreeNode{Val: v}
    return tree
}

func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode { // 2
    if n.Val < v { // 1
        if n.left == nil { // 2
            n.left = &BinaryTreeNode{Val: v}
            return n.left
        } else {
            return n.left.AddNode(v) // 3
        }
    } else {
        if n.right == nil { // 4 
            n.right = &BinaryTreeNode{Val: v} // 5
            return n.right
        } else { // 6
            return n.right.AddNode(v)
        }
    }
}

1 : tree Type을 만들어 줍니다.
2 : BinaryTreeNode의 AddNode라는 함수를 만들어서 Value를 넣도록 합니다.
2-1 : 현재 노드의 값보다 새로들어온 노드의 값이 작을 때 -> 왼쪽에 붙여 줍니다.
2-2 : 왼쪽에 있는 노드가 없으면 왼쪽에 추가해 줍니다.
2-3 : 왼쪽에 노드가 있는 경우 왼쪽 노드에 다시 AddNode()함수를 재귀호출해서 그 결과를 반환해 줍니다.
2-4 : 현재 노드의 값보다 새로들어온 노드의 값이 작지 않으면 -> 오른쪽에 붙여 줍니다.
2-5 : 마찬가지로 오른쪽에 값이 없으면 오른쪽에 추가해 줍니다.
2-6 : 오른쪽 노드가 있으면 오른쪽 노드에 AddNode()함수를 재귀호출해서 그 결과를 반환해 줍니다.

3 : Tree를 새로 만드는 함수. 처음 시작값을 받고, 새로 만들어진 BinaryTree를 반환시켜 줍니다.

이제 main.go로 넘어와서

main.go

package main

import (
    "./dataStruct"
)

func main() {
    tree := dataStruct.NewBinaryTree(5) // 1
    tree.Root.AddNode(3) // 2
    tree.Root.AddNode(2)
    tree.Root.AddNode(4)
    tree.Root.AddNode(8)
    tree.Root.AddNode(7)
    tree.Root.AddNode(6)
    tree.Root.AddNode(10)
    tree.Root.AddNode(9)

    tree.Print() // 3
}

1 : 처음 RootNode가 5인 BinaryTree를 생성한 뒤
2 : 값을 넣어 줍니다.
3 : 출력하는 함수가 있다고 가정하고 호출한 뒤

binaryTree.go에서 만들어보죠!

 

binaryTree.go

func (t *BinaryTree) Print() { // 1
    q := []*BinaryTreeNode{} // 2
    q = append(q, t.Root) // 3
    currentDepth := 0

    for len(q) > 0 { // 4
        var first depthNode // 1
        first, q = q[0], q[1:] // 2
    }
}

1 : 출력을 위한 Print함수를 생성해 줍니다.
이 때 BFS를 사용해서 출력을 할 것입니다.
2 : BFS는 큐(Queue)를 사용하므로 먼저 큐를 생성해 줍니다.
3 : 큐에 Push 합니다. 
4 : 큐가 비어있지 않았으면 for문을 돕니다. 
4-1 : 첫번째 노드를 저장할 변수를 선언 합니다. 
4-2 : 첫번째 노드와 큐를 갱신시켜 줍니다. 

출력 값을 보게 되면

출력이 뭔가 이상하게 되어 있는 것을 확인 할 수 있죠.

이 부분은 binaryTree.go에서 add할 때 first는 큐의 첫번째 값이고, q값은 큐를 첫번째의 값을 뺀 값을 넣어주어야 하므로 두번째 부터 넣어 줍니다.

 

그 다음 현재 노드를 집어넣어야 하는데 현재 나온 노드가 몇번째 층에 나온 노드인지 알기 위해서 코드를 수정해 줍니다.

binaryTree.go

type depthNode struct { // 1
    depth int
    node  *BinaryTreeNode
}

func (t *BinaryTree) Print() { // 2
    q := []depthNode{} // 1
    q = append(q, depthNode{depth: 0, node: t.Root}) // 2
    currentDepth := 0 // 3

    for len(q) > 0 {
        var first depthNode
        first, q = q[0], q[1:]

        if first.depth != currentDepth { // 4
            fmt.Println() // 5
            currentDepth = first.depth
        }
        fmt.Print(first.node.Val, " ") // 6

        if first.node.left != nil { // 7
            q = append(q, depthNode{depth: currentDepth + 1, node: first.node.left})
        }
        if first.node.right != nil { // 8
            q = append(q, depthNode{depth: currentDepth + 1, node: first.node.right})
        }
    }
}

1 : 깊이와 노드를 같이 가지고 있는 struct를 만들어 줍니다.
2-1 : 그리고 이 struct를 가지는 슬라이스를 만들어주고,
2-2 : Push할 때 처음의 depth는 0, node는 Rootnode를 넣어 줍니다.
2-3 : 현재 Depth를 표시하는 변수 입니다.
2-4 : first와 현재 depth가 다르면
2-5 : 한 줄을 띄워주고, currentDepth를 first.depth로 바꾸어주고,
2-6 : 값을 출력시켜 줍니다.
2-7 : left가 있다면 큐의 맨 뒤에 집어 넣어 줍니다.

큐에 집어 넣을 때 depth는 현재 depth의 1 더한 값(자식 노드니까)을 넣어주고, node는 first.node.left를 넣어주고,
2-8 : right가 있다면
큐에 집어 넣을 때 depth는 현재 depth의 1 더한 값(자식 노드니까)을 넣어주고, node는 first.node.right를 넣어줍니다.

func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode {
 // 현재 값이 새로 들어온 값 보다 작으면 
    if n.Val < v {
        if n.left == nil {
            n.left = &BinaryTreeNode{Val: v}
            return n.left
        } else {
            return n.left.AddNode(v)
        }
    } else {
        if n.right == nil {
            n.right = &BinaryTreeNode{Val: v}
            return n.right
        } else {
            return n.right.AddNode(v)
        }
    }
}

이 부분에서 문제가 생긴건데 현재 값이 새로 들어온 값 보다 작을 때 오른쪽에 넣어야 되는데 왼쪽에 넣었습니다.

그래서 현재값이 더 큰 경우, 새로 들어온 값이 작은경우에 왼쪽에 넣을 수 있도록 아래와 같이 바꾸어 줍니다.

func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode {
 // 현재 값이 새로 들어온 값 보다 작으면 
    if n.Val > v {
        if n.left == nil {
            n.left = &BinaryTreeNode{Val: v}
            return n.left
        } else {
            return n.left.AddNode(v)
        }
    } else {
        if n.right == nil {
            n.right = &BinaryTreeNode{Val: v}
            return n.right
        } else {
            return n.right.AddNode(v)
        }
    }
}

그러면 아래와 같이 정상적으로 바뀐 것을 알 수 있습니다.

이번에는 실제로 검색하는 것을 만들어보죠!

main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    tree := dataStruct.NewBinaryTree(5)
    tree.Root.AddNode(3)
    tree.Root.AddNode(2)
    tree.Root.AddNode(4)
    tree.Root.AddNode(8)
    tree.Root.AddNode(7)
    tree.Root.AddNode(6)
    tree.Root.AddNode(10)
    tree.Root.AddNode(9)

    tree.Print()

    if tree.Search(6) {
        fmt.Println("found 6")
    } else {
        fmt.Println("Not found 6")
    }
}

main 함수에 이렇게 추가해주고, 트리 안에 6을 찾도록 해보죠!

그 후 binaryTree.go로 와서 Search함수를 추가해 줍니다!

func (t *BinaryTree) Search(v int) bool { // 1
    return t.Root.Search(v)
}

func (n *BinaryTreeNode) Search(v int) bool { // 2
    if n.Val == v { // 3
        return true
    } else if n.Val > v { // 4
        if n.left != nil {
            return n.left.Search(v)
        }
        return false // 5
    } else {
        if n.right != nil { // 6
            return n.right.Search(v)
        }
        return false // 7
    }
}

1 : Binary Tree의 함수입니다. 찾아야 되는 값 v를 받고, 반환값으로 bool형으로 합니다.

그리고 tree의 Root의 Search라는 함수를 호출 하도록 해줍니다.

2 : 그런데 Root에 Search라는 함수가 없기 때문에 만들어 줍니다.

이번에는 BinaryTreeNode의 Search함수를 만들어 줍니다.

3 : 내가 찾아야 되는 값과 현재 노드와의 값이 같은 경우 True를 return 시켜주고,
4 : 같지 않고, 내 값이 찾아야 되는 값보다 큰 경우 왼쪽에 있을 가능성이 높으므로 왼쪽 노드에서 Search하도록 해주고,
5 : 없는 경우인데 없다는 얘기는 나보다 작은 수가 없다는 의미 이므로 false를 return 시켜 줍니다.
6 : 오른쪽 노드가 있으면 오른쪽에 찾아보고,
7 : 오른쪽에도 없으면 나보다 큰 값이 없는 것이므로 이 경우도 없는 수가 되어 false를 return 시켜 줍니다.

 

이렇게 Search 함수가 만들어졌고, 제대로 찾는지 확인해보죠!

이번에는 찾았는지 여부만 반환하는게 아니라 몇번만에 찾았는지도 반환시켜보죠!

main.go

func main() {
    tree := dataStruct.NewBinaryTree(5)
    tree.Root.AddNode(3)
    tree.Root.AddNode(2)
    tree.Root.AddNode(4)
    tree.Root.AddNode(8)
    tree.Root.AddNode(7)
    tree.Root.AddNode(6)
    tree.Root.AddNode(10)
    tree.Root.AddNode(9)

    tree.Print()

    if found, cnt := tree.Search(6); found { // 1
        fmt.Println("found 6")
    } else {
        fmt.Println("Not found 6")
    }
}

1 : 이 부분을 초기문이라고 해서 Search()를 먼저 실행하고, 그 결과를 found와 cnt에 대입하는 것이고, found가 true인 경우 fmt.Println("found 6")를 출력시킨다는 의미 입니다.

 

그 후 binaryTree.go로 와서 수정시켜보죠!

func (t *BinaryTree) Search(v int) (bool, int) {
    return t.Root.Search(v, 1)
}

func (n *BinaryTreeNode) Search(v int, cnt int) (bool, int) {
    if n.Val == v {
        return true, cnt
    } else if n.Val > v {
        if n.left != nil {
            return n.left.Search(v, cnt+1)
        }
        return false, cnt
    } else {
        if n.right != nil {
            return n.right.Search(v, cnt+1)
        }
        return false, cnt
    }
}

이렇게 BinaryTree의 Search엔 초기값이기 때문에 cnt를 1 넣어주어 반환 하도록 하고, BinaryTreeNode의 Search엔 cnt를 입력받아 bool과 cnt를 return하도록 수정해 줍니다.

 

이제 main.go로 넘어와 cnt도 출력할 수 있게 수정해준 뒤 실행시켜 줍니다.

func main() {
    tree := dataStruct.NewBinaryTree(5)
    tree.Root.AddNode(3)
    tree.Root.AddNode(2)
    tree.Root.AddNode(4)
    tree.Root.AddNode(8)
    tree.Root.AddNode(7)
    tree.Root.AddNode(6)
    tree.Root.AddNode(10)
    tree.Root.AddNode(9)

    tree.Print()

    if found, cnt := tree.Search(6); found {
        fmt.Println("found 6 cnt : ", cnt)
    } else {
        fmt.Println("Not found 6 cnt : ", cnt)
    }
}

이번에는 없는 숫자를 찾아보죠.

func main() {
    tree := dataStruct.NewBinaryTree(5)
    tree.Root.AddNode(3)
    tree.Root.AddNode(2)
    tree.Root.AddNode(4)
    tree.Root.AddNode(8)
    tree.Root.AddNode(7)
    tree.Root.AddNode(6)
    tree.Root.AddNode(10)
    tree.Root.AddNode(9)

    tree.Print()

    if found, cnt := tree.Search(6); found {
        fmt.Println("found 6 cnt : ", cnt)
    } else {
        fmt.Println("Not found 6 cnt : ", cnt)
    }

    if found, cnt := tree.Search(12); found {
        fmt.Println("found 12 cnt : ", cnt)
    } else {
        fmt.Println("Not found 12 cnt : ", cnt)
    }
}

정상적으로 출력되는 것을 알 수 있습니다.

이진검색트리를 사용하는 이유는 검색을 빨리하기 위해서 입니다.

여기서의 검색은 많은 용도로 사용합니다. 예를 들면 회원가입 시 ID를 입력할 때 ID를 DataBase에 저장해야 하는데 이걸 저장할 때
ID의 가 ABCD라고 할 때 문자열을 비교하는건 까다롭기 때문에 문자열을 HASH처리해서 숫자로 만들거나 회원가입 순서로 번호를 지정할 수 있는데, 그 번호를 이진트리 같은 곳에 넣고 그 아이디에 해당하는 값이 있는지 확인하는데 이 때 처음부터 끝까지 찾는거 보단 빠르기 때문에 이진트리 검색을 사용합니다.

최종 코드

main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    tree := dataStruct.NewBinaryTree(5)
    tree.Root.AddNode(3)
    tree.Root.AddNode(2)
    tree.Root.AddNode(4)
    tree.Root.AddNode(8)
    tree.Root.AddNode(7)
    tree.Root.AddNode(6)
    tree.Root.AddNode(10)
    tree.Root.AddNode(9)

    tree.Print()
    fmt.Println()

    if found, cnt := tree.Search(6); found {
        fmt.Println("found 6 cnt : ", cnt)
    } else {
        fmt.Println("Not found 6 cnt : ", cnt)
    }

    if found, cnt := tree.Search(12); found {
        fmt.Println("found 12 cnt : ", cnt)
    } else {
        fmt.Println("Not found 12 cnt : ", cnt)
    }
}

binaryTree.go

package dataStruct

import "fmt"

type BinaryTreeNode struct {
    Val   int
    left  *BinaryTreeNode
    right *BinaryTreeNode
}

type BinaryTree struct {
    Root *BinaryTreeNode
}

func NewBinaryTree(v int) *BinaryTree {
    tree := &BinaryTree{}
    tree.Root = &BinaryTreeNode{Val: v}
    return tree
}

func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode {
    if n.Val > v {
        if n.left == nil {
            n.left = &BinaryTreeNode{Val: v}
            return n.left
        } else {
            return n.left.AddNode(v)
        }
    } else {
        if n.right == nil {
            n.right = &BinaryTreeNode{Val: v}
            return n.right
        } else {
            return n.right.AddNode(v)
        }
    }
}

type depthNode struct {
    depth int
    node  *BinaryTreeNode
}

func (t *BinaryTree) Print() {
    q := []depthNode{}
    q = append(q, depthNode{depth: 0, node: t.Root})
    currentDepth := 0

    for len(q) > 0 {
        var first depthNode
        first, q = q[0], q[1:]

        if first.depth != currentDepth {
            fmt.Println()
            currentDepth = first.depth
        }
        fmt.Print(first.node.Val, " ")

        if first.node.left != nil {
            q = append(q, depthNode{depth: currentDepth + 1, node: first.node.left})
        }
        if first.node.right != nil {
            q = append(q, depthNode{depth: currentDepth + 1, node: first.node.right})
        }
    }
}

func (t *BinaryTree) Search(v int) (bool, int) {
    return t.Root.Search(v, 1)
}

func (n *BinaryTreeNode) Search(v int, cnt int) (bool, int) {
    if n.Val == v {
        return true, cnt
    } else if n.Val > v {
        if n.left != nil {
            return n.left.Search(v, cnt+1)
        }
        return false, cnt
    } else {
        if n.right != nil {
            return n.right.Search(v, cnt+1)
        }
        return false, cnt
    }
}