読者です 読者をやめる 読者になる 読者になる

Panda Noir

JavaScript の限界を究めるブログです。

JavaScriptでAVL木の実装をしました

今、応用情報の勉強をしています。その中で平衡二分探索木が出てきました。応用情報を取ろうとしている人間です。平衡二分探索木のひとつやふたつ実装した経験がなければいけない、と思ったので実装してみました。

github.com

仕様

全体の仕様はこんな感じです。

  • new AVLTree(val) でvalを値に持つ葉ノードを生成
  • avl.insert(val) でvalという値を持つノードを適切な位置へ挿入する。必要があれば平衡になるよう回転処理を行う。
  • avl.delete(val) でvalという値を持つノードを削除する。必要があれば回転処理を行う。
  • avl.search(val) でvalという値を持つノードを返す。見つからなければnullを返す

実際のコードは上のGitHubリポジトリを参照ください。