이진 검색 트리 In Go

대학에서 BST를 만드는 법을 배운 지 오래되었습니다. BST를 다시 방문하고 싶은 마음이 들어서 이 게시물을 작성합니다. BST는 그렇게 무섭지 않습니다. 각 노드에 중복된 값이 없는 트리를 생성하기만 하면 덜 가치 있는 노드가 왼쪽으로 이동하고 나머지 노드는 오른쪽으로 이동하거나 그 반대의 경우도 마찬가지입니다. 이 게시물에서는 덜 가치 있는 정수 노드가 왼쪽으로 이동하는 Go 언어의 BST를 만들 것입니다. Go 언어 및 트리 데이터 구조에 대한 기본 지식이 있다고 가정합니다.

디렉토리 구조

$ tree
.
├── bst
│   ├── node.go
│   └── tree.go
├── go.mod
└── main.go

tree 명령을 사용하여 디렉토리 구조를 나열했습니다(말장난이 아님).

암호

node struct 파일 안에 먼저 node.go를 만들어 봅시다.

type node struct {
  value int
  left, right *node
}

func newNode(value int) *node {
  return &node{
    value: val,
    left: nil,
    right: nil,
  }
}

func (n *node) Value() int {
  return n.value
}

func (n *node) Left() *node {
  return n.left
}

func (n *node) Right() *node {
  return n.right
}

데이터 변경 가능성을 피하기 위해 user가 node struct를 직접 사용할 수 없도록 하고 getter functions 일부를 제공합니다.

그런 다음 binarySearchTree struct 파일 내부에 tree.go를 만들어 node의 사용법을 래핑합니다. pointer of node struct를 root로 저장하므로 트리의 루트를 추적할 수 있습니다.

type binarySearchTree struct {
  root *node
}

func New() *binarySearchTree {
  return &binarySearchTree{}
}

현재 코드를 사용하여 main function에서 이와 같은 BST를 생성할 수 있습니다.

func main() {
  tree := bst.New()
}

이제 트리에 insert , find , traverse 및 remove 와 같은 몇 가지 기능을 부여하려고 합니다. 먼저 insert부터 시작하겠습니다. 의사 코드는 다음과 같습니다.

If there's no node, then create a new node.
If a node with same value is already exists inside the tree, returns error.
If the value is greater than current node's value, then insert to the right.
If the value is less than current node's value, then insert to the left.

함수를 재귀적으로 만들고 트리 값을 직접 변경하지 않습니다. 따라서 오류가 발생한 경우 트리는 동일하게 유지됩니다.

func insertNode(node *node, val int) (*node, error) {
  // if there's no node, create one
  if node == nil {
    return newNode(val), nil
  }

  if node.value == val {
    // if there's duplicated node returns error
    return nil, ErrDuplicatedNode
  }

  if val > node.value {
    // if value is greater than current node's value, insert to the right
    right, err := insertNode(node.right, val)

    if err != nil {
      return nil, err
    }

    node.right = right
  } else if val < node.value {
    // if value is less than current node's value, insert to the left
    left, err := insertNode(node.left, val)

    if err != nil {
      return nil, err
    }

    node.left = left
  }

  return node, nil
}

binarySearchTree struct를 통해 함수를 사용자에게 노출해 보겠습니다.

func (tree *binarySearchTree) Insert(val int) error {
  // always start insert from the root
  root, err := insertNode(tree.root, val)

  if err != nil {
    return err
  }

  tree.root = root
  return nil
}

입력한 값이 올바른 위치에 있는지 확인하기 위해 먼저 traverse 함수를 만듭니다. 트리를 탐색하는 방법은 pre-order , in-order 및 post-order 3가지가 있습니다. 차이점은 다음과 같습니다.

# pre-order
1. print current value
2. go recursively to the left
3. go recursively to the right

# in-order
1. go recursively to the left
2. print current value
3. go recursively to the right

# post-order
1. go recursively to the left
2. go recursively to the right
3. print current value

쉽게 기억하려면 현재 값을 인쇄해야 할 때를 기억하십시오. if pre이면 먼저 인쇄하고 if post이면 끝에 인쇄하고 그렇지 않으면 중간에 인쇄하십시오. 우리는 in order traverse 를 만들 것입니다. 왜냐하면 재귀적으로 먼저 왼쪽으로 이동한 다음 값을 인쇄하기 때문입니다. 우리의 경우에는 from least valuable nodes to the greatest 를 인쇄할 것입니다.

func traverse(node *node) {
  // exit condition
  if node == nil {
    return
  }

  traverse(node.left)
  fmt.Println(node.value)
  traverse(node.right)
}

func (tree *binarySearchTree) Traverse() {
  // traverse from the root
  traverse(tree.root)
}

먼저 코드를 확인해 봅시다.

func main() {
  tree := bst.New()

  tree.Insert(23)
  tree.Insert(10)
  tree.Insert(15)
  tree.Insert(20)
  tree.Insert(2)
  tree.Insert(25)
  tree.Insert(50)

  tree.Traverse() // 2 10 15 20 23 25 50
}

이제 traverse 결과가 정렬되었으므로 find 함수로 이동하겠습니다. 특정 노드를 찾기 위해 전체 트리를 돌아다닐 필요 없이 BST가 노드 값을 확인하여 특정 노드로 라우팅할 수 있음을 알아야 합니다. insert 함수와 마찬가지로 찾고자 하는 노드 값이 현재 노드보다 작으면 왼쪽으로, 노드 값이 크면 오른쪽으로만 가면 됩니다.

func findNode(node *node, val int) *node {
  if node == nil {
    return nil
  }

  // if the node is found, return the node
  if node.value == val {
    return node
  }

  // if value is greater than current node's value, search recursively to the right
  if val > node.value {
    return findNode(node.right, val)
  }

  // if value is less than current node's value, search recursively to the left
  if val < node.value {
    return findNode(node.left, val)
  }

  return nil
}

func (tree *binarySearchTree) Find(val int) *node {
  // as always, search from the root
  return findNode(tree.root, val)
}

이제 주어진 값을 가진 노드가 있으면 지정된 노드를 반환하고 그렇지 않으면 nil을 반환합니다. 우리는 노드 속성을 캡슐화하고 사용자에게 Getter 기능만 남겨두기 때문에 데이터 변경 가능성에 대해 걱정할 필요가 없습니다.

이제 remove 함수로 이동하겠습니다. insert, find 함수와 마찬가지로 노드의 위치를 ​​먼저 찾은 다음 삭제를 해야 합니다. 트리에서 노드를 제거하는 세 가지 규칙이 있습니다.

If the node has no child, then Simply make it nil
If the node has 1 child, then move the child to the node position.
If the node has 2 children, then find the successor and move the successor to the node position.

노드의 후속 노드를 찾으려면 두 가지 방법이 있습니다.

Find the least valueable node from the right child of the node
OR
Find the greatest valueable node from the left child of the node

첫 번째 접근 방식인 find the least valuable node of the right child node를 사용하겠습니다. 현재 노드에서 가치가 가장 낮은 노드를 찾으려면 가장 왼쪽 노드로 이동하기만 하면 됩니다. 그리고 현재 노드의 가장 가치 있는 노드를 찾으려면 가장 오른쪽 노드로 이동하면 됩니다.

func least(node *node) *node {
  if node == nil {
    return nil
  }

  if node.left == nil {
    return node
  }

  return least(node.left)
}

func removeNode(node *node, val int) (*node, error) {
  if node == nil {
    return nil, ErrNodeNotFound
  }

  if val > node.value {
    right, err := removeNode(node.right, val)
    if err != nil {
      return nil, err
    }

    node.right = right
  } else if val < node.value {
    left, err := removeNode(node.left, val)
    if err != nil {
      return nil, err
    }

    node.left = left
  } else {
    if node.left != nil && node.right != nil {
      // has 2 children

      // find the successor
      successor := least(node.right)
      value := successor.value

      // remove the successor
      right, err := removeNode(node.right, value)
      if err != nil {
        return nil, err
      }
      node.right = right

      // copy the successor value to the current node
      node.value = value
    } else if node.left != nil || node.right != nil {
      // has 1 child
      // move the child position to the current node
      if node.left != nil {
        node = node.left
      } else {
        node = node.right
      }
    } else if node.left == nil && node.right == nil {
      // has no child
      // simply remove the node
      node = nil
    }
  }

  return node, nil
}

그게 다야, 여러분. 코드를 정리하면 이렇게 될 것입니다.

node.go

package bst

import (
  "errors"
  "fmt"
)

var (
  ErrDuplicatedNode error = errors.New("bst: found duplicated value on tree")
  ErrNodeNotFound   error = errors.New("bst: node not found")
)

type node struct {
  value       int
  left, right *node
}

func (n *node) Value() int {
  return n.value
}

func (n *node) Left() *node {
  return n.left
}

func (n *node) Right() *node {
  return n.right
}

func newNode(val int) *node {
  return &node{
    value: val,
    left:  nil,
    right: nil,
  }
}

func insertNode(node *node, val int) (*node, error) {
  // if there's no node, create one
  if node == nil {
    return newNode(val), nil
  }

  if node.value == val {
    // if there's duplicated node returns error
    return nil, ErrDuplicatedNode
  }

  if val > node.value {
    // if value is greater than current node's value, insert to the right
    right, err := insertNode(node.right, val)

    if err != nil {
      return nil, err
    }

    node.right = right
  } else if val < node.value {
    // if value is less than current node's value, insert to the left
    left, err := insertNode(node.left, val)

    if err != nil {
      return nil, err
    }

    node.left = left
  }

  return node, nil
}

func removeNode(node *node, val int) (*node, error) {
  if node == nil {
    return nil, ErrNodeNotFound
  }

  if val > node.value {
    right, err := removeNode(node.right, val)
    if err != nil {
      return nil, err
    }

    node.right = right
  } else if val < node.value {
    left, err := removeNode(node.left, val)
    if err != nil {
      return nil, err
    }

    node.left = left
  } else {
    if node.left != nil && node.right != nil {
      // has 2 children

      // find the successor
      successor := least(node.right)
      value := successor.value

      // remove the successor
      right, err := removeNode(node.right, value)
      if err != nil {
        return nil, err
      }
      node.right = right

      // copy the successor value to the current node
      node.value = value
    } else if node.left != nil || node.right != nil {
      // has 1 child
      // move the child position to the current node
      if node.left != nil {
        node = node.left
      } else {
        node = node.right
      }
    } else if node.left == nil && node.right == nil {
      // has no child
      // simply remove the node
      node = nil
    }
  }

  return node, nil
}

func findNode(node *node, val int) *node {
  if node == nil {
    return nil
  }

  // if the node is found, return the node
  if node.value == val {
    return node
  }

  // if value is greater than current node's value, search recursively to the right
  if val > node.value  {
    return findNode(node.right, val)
  }

  // if value is less than current node's value, search recursively to the left
  if val < node.value {
    return findNode(node.left, val)
  }

  return nil
}

func least(node *node) *node {
  if node == nil {
    return nil
  }

  if node.left == nil {
    return node
  }

  return least(node.left)
}

func traverse(node *node) {
  // exit condition
  if node == nil {
    return
  }

  traverse(node.left)
  fmt.Println(node.value)
  traverse(node.right)
}

트리.고

package bst

type binarySearchTree struct {
  root *node
}

func New() *binarySearchTree {
  return &binarySearchTree{}
}

func (tree *binarySearchTree) Insert(val int) error {
  // always start insert from the root
  root, err := insertNode(tree.root, val)

  if err != nil {
    return err
  }

  tree.root = root
  return nil
}

func (tree *binarySearchTree) Remove(val int) error {
  root, err := removeNode(tree.root, val)

  if err != nil {
    return err
  }

  tree.root = root
  return nil
}

func (tree *binarySearchTree) Find(val int) *node {
  // as always, search from the root
  return findNode(tree.root, val)
}

func (tree *binarySearchTree) Traverse() {
  // traverse from the root
  traverse(tree.root)
}

main.go

package main

import (
  "learn/bst"
)

func main() {
  tree := bst.New()

  tree.Insert(23)
  tree.Insert(10)
  tree.Insert(15)

  tree.Remove(10)

  tree.Insert(20)
  tree.Insert(2)
  tree.Insert(25)

  tree.Remove(25)
  tree.Remove(23)
  tree.Insert(50)

  tree.Traverse() // 2 15 20 50
}

읽어 주셔서 감사합니다.