TypeScript で二分探索木

令和を無事迎えることができたので、なんとなく。

```typescript
class BST<T> {
  public v: T | undefined;
  public left: BST<T> | undefined;
  public right: BST<T> | undefined;

  constructor(init_value?: T) {
    this.v = init_value;
  }

  // 要素の表示
  public toList(): T[] {
    if (this.v === undefined) {
      return [];
    } else {
      if (this.left !== undefined && this.right !== undefined) {
        return [...this.left.toList(), this.v, ...this.right.toList()];
      } else if (this.left !== undefined) {
        return [...this.left.toList(), this.v];
      } else if (this.right !== undefined) {
        return [this.v, ...this.right.toList()];
      } else {
        return [this.v];
      }
    }
  }

  // 構造の表示
  public showStructure(): string {
    if (this.v === undefined) {
      return "";
    } else {
      if (this.left !== undefined && this.right !== undefined) {
        return `BST { value: ${this.v} left: ${this.left.showStructure()} right: ${this.right.showStructure()} }`;
      } else if (this.left !== undefined) {
        return `BST { value: ${this.v} left: ${this.left.showStructure()} }`;
      } else if (this.right !== undefined) {
        return `BST { value: ${this.v} right: ${this.right.showStructure()} }`;
      } else {
        return `BST { value: ${this.v} }`;
      }
    }
  }

  // 要素の追加
  public insert(w: T): void {
    if (this.v === undefined) {
      this.v = w;
    } else {
      if (w >= this.v) {
        if (this.right === undefined) {
          this.right = new BST<T>(w);
        } else {
          this.right.insert(w);
        }
      } else {
        if (this.left === undefined) {
          this.left = new BST<T>(w);
        } else {
          this.left.insert(w);
        }
      }
    }
  }

  // 要素の削除
  public remove(w: T): void {
    if (this.v !== undefined) {
      if (w > this.v) {
        if (this.right !== undefined) {
          this.right.remove(w);
        } 
      } else if (w < this.v) {
        if (this.left !== undefined) {
          this.left.remove(w);
        }
      } else {
        if (this.left === undefined) {
          if (this.right === undefined) {
            this.v = undefined;
          } else {
            this.v = this.right.v;
            this.right = undefined;
          }
        } else {
          if (this.right === undefined) {
            this.v = this.left.v;
            this.left = undefined;            
          } else {
            const data: [T | undefined, BST<T> | undefined] = this.get_minimum_and_the_rest(this.right);
            if (data[0] !== undefined) {
              this.v = data[0];
              this.right = data[1];
            }
          }
        }
      }
    }
  }

  private get_minimum_and_the_rest(tree: BST<T>): [T | undefined, BST<T> | undefined] {
    if (tree.v !== undefined) {
      if (tree.left !== undefined) {
        const data: [T | undefined, BST<T> | undefined] = this.get_minimum_and_the_rest(tree.left);
        tree.left = data[1];
        return [data[0], tree];
      } else {
        return [tree.v, tree.right];
      }
    } else {
      return [undefined, undefined];
    }
  }
}
```

書いてて一番の鬼門になるのは、やはり、左右両方の子を持った場合の要素の削除ですが、Cで昔書いた時のイメージよりは思ったより綺麗にいけるな、という印象でした。
ただ、要素の削除全般に関して、Cだと malloc した領域を free で解放できるわけですが、この実装では単に値に undefined を代入しているだけなので、メモリ効率の悪い実装になります。


## Usage

```typescript
const tree = new BST<number>();
console.log(tree.toList());
// []
tree.insert(3);
tree.insert(1);
tree.insert(10);
tree.insert(6);
tree.insert(12);
tree.insert(4);
tree.insert(8);
tree.insert(11);
tree.insert(7);
tree.insert(9);
console.log(tree.toList());
// [ 1, 3, 4, 6, 7, 8, 9, 10, 11, 12 ]
console.log(tree.showStructure());
// BST { value: 3 left: BST { value: 1 } right: BST { value: 10 left: BST { value: 6 left: BST { value: 4 } right: BST { value: 8 left: BST { value: 7 } right: BST { value: 9 } } } right: BST { value: 12 left: BST { value: 11 } } } }
tree.remove(3);
console.log(tree.toList());
// [ 1, 4, 6, 7, 8, 9, 10, 11, 12 ]
console.log(tree.showStructure());
// BST { value: 4 left: BST { value: 1 } right: BST { value: 10 left: BST { value: 6 right: BST { value: 8 left: BST { value: 7 } right: BST { value: 9 } } } right: BST { value: 12 left: BST { value: 11 } } } }
tree.remove(4);
console.log(tree.toList());
// [ 1, 6, 7, 8, 9, 10, 11, 12 ]
console.log(tree.showStructure());
// BST { value: 6 left: BST { value: 1 } right: BST { value: 10 left: BST { value: 8 left: BST { value: 7 } right: BST { value: 9 } } right: BST { value: 12 left: BST { value: 11 } } } }
tree.remove(6);
console.log(tree.toList());
// [ 1, 7, 8, 9, 10, 11, 12 ]
console.log(tree.showStructure());
// BST { value: 7 left: BST { value: 1 } right: BST { value: 10 left: BST { value: 8 right: BST { value: 9 } } right: BST { value: 12 left: BST { value: 11 } } } }
tree.remove(8);
console.log(tree.toList());
// [ 1, 7, 9, 10, 11, 12 ]
console.log(tree.showStructure());
// BST { value: 7 left: BST { value: 1 } right: BST { value: 10 left: BST { value: 9 } right: BST { value: 12 left: BST { value: 11 } } } }
```