Zenn
Open2

Go言語勉強メモメモ

Go
つっきーつっきー

-二分木の実装

type Node struct {
    Key int
    Left *Node
    Right *Node
}

func NewNode(k int) *Node {
  return &Node{
     Key : k,
  }
}

・二分木は再帰的なデータ構造なので、ポインタを使って定義する

*Node としてポインタを使用する主な理由は以下の通りです：

  1. メモリの効率: ノードが他のノードへの参照を保持している場合、ポインタを使用するとメモリ使用量が削減されます。特に、ノードの実体を持つ代わりにノードへの参照を保持すると、必要なメモリが大幅に削減される場合があります。

  2. 動的な変更: ノードを変更したり、新しいノードを追加・削除する場合、ポインタを使って操作すると変更が容易になります。ポインタを使わない場合、ノード全体のコピーが発生し、効率が悪くなります。

  3. 再帰的なデータ構造: 二分木のような再帰的なデータ構造において、ノードが同じ型の他のノードへの参照を持っている必要があります。Go言語の場合、再帰的なデータ構造を定義するには、必ずポインタを使用する必要があります。つまり、ノードが自分自身の型（Node）を直接持つことはできず、ノードのポインタ（*Node）を持つ必要があります。

  4. nilの使用: ポインタを使用することで、子ノードが存在しない場合や、ツリーが空の場合など、特定の状況をnilで表現することができます。

これらの理由から、二分木のようなデータ構造を実装する際には、ノードの定義にポインタを使用するのが一般的です。

つっきーつっきー

挿入と探索

func (n *Node) Insert(key int) {
    if n == nil {
        return
    } else if key < n.Key {
        if n.Left == nil {
            n.Left = NewNode(key)
        } else {
            n.Left.Insert(key)
        }
    } else {
        if n.Right == nil {
            n.Right = NewNode(key)
        } else {
            n.Right.Insert(key)
        }
    }
}
func (n *Node) Search(key int) bool {
    if n == nil {
        return false
    } else if key < n.Key {
        return n.Left.Search(key)
    } else if key > n.Key {
        return n.Right.Search(key)
    }

    return true
}