1. 概要

このチュートリアルでは、Kotlinプログラミング言語を使用してバイナリツリーの基本的な操作を実装します。

これと同じチュートリアルのJavaバージョンを自由に確認してください。

2. 意味

プログラミングでは、バイナリツリーは、すべてのノードに2つ以下の子ノードがあるツリーです。すべてのノードには、キーと呼ばれるデータが含まれています。

一般性を失うことなく、キーが単なる整数である場合に限定して考えてみましょう。

したがって、再帰データ型を定義できます。

class Node(
    var key: Int,
    var left: Node? = null,
    var right: Node? = null)

これには、値(整数値フィールド key )と、親と同じタイプの左右の子へのオプションの参照が含まれます。

リンクされた性質により、バイナリツリー全体をルートノードと呼ぶ1つのノードで記述できることがわかります。

ツリー構造にいくつかの制限を適用すると、物事はより興味深いものになります。 このチュートリアルでは、ツリーが順序付けられた二分木(二分探索木とも呼ばれます)であると想定しています。 これは、ノードが特定の順序で配置されていることを意味します。

次の条件はすべて、ツリーの不変の一部であると想定しています。

  1. ツリーに重複するキーは含まれていません
  2. すべてのノードで、そのキーは左側のサブツリーノードのキーよりも大きい
  3. すべてのノードで、そのキーは右側のサブツリーノードのキーよりも小さくなります

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. 挿入

ツリーでは重複キーが許可されていないため、新しい値を挿入するのは非常に簡単です。

  1. 値がすでに存在する場合、アクションは不要です
  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. トラバーサル

ノードにアクセスする方法にはさまざまな方法があります。 最も一般的なのは、深さ優先、幅優先、およびレベル優先の検索です。 ここでは、深さ優先探索のみを検討しますこれは、次のいずれかの種類になります。

  1.  事前注文(親ノード、左の子、右の子の順にアクセスします)
  2. 順番に(左の子、次に親ノード、次に右の子にアクセスします)
  3. 注文後(左の子、次に右の子、次に親ノードにアクセスします)

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利用できます。