JavaScript を使用して二分探索木を実装する方法

var ノード = {
  値: 125,
  左: null、
  右: null
};

関数 BinarySearchTree() {
  this._root = null;
}

バイナリサーチツリー.プロトタイプ = {

  //コンストラクタを復元する
  コンストラクタ: BinarySearchTree、

  追加: 関数 (値) {
  },

  含む: 関数(値){
  },

  削除: 関数(値){
  },

  サイズ: 関数(){
  },

  toArray: 関数(){
  },

  toString: 関数(){
  }

};

バイナリサーチツリー.プロトタイプ = {

  //さらにコード

  含む: 関数(値){
    var found = false、
      現在の = this._root

    //検索するノードがあることを確認する
    while(!found && current){

      //値が現在のノードより小さい場合は左へ進む
      （値<現在の値）の場合{
        現在の = 現在の.left;

      //値が現在のノードより大きい場合は右に進みます
      } それ以外の場合 (値 > 現在の値){
        現在の = 現在の.right;

      //値が等しい、見つかりました!
      } それ以外 {
        見つかりました = true;
      }
    }

    //ノードが見つかった場合のみ続行します
    戻り値が見つかりました。
  },

  //さらにコード

};

バイナリサーチツリー.プロトタイプ = {

  //さらにコード

  追加: 関数(値){
    //新しいアイテムオブジェクトを作成し、データを配置します
    var ノード = {
        値: 値、
        左: null、
        右: null
      },

      //構造を走査するために使用される
      現在;

    //特別なケース: ツリーにはまだアイテムがありません
    if (this._root === null){
      this._root = ノード;
    } それ以外 {
      現在の = this._root;

      while(true){

        //新しい値がこのノードの値より小さい場合は左に進みます
        （値<現在の値）の場合{

          // 残っていない場合は、新しいノードはそこに属します
          (current.left === null)の場合{
            現在の左ノード;
            壊す;
          } それ以外 {
            現在の = 現在の.left;
          }

        //新しい値がこのノードの値より大きい場合は右に進みます
        } それ以外の場合 (値 > 現在の値){

          // 権利がない場合、新しいノードはそこに属します
          (current.right === null)の場合{
            現在のノードの現在の位置。
            壊す;
          } それ以外 {
            現在の = 現在の.right;
          }   

        //新しい値が現在の値と等しい場合は無視します
        } それ以外 {
          壊す;
        }
      }
    }
  },

  //さらにコード

};

バイナリサーチツリー.プロトタイプ = {

  //さらにコード

  トラバース: 関数(プロセス){

    //ヘルパー関数
    関数 inOrder(ノード){
      if (ノード){

        //左のサブツリーを走査する
        （node.left !== null）の場合{
          ノードの左端に順序を入れます。
        }      

        //このノードのプロセスメソッドを呼び出す
        プロセスを呼び出す(これ、ノード);

        //右のサブツリーをトラバースする
        （node.right !== null）の場合{
          ノードの右端に順序を入れます。
        }
      }
    }

    //ルートから開始
    inOrder(this._root);
  },

  //さらにコード

};

バイナリサーチツリー.プロトタイプ = {

  //さらにコード

  サイズ: 関数(){
    var 長さ = 0;

    this.traverse(function(node){
      長さ++;
    });

    長さを返します。
  },

  toArray: 関数(){
    var 結果 = [];

    this.traverse(function(node){
      結果をプッシュします(ノードの値)。
    });

    結果を返します。
  },

  toString: 関数(){
    this.toArray().toString() を返します。
  },

  //さらにコード

};

バイナリサーチツリー.プロトタイプ = {

  //ここにさらにコード

  削除: 関数(値){

    var found = false、
      親 = null、
      現在の = this._root、
      子の数、
      交換、
      置き換え親;

    //検索するノードがあることを確認する
    while(!found && current){

      //値が現在のノードより小さい場合は左へ進む
      （値<現在の値）の場合{
        親 = 現在;
        現在の = 現在の.left;

      //値が現在のノードより大きい場合は右に進みます
      } それ以外の場合 (値 > 現在の値){
        親 = 現在;
        現在の = 現在の.right;

      //値が等しい、見つかりました!
      } それ以外 {
        見つかりました = true;
      }
    }

    //ノードが見つかった場合のみ続行します
    （見つかった場合）{
      //続く
    }

  },
  //ここにさらにコード

};

バイナリサーチツリー.プロトタイプ = {

  //ここにさらにコード

  削除: 関数(値){

    var found = false、
      親 = null、
      現在の = this._root、
      子の数、
      交換、
      置き換え親;

    //ノードを見つける（スペースの関係で削除）

    //ノードが見つかった場合のみ続行します
    （見つかった場合）{

      //子供の数を計算する
      子カウント = (current.left !== null ? 1 : 0) + 
             (current.right !== null ? 1 : 0);

      //特別なケース: 値はルートにあります
      (現在の値 === this._root) の場合{
        スイッチ(子の数){

          //子要素はなし、ルート要素のみ削除
          ケース0:
            this._root = null;
            壊す;

          // 子が 1 つある場合、そのうちの 1 つをルートとして使用します
          ケース1:
            this._root = (current.right === null ? 
                   現在の左:現在の右);
            壊す;

          // 子供が2人、仕事はほとんどない
          ケース2:

            //やるべきこと

          //デフォルトなし

        }    

      //非ルート値
      } それ以外 {

        スイッチ (childCount) {

          //子はないので、親から削除するだけです
          ケース0:
            //現在の値がその 
            //親の左ポインタをnullにする
            (現在の値 < 親の値) の場合{
              親.left = null;

            //現在の値がその
            //親の右ポインタをnullにする
            } それ以外 {
              親.right = null;
            }
            壊す;

          // 子が 1 つある場合は、親に再割り当てするだけです
          ケース1:
            //現在の値がその 
            //親の左ポインタをリセットする
            (現在の値 < 親の値) の場合{
              parent.left = (current.left === null ? 
                      現在の右:現在の左);

            //現在の値がその 
            //親の右ポインタをリセットする
            } それ以外 {
              parent.right = (current.left === null ? 
                      現在の右:現在の左);
            }
            壊す;  

          // 2 つの子、少し複雑
          ケース2:

            //やるべきこと     

          //デフォルトなし

        }

      }

    }

  },

  //ここにさらにコード

};

バイナリサーチツリー.プロトタイプ = {

  //ここにさらにコード

  削除: 関数(値){

    var found = false、
      親 = null、
      現在の = this._root、
      子の数、
      交換、
      置き換え親;

    //ノードを見つける（スペースの関係で削除）

    //ノードが見つかった場合のみ続行します
    （見つかった場合）{

      //子供の数を計算する
      子カウント = (current.left !== null ? 1 : 0) + 
             (current.right !== null ? 1 : 0);

      //特別なケース: 値はルートにあります
      (現在の値 === this._root) の場合{
        スイッチ(子の数){

          //スペース節約のため他のケースは削除

          // 子供が2人、仕事はほとんどない
          ケース2:

            //新しいルートは古いルートの左の子になります
            //... 多分
            置き換え = this._root.left;

            // 最も右の葉ノードを見つけます 
            //本当の新しいルート
            (replacement.right !== null){
              置き換え親 = 置き換え;
              置き換え = 置き換え.right;
            }

            //左の最初のノードではない
            （置換親！== null）の場合{

              //新しいルートを 
              //前の位置
              置き換え親.right = 置き換え.left;

              //新しいルートに古いものをすべて渡す 
              //ルートの子
              replacement.right = this._root.right;
              replacement.left = this._root.left;
            } それ以外 {

              //子を割り当てるだけ
              replacement.right = this._root.right;
            }

            //正式に新しいルートを割り当てる
            this._root = 置換;

          //デフォルトなし

        }    

      //非ルート値
      } それ以外 {

        スイッチ (childCount) {

          //スペース節約のため他のケースは削除

          // 2 つの子、少し複雑
          ケース2:

            //新しいトラバーサルのためにポインタをリセットする
            置き換え = current.left;
            置換親 = 現在の;

            //一番右のノードを見つける
            while(replacement.right !== null){
              置き換え親 = 置き換え;
              置き換え = 置き換え.right;
            }

            置き換え親.right = 置き換え.left;

            // 置換に子を割り当てる
            置き換え後の右辺を現在の右辺とする。
            置き換え後の左辺を現在の左辺とする。

            // 置換物を適切な場所に配置する
            (現在の値 < 親の値) の場合{
              親.left = 置き換え;
            } それ以外 {
              親.right = 置き換え;
            }     

          //デフォルトなし

        }

      }

    }

  },

  //ここにさらにコード

};