(data-structure)データ構造(ツリー、ツリー)

資料構造木が木なのは、木のように生えているからです.△正確に言えば、木をひっくり返したようです.
簡単な例としてHTML構造があります.根から下に枝分かれする.最後のノードは
葉といいます.一番上が根、一番下が葉っぱなので、木を逆さまにしている様子が想像できます:-)
こちらです.非ルートノードと非リーフノードを内部ノードと呼びます.

ノードとノード間の接続をbranchまたはedgeと呼びます.出発点にはルートが必要です.
HTMLは木の構造を模倣しているため、類似性がある.
上図に示す添付ファイルから、ドキュメントから最後のテキストへのパスをパス(path)と呼びます.また,親ノードでは,子ノード間のedge数を「高さ」(height)と呼ぶ.例えば、上記の場合、文書ルートからテキスト「DOM Tree」までの高さは4である.(4つの矢印で計算しやすい)
木の中で注意しなければならないのは、木の底も木で、木の下にはずっと木があるので、再帰関数を使うことです.
実生活でもクリスマスツリーがよく使われています.対戦表や指揮システムなどの段階や階層がある場所では、必ず使用します.

バイナリツリー

重複データがないという仮定の下で、バイナリツリーはサイズを区別しやすい.したがって、一度ソートすると、必要なデータがすばやく見つかります.

バイナリツリーでは、最小の数字が一番左に、最大の数字が一番右のファミリーにあります.ツリーは,これまでの資料構造とコードの複雑さとは異なる階層である.ツリーにデータを配置または検索する場合、およびデータを削除する場合、ほとんどが再帰を使用します.非公開関数は資料構造において初めて用いられた.

var Tree = (function() {
  function Tree() {
    this.count = 0;
    this.root;
  }
  function Node(data) {
    this.data = data;
    this.left;
    this.right;
  }
  function _insert(root, node) {
    if(!root) return node;
    if(node.data < root.data) {
      root.left = _insert(root.left, node);
      return root;
    } else {
      root.right = _insert(root.right, node);
      return root;
    }
    return root;
  }
  Tree.prototype.add = function(data) {
    var node = new Node(data);
    if (this.count === 0) {
      this.root = node;
    } else {
      _insert(this.root, node);
    }
    return ++this.count;
  }
  function _get(data, node) {
    if (node) {
      if (data < node.data) {
        return _get(data, node.left);
      } else if (data > node.data) {
        return _get(data, node.right);
      } else {
        return node;
      }
    } else {
      return null;
    }
  }
  Tree.prototype.get = function(data) {
    if (this.root) {
      return _get(data, this.root);
    } else {
      return null;
    }
  };
  function _remove(root, data) {
    var newRoot, exchange, temp;
    if (!root) return false;
    if (data < root.data) {
      root.left = _remove(root.left, data);
    } else if (data > root.data) {
      root.right = _remove(root.right, data);
    } else {
      if(!root.left) {
        newRoot = root.right;
        // root 메모리 정리
        return newRoot;
      } else {
        exchage = root.left;
        while (exchange.right) exchange = exchange.right;
        temp = root.data;
        root.data = exchage.data;
        exchange.data = temp;
        root.left = _remove(root.left, exchange.data);
      }
    }
    return root;
  }
  Tree.prototype.remove = function(key) {
    var node = _remove(this.root, key);
    if (node) {
      this.root = node;
      this.count--;
      if (this.count === 0) this.root = null;
    }
    return true;
  };
  return true;
})();

var tree = new Tree();
tree.add(5); // 1
tree.add(3); // 2
tree.add(4); // 3
tree.add(2); // 4
tree.add(7); // 5
tree.add(6); // 6
tree.root.left.data; // 3
tree.root.left.left.data; // 2;
tree.root.left.right.data; // 4
tree;
tree.remove(3);
tree.root.left.data;

右側の左側に追加し、必要な場所が見つかるまで再帰的に完了します.消去したいデータを再帰的に検索して消去すればよいが、消去後はツリーがバイナリ検索ツリー条件を満たしていることを確認する必要がある.
そのため、削除する際には3つの要因を考慮する必要があります.

左サブノードがない場合

右サブノードがない場合

左、右の2つのサブノードは、時間

である.
**両方のサブノードが存在しない場合は1です.処理は左ノードがない場合と同じです.(ノードの挿入と迂回)

左側のサブノード(数値10の場合)がない場合は、右側のノードをドラッグして消去されたスペースを埋めることができます.右側のサブノード(数値14)がない場合は、左側のノードをドラッグすることができます.
子供は両側(数字8の場合)で少し違う戦略が必要です.まず、削除する8つのノードと8の左側のサブノードのうち最大のノード(7)を交換します.これにより、バイナリ検索ツリー条件が維持されます.

今は7が根になり、8が7位になりました.次に、3本のツリーから8を削除します.現在のノード8には2つのサブノードがないため、1となる.左側のサブノードがない場合の条件に相当します.

8を削除すると、新しいバイナリ検索ツリーが完了します.従来の検索ツリーの削除機能は,ノードの位置や個数に応じて分岐処理を行う必要があるため,より複雑である.

ソース

データ構造(hip、heap)0秒ブログ