Kotlinでのバイナリツリーの実装
1. 概要
このチュートリアルでは、Kotlinプログラミング言語を使用してバイナリツリーの基本的な操作を実装します。
これと同じチュートリアルのJavaバージョンを自由に確認してください。
2. 意味
プログラミングでは、バイナリツリーは、すべてのノードに2つ以下の子ノードがあるツリーです。すべてのノードには、キーと呼ばれるデータが含まれています。
一般性を失うことなく、キーが単なる整数である場合に限定して考えてみましょう。
したがって、再帰データ型を定義できます。
class Node(
var key: Int,
var left: Node? = null,
var right: Node? = null)
これには、値(整数値フィールド key )と、親と同じタイプの左右の子へのオプションの参照が含まれます。
リンクされた性質により、バイナリツリー全体をルートノードと呼ぶ1つのノードで記述できることがわかります。
ツリー構造にいくつかの制限を適用すると、物事はより興味深いものになります。 このチュートリアルでは、ツリーが順序付けられた二分木(二分探索木とも呼ばれます)であると想定しています。 これは、ノードが特定の順序で配置されていることを意味します。
次の条件はすべて、ツリーの不変の一部であると想定しています。
- ツリーに重複するキーは含まれていません
- すべてのノードで、そのキーは左側のサブツリーノードのキーよりも大きい
- すべてのノードで、そのキーは右側のサブツリーノードのキーよりも小さくなります
3. 基本操作
最も一般的な操作には、次のものがあります。
- 指定された値を持つノードの検索
- 新しい値の挿入
- 既存の値の削除
- そして、特定の順序でノードを取得します
3.1. 調べる
ツリーが順序付けられると、ルックアッププロセスが非常に効率的になります:検索する値が現在のノードの値と等しい場合、ルックアップは終了します。 検索する値が現在のノードの値よりも大きい場合は、左側のサブツリーを破棄して、右側のサブツリーのみを検討することができます。
fun find(value: Int): Node? = when {
this.value > value -> left?.findByValue(value)
this.value < value -> right?.findByValue(value)
else -> this
}
ツリーのキーの中に値が存在しない可能性があるため、ルックアップの結果がnull値を返す可能性があることに注意してください。
switch-case ステートメントのJavaアナログであるが、はるかに強力で柔軟性のあるKotlinキーワードwhenをどのように使用したかに注意してください。
3.2. 挿入
ツリーでは重複キーが許可されていないため、新しい値を挿入するのは非常に簡単です。
- 値がすでに存在する場合、アクションは不要です
- 値が存在しない場合は、左または右の「スロット」が空いているノードに挿入されます。
そのため、値に対応する必要があるサブツリーを検索するために、ツリーを再帰的に解析する場合があります。 値が現在のノードのキーよりも小さい場合、左側のサブツリーが存在する場合はそれを選択します。 存在しない場合は、値を挿入する場所が見つかったことを意味します。これは、現在のノードの左の子です。
同様に、値が現在のノードのキーより大きい場合。 残っている唯一の可能性は、値が現在のノードキーと等しい場合です。これは、値がツリーにすでに存在し、何もしないことを意味します。
fun insert(value: Int) {
if (value > this.key) {
if (this.right == null) {
this.right = Node(value)
} else {
this.right.insert(value)
}
} else if (value < this.key) {
if (this.left == null) {
this.left = Node(value)
} else {
this.left.insert(value)
}
}
3.3. 除去
まず、指定された値を含むノードを特定する必要があります。 ルックアッププロセスと同様に、ノードを検索するためにツリーをスキャンし、検索されたノードの親への参照を維持します。
fun delete(value: Int) {
when {
value > key -> scan(value, this.right, this)
value < key -> scan(value, this.left, this)
else -> removeNode(this, null)
}
}
二分木からノードを削除するときに直面する可能性のある3つの異なるケースがあります。 null以外の子ノードの数に基づいて分類します。
両方の子ノードがnullですこのケースは処理が非常に簡単で、ノードの削除に失敗する可能性があるのはこのケースだけです。ノードがルートの場合、削除することはできません。 それ以外の場合は、親の対応する子をnullに設定するだけで十分です。
このアプローチの実装は次のようになります。
private fun removeNoChildNode(node: Node, parent: Node?) {
if (parent == null) {
throw IllegalStateException("Can not remove the root node without child nodes")
}
if (node == parent.left) {
parent.left = null
} else if (node == parent.right) {
parent.right = null
}
}
一方の子はnullで、もう一方はnullではありませんこの場合、削除するノードに唯一の子ノードを「シフト」するだけで十分なので、常に成功する必要があります。
このケースを簡単に実装できます。
private fun removeSingleChildNode(parent: Node, child: Node) {
parent.key = child.key
parent.left = child.left
parent.right = child.right
}
両方の子ノードがnullではありません削除するノードを置き換えるノードを見つける必要があるため、このケースはより複雑です。 この「置換」ノードを見つける1つの方法は、左側のサブツリーで最大のキーを持つノードを選択することです(確かに存在します)。 もう1つの方法は、対称的な方法です。右側のサブツリーで、キーが最小のノードを選択する必要があります(これも存在します)。 ここでは、最初のものを選択します。
置換ノードが見つかったら、その親からの参照を「リセット」する必要があります。 これは、置換ノードを検索するときに、その親も返す必要があることを意味します。
private fun removeTwoChildNode(node: Node) {
val leftChild = node.left!!
leftChild.right?.let {
val maxParent = findParentOfMaxChild(leftChild)
maxParent.right?.let {
node.key = it.key
maxParent.right = null
} ?: throw IllegalStateException("Node with max child must have the right child!")
} ?: run {
node.key = leftChild.key
node.left = leftChild.left
}
}
3.4. トラバーサル
ノードにアクセスする方法にはさまざまな方法があります。
- 事前注文(親ノード、左の子、右の子の順にアクセスします)
- 順番に(左の子、次に親ノード、次に右の子にアクセスします)
- 注文後(左の子、次に右の子、次に親ノードにアクセスします)
Kotlinでは、これらすべての種類のトラバーサルを非常に簡単な方法で実行できます。 たとえば、先行予約トラバーサルの場合、次のようになります。
fun visit(): Array<Int> {
val a = left?.visit() ?: emptyArray()
val b = right?.visit() ?: emptyArray()
return a + arrayOf(key) + b
}
Kotlinで「+」演算子を使用して配列を連結する方法に注意してください。 この実装は効率的な実装とはほど遠いものです。末尾再帰ではなく、より深いツリーでは、スタックオーバーフローの例外が発生する可能性があります。
4. 結論
このチュートリアルでは、Kotlin言語を使用してバイナリ検索ツリーの基本的な操作を構築および実装する方法を検討しました。 Javaには存在せず、役立つ可能性のあるKotlinコンストラクトをいくつか示しました。
いつものように、上記のアルゴリズムの完全な実装は、Githubで利用できます。