このようなオブジェクト

Question

の配列を使用して作業する私は、同じオブジェクトタイプの子を含めることができるオブジェクトの配列を持っている：

var exampleArray = [ 
    { 
     alias: 'alias1', 
     children: [ 
      { 
       alias: 'child1' 
      }, 
      { 
       alias: 'child2', 
       children: [ 
        { 
         alias: 'child4' 
        }, 
        { 
         alias: 'child5' 
        } 
       ] 
      }, 
      { 
       alias: 'child3' 
      } 
     ] 
    }, 
    { 
     alias: 'alias2' 
    }, 
    { 
     alias: 'alias3', 
     children: [ 
      { 
       alias: 'child6' 
      }, 
      { 
       alias: 'child7' 
      } 
     ] 
    } 
]; 

ベースオブジェクトは、他のプロパティを持っていますが、彼らは、質問（sまで重要ではありません） 手元に。今のところ、ちょうどオブジェクトが可能と仮定することができます：

{ 
    alias: 'string', 
    children: [] 
} 

子供はオプションです。

私はこのようなオブジェクトでいくつかのものを管理するための最善の方法/最速の方法を探しています。私は、私が欲しいもののいくつかを行うには、いくつかの再帰的なメソッドを作成しましたが、私は、次の作業を行うことについて移動する良い方法があるかどうかを知りたい：

1. hasAlias（ARR、別名は） - 私が判断する必要がありますオブジェクト全体に、エイリアスを持つオブジェクトが含まれている場合

現在、私はこれを再帰的に行いますが、この配列が有限に大きくなる可能性があることを考えると、再帰的メソッドは最終的にスタック制限を打ちます。

2. getParent（arr、alias） - 指定されたエイリアスを持つ要素を含む親を取得できる必要があります。エイリアスが配列全体にユニークであるとすれば、同じエイリアスは2つありません。繰り返しますが、私はこれを再帰的に行いますが、これを行うためのより良い方法を探したいと思います。

3. deleteObject（arr、alias） - 私は現在この方法を達成する方法がわかりません。配列とエイリアスを渡して、そのオブジェクト（とそのすべての子）を指定の配列から削除する必要があります。私はこれを行う再帰的な方法を開始したが、代わりにここに投稿することをやめた。

私はNode.jsを使用しており、より高速な方法で利用できるようになっています。私はまだかなりJavaScriptに新しいので、このような大規模な配列を使ってやる方が良いかどうかはわかりません。

Answer 1

私は主な配列に多少違っているかもしれませんが、それを完全に組み込むのではなく、他の項目を参照するフラットな配列として保管してください。

var flat = [ 
    { 
     alias : "str1", 
     children : [ flat[1], flat[2] ], 
     parent : null 
    }, 

    { 
     alias : "str1", 
     children : [], 
     parent : flat[0]  
    }, 

    { 
     alias : "str1", 
     children : [], 
     parent : flat[0]  
    } 
] 

これは「linked list」アプローチのようなものです。リンクされたリストには長所と短所がありますが、すばやくすべての項目を繰り返し処理できます。

Answer 2

再帰をサポートしていないFORTRANの時代には、再帰のレベルをシミュレートするようにデータセットを変更することで同様の効果が達成されました。例えば、オブジェクト構造にこの原則を適用すると、その「エイリアス」（別の単語によって名前またはID）によってオブジェクトを検索する機能は、次のように再帰せずに書くことができます。短いもので

function findAlias(parent, alias) // parent object, alias value string 
{ function frame(parent) 
    { return {parent: parent, children: parent.children, 
     index: 0, length: parent.children.length}; 
    } 
    var stack, tos, child, children, i; 

    stack = []; 
    if(parent.children) 
     stack.push(frame(parent)); 

    search: 
    while(stack.length) 
    { tos = stack.pop(); // top of generation stack 
     children = tos.children; 
     for(i = tos.index; i < tos.length; ++i) 
     { child = children[i]; 
      if(child.alias == alias) 
      { return { parent: tos.parent, child: child, childIndex: i} 
      } 
      if(child.children) 
      { tos.index = i + 1; 
       stack.push(tos); // put it back 
       stack.push(frame(child)); 
       continue search; 
      } 
     } 
    } 
    return null; 
} 

は、作成して終わります再帰呼び出しを行う代わりに同じ関数でプッシュおよびポップされる小さなデータオブジェクトのスタック。上記の例では、オブジェクト値がparentとchildのオブジェクトが返されます。子値は、指定されたエイリアスプロパティを持つものであり、親オブジェクトは、子がchildren配列にあるオブジェクトです。

エイリアスが見つからない場合はnullを返し、hasAlias機能に使用できます。 nullを返さない場合は、getParent機能を実行します。ただし、ルートノードを作成する必要があります：

// create a rootnode 
var rootNode = { alias: "root", children: exampleArray}; 
var found = findAlias(rootNode, "alias3"); 
if(found) 
{ console.log("%s is a child of %s, childIndex = %s", 
     found.child.alias, found.parent.alias, found.childIndex); 
} 
else 
    console.log("not found"); 

---

を[編集：、戻りオブジェクトを検索するchildIndexにを追加し、テストコード例を更新し、結論を追加します。]

結論

ツリーウォークアプリケーションでサポートされている場合に再帰関数呼び出しを使用すると、自己文書化コードと保守性の点で意味があります。容積圧テストでサーバの負荷を軽減することに大きな利点があるが、健全な文書化が必要であることが示されていれば、再帰的ではない変形がそれを支払うかもしれない。

• ：かかわらず、内部コーディング、これまでに行われtreewalksの合計数を減らすことで、プログラム全体の効率化に貢献するかもしれない親、子、子インデックス値の詳細を持つオブジェクトを返しますツリー歩行機能の
  検索戻り値の正当性は、hasAlias関数の代わりに
• 検索からの戻りオブジェクトは、関数ごとにツリー検索を繰り返すことなく更新、削除または挿入することができます。

Answer 3

保証最速の方法は、インデックスからからそれとその子を取り除く意味するだろうあなたはエイリアスを削除するID索引

var index = {} 
(function build(parent) { 
    index[parent.alias] = parent; 
    (parent.children || []).forEach(item => { 
     item.parent = parent 
     build(item) 
    }) 
})(objectRoot) 


function hasAlias(alias) { return alias in index } 

function getAlias(alias) { return index[alias] } 

function getParent(alias) { return index[alias] && index[alias].parent} 

に対して見上げる

- an index for the aliases (thats actually a unique id) 
- have a parent backlink on each child item (if it has a parent) 

を持つことは明らかですインデックスにまだ残っている親。

function deleteAlias(alias) { 

    function deleteFromIndex(item) { 
     delete index[item.alias] 
     (item.children || []).forEach(deleteFromIndex) 
    } 
    var item = index[alias] 
    item.parent.children.splice(item.parent.children.indexOf(item)) 
    deleteFromIndex(item) 

}