PowerShellで2分探索木(Binary Search Tree)を作ってみる

2分探索木をPowerShellで作ってみました。

2分探索木の作成

PowerShellにはクラスが無いので、PSObjectを利用してノードを作成します。

#ノードオブジェクト作成メソッド
function create_node($leftNode,$rightNode,[int]$value){
	$obj = New-Object PSObject
	Add-Member -NotePropertyName 'Left' -NotePropertyValue $leftNode -InputObject $obj
	Add-Member -NotePropertyName 'Right' -NotePropertyValue $rightNode -InputObject $obj
	Add-Member -NotePropertyName 'Value' -NotePropertyValue $value -InputObject $obj
	return $obj
}

#新しいノードを既存ノードの配下に追加
function insert_node($node,[int]$value){
	if(!$node.Value)
	{
		$node = create_node $null $null $value
	}
        #今回は重複要素は無視します
	elseif ($node.Value -eq $value) {}
	elseif($node.Value -lt $value)
	{
		$node.Right = insert_node $node.Right $value
	}
        else
	{
		$node.Left = insert_node $node.Left $value
	}
	return $node
}

これらの関数を利用して2分探索木を作ります。

#木に入れる要素を配列として用意します
$text = '50,38,11,23,15,10,77,61,34,44,96,58,5,20,34,73,72,55,49,23,37,93,58,21,51,75,100,38'
$text = $text.split(',')

#配列を木に挿入していきます
foreach ($item in $text) {
	if(!$root)
	{
		#ルートノードを作成します
		$root = create_node $null $null $item
	}
	else
	{
		#ルートノードに要素を挿入していきます
		insert_node $root $item > $null
	}
}

これで$rootという2分探索木ができました。

2分探索木を利用する

いくつか2分探索木を利用する処理を書いてみました。

#引数の数値を持ったノードの存在を確認
function search_node($node,[int]$value)
{
	while ($node) 
	{
		if($node.Value -eq $value)
		{
			return $True
		}
		elseif($node.Value -lt $value)
		{
			$node = $node.Right
		}
		else
		{
			$node = $node.Left
		}
	}
	return $False
}

#ツリー内の最小値を検索
function search_min_value($node)
{
	while($node)
	{
		if(!$node.Left)
		{
			return $node.Value
		}
		else
		{
			$node = $node.Left
		}
	}
}

#ツリー内の最大値を検索
function search_max_value($node)
{
	while($node)
	{
		if(!$node.Right)
		{
			return $node.Value
		}
		else
		{
			$node = $node.Right
		}
	}
}

#ツリーの内容を出力
function dump_node($node)
{
	if($node)
	{
		Write-Host $node.Value
		dump_node $node.Right
		dump_node $node.Left
	}
}

早速使ってみた結果がこのような感じです。

#2分探索木の$rootから23を検索します
PS > search_node $root 23
True

#2分探索木の$rootから24を検索します
PS > search_node $root 24
False

#2分探索木の$rootの最小値を検索します
PS > search_min_value $root
5

#2分探索木の$rootの最大値を検索します
PS > search_max_value $root
100

#2分探索木の$rootの内容を出力します
PS > dump_node $root
50
77
96
100
93
61
73
75
72
58
55
51
38
44
49
11
23
34
37
15
20
21
10
5

本当は、2分探索木は削除処理が一番面倒くさいのですが、それは今度時間見つけたら書こうと思います。