0

Go ポインター レシーバーの仕組みについて教えてください。

以下に、説明に役立つバイナリ検索ツリーの例を示します。

package main

import "fmt"

type Node struct {
  key         int
  left, right *Node
}

func NewNode(key int) *Node {
  return &Node{key, nil, nil}
}

type BST struct {
  root *Node
}

func NewBinarySearchTree() *BST {
  return &BST{nil}
}

func (t *BST) Insert(key int) {
  if t.root == nil {
    t.root = NewNode(key)
    return
  }
  var node = t.root
  for {
    if key < node.key {
      if node.left == nil {
        node.left = NewNode(key)
        return
      } else {
        node = node.left
      }
    } else {
      if node.right == nil {
        node.right = NewNode(key)
        return
      } else {
        node = node.right
      }
    }
  }
}

func inorder(node *Node) {
  if node == nil {
    return
  }
  inorder(node.left)
  fmt.Print(node.key, " ")
  inorder(node.right)
}

func main() {
  tree := NewBinarySearchTree()
  tree.Insert(3)
  tree.Insert(1)
  tree.Insert(2)
  tree.Insert(4)
  inorder(tree.root) // 1 2 3 4
}

しかし、これを書いた後、挿入関数を次のように単純化できると考えました。

func (t *BST) Insert2(key int) {
  var node *Node
  node = t.root
  for node != nil {
    if key < node.key {
      node = node.left
    } else {
      node = node.right
    }
  }
  node = NewNode(key)
}

ただし、この方法ではツリーは更新されません。私の考えは...

  • 最初の挿入では、ルート ノードは nil になります。
  • したがって、t.root を参照するローカル変数ノードも nil になります。
  • したがって、for ループはスキップされます。
  • node = NewNode(key)と同じ効果がありますt.root = NewNode(key)

私の Insert2 メソッドはどこで間違っていますか? 微調整できる方法はありますか？

4

2 に答える 2