のバイナリ検索ツリー

大学でBSTを作ることを学んだので、ずっと.私はBSTのものを再訪したいと思うので、私はこのポストを作ります.BSTは怖いです.各ノードに値を重複させずにツリーを作成する必要があるだけで、より貴重なノードが左側に移動し、ノードの残りが右または逆に移動します.この記事では、整数の価値の少ないノードが左側に移動し、go言語でBSTを作ります.go languageとtreeデータ構造の基本的な知識を持っていると思います.

ディレクトリ構造

$ 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 . ITストアpointer of node struct としてroot それで、我々は木の根を追跡することができます.

type binarySearchTree struct {
  root *node
}

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

現在のコードでは、このようにBSTを作成できますmain function .

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

今、私たちは木にいくつかの機能性を与えますinsert , find , traverse , and 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
}

入力した値が正しい位置にあるかどうかを確認するには、まずトラバース関数を作成します.ツリーを横断する3つの方法があります.pre-order , in-order , and post-order . 以下は違いです.

# 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 次に最初に印刷するpost そして最後に印刷し、そうでなければ中央に印刷する.私達はgonna作る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)
}

指定された値を持つノードがあれば、指定したノードを返します.我々はノード属性をカプセル化して、ゲッター機能だけでユーザを残すので、データの変異性を心配する必要はありません.
さあ、へ移動しましょうremove 関数.まさにinsert and find 関数は、ノードの位置を最初に見つけ、削除する必要があります.ツリーからノードを削除する3つの規則があります.

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.

ノードの後継者を見つけるには2つの方法があります

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
}

それはすべて、人々です.私がコードを抑制するならば、それはこれのようです.

ノード。試み

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)
}

メイン.試み

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
}

お読みありがとうございます.