Cara paling efisien untuk menghasilkan semua turunan dari semua simpul di pohon

Saya mencari algoritma yang paling efisien untuk mengambil pohon (disimpan sebagai daftar tepi; ATAU sebagai daftar pemetaan dari simpul induk ke daftar simpul anak); dan menghasilkan, untuk SETIAP simpul, daftar semua node turun darinya (tingkat daun dan tingkat non-daun).

Implementasinya harus melalui loop bukan dari resusi, karena skala; dan idealnya adalah O (N).

Pertanyaan SO ini mencakup solusi standar yang cukup jelas untuk menemukan jawaban untuk SATU simpul di pohon. Tetapi jelas, mengulangi bahwa algoritma pada setiap simpul pohon sangat tidak efisien (dari atas kepala saya, O (NlogN) ke O (N ^ 2)).

Akar pohon dikenal. Pohon itu benar-benar bentuk sewenang-wenang (misalnya bukan N-nary, tidak seimbang dengan cara apa pun, bentuk atau bentuk, bukan kedalaman seragam) - beberapa node memiliki 1-2 anak, beberapa memiliki 30K anak.

Pada level praktis (walaupun seharusnya tidak mempengaruhi algoritma) pohon memiliki ~ 100K-200K node.

Jika Anda benar-benar ingin MENGHASILKAN setiap daftar sebagai salinan yang berbeda, Anda tidak dapat berharap untuk mencapai ruang yang lebih baik daripada n ^ 2 dalam kasus terburuk. Jika Anda hanya perlu ACCESS untuk setiap daftar:

Saya akan melakukan traversal berurutan dari pohon mulai dari root:

http://en.wikipedia.org/wiki/Tree_traversal

Kemudian untuk setiap simpul di pohon menyimpan jumlah minimum pesanan dan maksimum urutan dalam subtree (ini mudah dipelihara melalui rekursi - dan Anda dapat mensimulasikannya dengan tumpukan jika Anda mau).

Sekarang Anda meletakkan semua node dalam array A dengan panjang n di mana simpul dengan nomor in-order i berada di posisi i. Kemudian ketika Anda perlu menemukan daftar untuk simpul X, Anda melihat dalam A [X.min, X.max] - perhatikan bahwa interval ini akan mencakup simpul X, yang juga dapat dengan mudah diperbaiki.

Semua ini dicapai dalam O (n) waktu dan membutuhkan O (n) ruang.

Saya harap ini membantu.

Bagian yang tidak efisien bukanlah melintasi pohon, tetapi membangun daftar node. Tampaknya masuk akal untuk membuat daftar seperti ini:

descendants[node] = []
for child in node.childs:
    descendants[node].push(child)
    for d in descendants[child]:
        descendants[node].push(d)

Karena setiap simpul turunan disalin ke dalam daftar setiap induk, kami berakhir dengan kompleksitas rata-rata O (n log n) untuk pohon seimbang, dan kasus terburuk O (n²) terburuk untuk pohon degenerasi yang benar-benar terkait dengan daftar.

Kami dapat beralih ke O (n) atau O (1) tergantung pada apakah Anda perlu melakukan pengaturan apa pun jika kami menggunakan trik menghitung daftar dengan malas. Asumsikan kita memiliki child_iterator(node)yang memberi kita anak-anak dari simpul itu. Kami kemudian dapat dengan sepele mendefinisikan descendant_iterator(node)seperti ini:

def descendant_iterator(node):
  for child in child_iterator(node):
    yield from descendant_iterator(child)
  yield node

Solusi non-rekursif jauh lebih terlibat, karena aliran kontrol iterator rumit (coroutine!). Saya akan memperbarui jawaban ini hari ini juga.

Karena traversal suatu pohon adalah O (n) dan iterasi pada daftar juga linier, trik ini benar-benar mengurangi biaya sampai tetap dibayar. Sebagai contoh, mencetak daftar keturunan untuk setiap node memiliki kompleksitas kasus terburuk O (n²): Iterasi atas semua node adalah O (n) dan juga iterasi dari setiap node, apakah mereka disimpan dalam daftar atau dihitung ad hoc .

Tentu saja, ini tidak akan berfungsi jika Anda membutuhkan koleksi aktual untuk dikerjakan.

Algoritme singkat ini harus melakukannya, Lihat kode public void TestTreeNodeChildrenListing()

Algoritma ini benar-benar melewati node pohon secara berurutan, dan menjaga daftar orang tua dari node saat ini. Sesuai kebutuhan Anda, simpul saat ini adalah anak dari masing-masing simpul orangtua yang ditambahkan ke masing-masing simpul sebagai anak.

Hasil akhir disimpan dalam kamus.

    [TestFixture]
    public class TreeNodeChildrenListing
    {
        private TreeNode _root;

        [SetUp]
        public void SetUp()
        {
            _root = new TreeNode("root");
            int rootCount = 0;
            for (int i = 0; i < 2; i++)
            {
                int iCount = 0;
                var iNode = new TreeNode("i:" + i);
                _root.Children.Add(iNode);
                rootCount++;
                for (int j = 0; j < 2; j++)
                {
                    int jCount = 0;
                    var jNode = new TreeNode(iNode.Value + "_j:" + j);
                    iCount++;
                    rootCount++;
                    iNode.Children.Add(jNode);
                    for (int k = 0; k < 2; k++)
                    {
                        var kNode = new TreeNode(jNode.Value + "_k:" + k);
                        jNode.Children.Add(kNode);
                        iCount++;
                        rootCount++;
                        jCount++;

                    }
                    jNode.Value += " ChildCount:" + jCount;
                }
                iNode.Value += " ChildCount:" + iCount;
            }
            _root.Value += " ChildCount:" + rootCount;
        }

        [Test]
        public void TestTreeNodeChildrenListing()
        {
            var iteration = new Stack<TreeNode>();
            var parents = new List<TreeNode>();
            var dic = new Dictionary<TreeNode, IList<TreeNode>>();

            TreeNode node = _root;
            while (node != null)
            {
                if (node.Children.Count > 0)
                {
                    if (!dic.ContainsKey(node))
                        dic.Add(node,new List<TreeNode>());

                    parents.Add(node);
                    foreach (var child in node.Children)
                    {
                        foreach (var parent in parents)
                        {
                            dic[parent].Add(child);
                        }
                        iteration.Push(child);
                    }
                }

                if (iteration.Count > 0)
                    node = iteration.Pop();
                else
                    node = null;

                bool removeParents = true;
                while (removeParents)
                {
                    var lastParent = parents[parents.Count - 1];
                    if (!lastParent.Children.Contains(node)
                        && node != _root && lastParent != _root)
                    {
                        parents.Remove(lastParent);
                    }
                    else
                    {
                        removeParents = false;
                    }
                }
            }
        }
    }

    internal class TreeNode
    {
        private IList<TreeNode> _children;
        public string Value { get; set; }

        public TreeNode(string value)
        {
            _children = new List<TreeNode>();
            Value = value;
        }

        public IList<TreeNode> Children
        {
            get { return _children; }
        }
    }
}

Biasanya, Anda hanya akan menggunakan pendekatan rekursif, karena memungkinkan Anda untuk mengubah urutan eksekusi Anda sehingga Anda dapat menghitung jumlah daun mulai dari daun ke atas. Karena, Anda harus menggunakan hasil dari panggilan rekursif Anda untuk memperbarui node saat ini, akan diperlukan upaya khusus untuk mendapatkan versi rekursif ekor. Jika Anda tidak melakukan upaya itu, maka tentu saja, pendekatan ini hanya akan meledak tumpukan Anda untuk pohon besar.

Mengingat bahwa kami menyadari ide utamanya adalah untuk mendapatkan urutan putaran mulai dari daun dan kembali ke akar, ide alami yang muncul di pikiran adalah untuk melakukan semacam topologi pada pohon. Urutan node yang dihasilkan dapat dilalui secara linier untuk menjumlahkan jumlah daun (dengan asumsi Anda dapat memverifikasi suatu node adalah leaf in O(1)). Kompleksitas waktu keseluruhan dari jenis topologi adalah O(|V|+|E|).

Saya berasumsi bahwa Anda Nadalah jumlah node, yang |V|biasanya (dari nomenklatur DAG). Ukuran Edi sisi lain sangat tergantung pada arity pohon Anda. Sebagai contoh, pohon biner memiliki paling banyak 2 tepi per node, oleh karena itu O(|E|) = O(2*|V|) = O(|V|)dalam hal ini, yang akan menghasilkan O(|V|)algoritma keseluruhan . Perhatikan bahwa karena struktur keseluruhan pohon, Anda tidak dapat memiliki sesuatu seperti O(|E|) = O(|V|^2). Faktanya, karena setiap node memiliki orangtua yang unik, Anda dapat memiliki paling banyak satu sisi untuk dihitung per node ketika Anda hanya mempertimbangkan hubungan orangtua, jadi untuk pohon kami memiliki jaminan itu O(|E|) = O(|V|). Oleh karena itu, algoritma di atas selalu linier dalam ukuran pohon.