Binary Search Tree in kotlin (sealed classとlinked listを使用した実装の比較）

# 目次
1. [目的](#目的)
1. [前提](#前提)
    1. Sealed Class
1. [Binary Search Treeの実装の比較](#binarysearchtree実装の比較)
    1. [要素の表現方法](#要素の表現方法)
    2. [要素の追加](#要素の追加)
    3. [要素の参照](#要素の参照) 
    4. [要素数と高さの計算](#要素数と高さの計算) <-- ここまで
    5. 最小（最大）要素の取得
    7. 要素の削除
    7. 要素の走査
    8. 木の回転

<a id="anchor1"></a>
# 目的
Binary Search Treeの2つの実装方法を比較する。
実装方法は以下の2つ

- Sealed classを用いた実装  
    - [joy of kotlin](https://www.manning.com/books/the-joy-of-kotlin)で紹介されている実装
- LinkedListを用いた実装 
    - [Algorithms, 4th Edition](https://algs4.cs.princeton.edu/home/)に載っている実装

<a id="anchor2"></a>
# 前提
## Sealed class
以下、kotlinの公式から引用。
> Sealed classes are used for representing restricted class hierarchies, 
when a value can have one of the types from a limited set, 
but cannot have any other type. 
[kotlin documentation](https://kotlinlang.org/docs/reference/sealed-classes.html)

sealedクラスとは、制限されたクラス構造を表すために使用される。
sealedクラス内に定義された型であれば値として保持できるが、
他の型は保持できない。

```kotlin
sealed class Example {

    internal class Example1() : Example() {}

    internal class Example2(): Example() {}

    companion object {
        operator fun invoke(): Example = Example1()
    }
}

// インスタンス
val e = Example()
```

2つのサブクラス`Example1`, `Example2`は、
sealed class `Example`を継承している。

この例では、sealed class `Example`は、
型`Example1`か`Example2`のいずれかのみを取りうる。

`Enum`クラスに似ているが、違いは以下の通り。

> They are, in a sense, an extension of enum classes: 
the set of values for an enum type is also restricted, 
but each enum constant exists only as a single instance, 
whereas a subclass of a sealed class can have multiple instances which can contain state.
[kotlin documentation](https://kotlinlang.org/docs/reference/sealed-classes.html)

sealedクラスは、ある種enumクラスの拡張。
（取りうる型が制限されているという点は同じ。）
異なるのは、enumはシングルインスタンスとして存在するが、
sealed classのサブクラスは、
状態を保持し複数のインスタンスとして存在する。

```kotlin
sealed class Example {

    internal class Example1(name: String) : Example() {}

    internal class Example2(): Example() {}

    companion object {
        operator fun invoke(name:String? = null): Example =
                if(name == null) Example2() else Example1(name)
    }
}

val e1 = Example("hi")
val e2 = Example("bye")
```

サブクラス`Example1`に引数`name`を追加した。
これにより、状態を持つようになる。
e1,e2に格納された`Example1`型のインスタンスはそれぞれ異なる。

<a id="anchor3"></a>
# BinarySearchTree実装の比較
BST（二分探索木）の詳細は、wikipediaを参照
[二分探索木](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8)

BSTは、木構造なので、親から子への参照が必要になる。
加えて、二分木なので、親は左部分木と右部分木の2つの子の参照を持つ必要がある。

また、要素間の制約として、
`「左の子孫の値 ≤ 親 ≤ 右の子孫の値」`がある。

左の部分木の値は、親の値以下となり、
右の部分木の値は、親の値より大きくなる。

<a id="anchor4"></a>
## 要素の表現方法

### LinkedListを使用した実装
BSTのアルゴリズムの実装は、
Javaで記載されているのもあり、
[Algorithms, 4th Edition](https://algs4.cs.princeton.edu/home/)を参考にした。

BSTを実装するクラスでは、
rootと呼ばれる木の頂上に位置する要素と、
それ以外の要素を管理する。

rootも含めた全ての要素の型は,
`Node<K,V>?`となる。
`Nullable`としているのは、要素がない場合を`null`として表現するため。

また、BSTでは、
`「左の子孫の値 ≤ 親 ≤ 右の子孫の値」`という
要素間の制約を担保するため、要素間での比較を行うことから、
要素のkeyの型`K`は`Comparable`を実装している型とする。

BSTクラスでは、頂上の要素`root`への参照のみを保持する。

```kotlin
class BST<K : Comparable<K>, V> {

        var root : Node<K,V>? = null

        data class Node<K,V>(
                var key:K,
                var value:V,
                // link to subtrees
                var left: Node<K,V>? = null,
                var right: Node<K,V>? = null,
                // # nodes in subtree rooted here
                var N: Int = 0,
                // height of the subtree rooted here
                var height: Int = 0
        )
}
```

`Node<K,V>`を見ると、
`Node<K,V>?`型の`left`、`right`の変数がある。
これらは、それぞれ左の子要素と右の子要素への参照である。
要素がない場合は`null`を使って表現する。

![linkedlist.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202689/75bb8a76-9191-dcb9-d4e3-a479357f7412.png)

図. Node Classによる木構造の表現


### Sealed Classを使用した場合
実装は、[joy of kotlin](https://www.manning.com/books/the-joy-of-kotlin)の10章を参照。

木構造をsealed class `Tree`を用いて実装する。
サブクラスは、`Empty`と`T`とする。

```kotlin
sealed class Tree<out A: Comparable<@UnsafeVariance A>> {
   
    internal object Empty : Tree<Nothing>() {

        override fun toString(): String = "E" 
    }

    internal class T<out A: Comparable<@UnsafeVariance A>>(
                           internal val left: Tree<A>,
                           internal val value: A,
                           internal val right: Tree<A>) : Tree<A>() {

        override fun toString(): String =
                    "(T $left $value $right)"
    }

    companion object {
            operator fun <A: Comparable<A>> invoke(): Tree<A> = Empty
    }
}
```

- Empty
    - 空のtreeを表す
    - 状態を持つ必要がないので、`object`を使用し、シングルトンオブジェクトとする。
    - `Nothing`は全ての型の子クラスとして機能
- T
    - 空ではないtreeを表す
    - 値valueを保持
    - 子となる左子要素と右要素をleft, rightとして保持
        - 子に要素があるかどうかは子の型で判断する

初期化の際は、型Emptyとなるようにしている。

<a id="anchor5"></a>
## 要素の追加
木に要素を追加する際は、
以下の制約を維持するように処理をする。

> 左の部分木の値は、親の値以下となり、
> 右の部分木の値は、親の値より大きくなるよう管理する必要がある

### LinkedListを使用した実装
要素の追加処理は、以下のインターフェースを実装する。

但し、引数のkeyがすでに木に存在している場合は、
引数のvalueで値を更新するものとする。

```kotlin
fun put(key: K, value: V)
```

木構造は、
「ノードと、そのノードが参照する左右の子要素」の集合であるため、
再帰処理と相性が良い。

この`put`メソッドも再帰処理を用いる。
以下のような処理の流れとなる。

- ノードが存在するか？
    - ノードが存在する場合、引数のkeyとノードのkeyを比較
        - 引数のkey < ノードのkey -> 左の子要素を走査 ①
        - 引数のkey > ノードのkey -> 右の子要素を走査 ②
        - 引数のkey == ノードのkey -> valueを更新 ③
    - ノードが存在しない場合、新しいノードを挿入する ④

```kotlin
private fun put(node: Node<K,V>?, key:K, value:V): Node<K,V> =
        node?.also {
            when {
                key < it.key -> it.left = put(it.left, key, value) // ①
                key > it.key -> it.right = put(it.right, key, value) // ②
                else -> it.value = value // ③
            }
        } ?: Node(key = key, value = value, N = 1) // ④
```

再帰処理が終わる条件（終端条件）は、③か④のいずれかとなる。
③は、木のなかにすでにkeyが存在している場合で、
引数のvalueで値を更新し、そのノードが戻り値となる。

一方で、④は、ノードが新たに作成される場合である。
起きうる条件は以下の2点である。
- 最初にノードが作られる場合
- 木の末端まで再帰処理が進んだ場合

最終的なpublicなputメソッドは以下の通り、
上述の再帰処理をrootから順に行う。

```kotlin
fun put(key: K, value: V) { root = put(root, key, value) }
```

### Sealed Classを使用した実装
[Joy of Kotlinのサンプルコード](https://github.com/pysaumont/fpinkotlin/blob/master/fpinkotlin-parent/fpinkotlin-trees-exercises/src/main/kotlin/com/fpinkotlin/trees/exercise02/Tree.kt)を参照。

LinkedListを使用した場合と同様、再帰処理を用いる。
再帰処理の終端条件についても同様であるが、表現方法が異なる。

特に、④の「ノードが新たに作成される」は、
Sealed Classを用いると以下のように`Empty`を用いて記述できる。

```kotlin
operator fun plus(element: @UnsafeVariance A): Tree3<A> =
        // thisは、Treeを指す
        when(this) {
            // 木が空か、木の末端の場合、新たにノードを作成
            Empty -> T(Empty, element, Empty)
            // 木が要素を持つ場合、引数keyとノードのkeyを比較
            is T -> when {
                element < value -> T(left + element, value, right)
                element > value -> T(left, value, right + element)
                else -> T(left, element, right)
            }
        }
```

`operator fun plus`を実装することで、
以下のように、`Tree`クラスに対し`+`演算子を使用し、
このメソッドを呼び出すことができる。

```kotlin
var t = Tree<Int>()
t += 3
t += 2
```

<a id="anchor6"></a>
## 要素の参照
次に、木に追加した要素を参照する方法について見ていく。
### LinkedListを使用した実装
LinkedListを用いた実装では、以下のインターフェースを実装する。

```kotlin
fun get(key:K): V?
```

[要素の追加](#anchor6)と同じ再帰処理を用いる。

```kotlin
private fun get(node:Node<K,V>?, key:K): Node<K,V>? =
            node?.let {
                when {
                    key < it.key -> get(it.left, key)
                    key > it.key -> get(it.right, key)
                    else -> it
                }
            } ?: null
```

終端条件は、 

- 検索対象のkeyを持つNodeにたどり着いた場合
- 木の末端にたどり着いた場合 (木が空の場合も含む）

こちらも、rootから順に再帰的に処理を行う。

```kotlin
fun get(key: K): V? = get(root,key)?.value ?: null
```

### Sealed Classを使用した実装
Sealed Classを用いた場合も同様、再帰的に処理を行う。

```kotlin
fun get(a: @UnsafeVariance A): Tree? = when(this) {
            Empty -> this
            is T -> when {
                a < value -> left.get(a)
                a > value -> right.get(a)
                else -> this
            }
        }
```

終端条件もLineked Listと同じで、表現方法が異なるのみである。

## 要素数と高さの計算
要素数とは、木のなかに含まれる要素の数を指し、
高さは、木の中の要素で最大の深さを指す。
それぞれnullの要素はカウントしない。

<img width="300" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202689/e952a802-ced1-24e4-8fcd-cce283bcbaf8.png">

### LinkedListを使用した実装
Nodeクラス再掲

```kotlin
data class Node<K,V>(
        var key:K,
        var value:V,
        // link to subtrees
        var left: Node<K,V>? = null,
        var right: Node<K,V>? = null,
        // # nodes in subtree rooted here
        var N: Int = 0,
        // height of the subtree rooted here
        var height: Int = 0
)
```

`Node.N`は、自身をrootとし、自らを含んだ配下の要素数を保持する。
`Node.height`は、自身をrootとし、自らを含んだ配下の要素内での高さを保持する。

要素数を取得するメソッド`size()`と
高さを取得するメソッド`hegiht()`を実装する。

```kotlin
fun size(): Int = size(root)
private fun size(node: Node<K,V>?): Int = node?.N ?: 0
```

```kotlin
fun height(): Int = root?.let { height(it) } ?: -1
private fun height(node: Node<K,V>?) : Int = node?.height ?: -1
```

これらのメソッドを正しく動作させるためには、
各ノードで管理している「配下の要素に関する要素数と高さ」を正しく維持し続ける必要がある。

現在、要素数や高さが変動するのは、
要素の追加処理のみなので、
`put`メソッドへ変更を加える。

`put`メソッド再掲

```kotlin
private fun put(node: Node<K,V>?, key:K, value:V): Node<K,V> =
        node?.also {
            when {
                key < it.key -> it.left = put(it.left, key, value) 
                key > it.key -> it.right = put(it.right, key, value) 
                else -> it.value = value 
            }
        } ?: Node(key = key, value = value, N = 1) 
```

要素を挿入する際に、`N=1`としている。
これは、新規挿入される要素は、必ず木の末端に位置し、
配下に自分以外の要素が存在しないためである。


末端に要素が新たに追加された場合、
その親要素に関しては、
自身（親要素）の配下の要素に関する値を更新する必要がある。
コードだと以下の部分にあたる。

```kotlin
key < it.key -> it.left = put(it.left, key, value) 
key > it.key -> it.right = put(it.right, key, value) 
```

そこで、値の更新処理を行うようにする。

```kotlin
it.N = size(it.left) + size(it.right) + 1
it.height = kotlin.math.max(height(it.left), height(it.right)) + 1
```

先ほど記載した
` size(node: Node<K,V>?): Int `、`height(node: Node<K,V>?) : Int `
メソッドにより、
任意のノードの要素数と高さが取得できるため、それらを使用する。

要素数の計算では、
配下の要素(`it.left`、`it.right`)と自分自身(1)を足すことで、値の更新を行う。

一方で、高さの計算では、
配下の要素(`it.left`、`it.right`)で、
より深い方の深さと自分自身が存在する階層分(1)足すことで、
高さの更新を行う。

### Sealed Classを使用した実装
Sealed Classを用いた実装では、
`Tree`クラスにabstract methodとして、`size()`, `height()`メソッドを宣言する。

```kotlin
abstract fun size(): Int
abstract fun height(): Int
```

Sealed Classでは、abstract methodとして宣言されたメソッドは、
サブクラスで必ず実装する必要がある。

そのため、サブクラス`Empty`、`T`でそれぞれ実装する。

サブクラス`Empty`は、
> 空のtreeを表す

という定義の関係上、要素も高さも存在しない。

```kotlin
internal object Empty : Tree<Nothing>() {
	override fun size(): Int = 0
	override fun height(): Int = -1
}
```

一方で、サブクラス`T`には、
要素が存在するため、要素数や高さを計算する必要がある。

```kotlin
internal class T<out A: Comparable<@kotlin.UnsafeVariance A>>(
                override val left: Tree<A>,
                override val value: A,
                override val right: Tree<A>) : Tree<A>() {
                
            	override fun size(): Int = 1 + left.size() + right.size()
            	override fun height(): Int = 1 + max(left.height(), right.height())
 }
```

要素数や高さの計算は、LinkedListを使用した実装と同様、
自分自身含め、配下の要素に対して、要素数や高さを計算する。

LinkedListを用いた実装では、
メソッドに計算対象のノードを渡していたが、
Sealed Classの場合は、
計算対象のノードをreceiverとして、
`size`、`height`メソッドを呼び出すことで実現できる。

```kotlin
var t = Tree<Int>()
t += 3
t += 2

// rootのサイズ(木全体の要素数)
t.size()
// rootの左要素のサイズ(rootの左部分木の要素数)
t.left.size()
```

# Reference
- [joy of kotlin](https://www.manning.com/books/the-joy-of-kotlin)
- [Algorithms, 4th Edition](https://algs4.cs.princeton.edu/home/)
- [Joy of Kotlinのサンプルコード](https://github.com/pysaumont/fpinkotlin)
- [Algorithms, 4th Editionのサンプルコード](https://github.com/kevin-wayne/algs4)