從理論上講，我可以對具有共享記憶體的樹使用什麼資料結構？

現實世界的問題

我有一片樹林。就像兩萬棵樹。這片森林占用了太多的記憶體。但是這些樹是相似的——你可以找到一組樹（大約 200 棵樹），這樣它們就有一個相當大的公共子樹（百分之幾十）。

理論

所以知道：

樹是相似的，即它們共享一個共同的連接子圖，包括根（不一定包括葉子——但可能）。

是否存在任何允許有效儲存該資訊的資料結構？創建結構後，我只對閱讀感興趣。

它不一定是 .NET 的解決方案，我可以從頭開始編寫程式碼，我只需要這個想法 :D 但是當然，如果 .NET 中有一些鮮為人知的結構可以實現這一點，我會很高興知道。

我有一種感覺，這種共享記憶體的東西可能與不可變結構有關，根據定義，這些結構應該共享記憶體……

不幸的是，我的樹不是二叉搜尋樹。他們可以有任意數量的孩子。

閱讀

至於閱讀，很簡單。我總是從根導航到葉子。就像在任何 JSON 或 XML 中一樣，給定一個值的確切路徑。

相似性的性質

包括兩棵樹之間相同（可能）根的連通子圖始終包含根並向下延伸。在某些情況下，甚至可以到達樹葉。看一個例子（黃色部分是包含根的連接子圖）：

給定這些規則，從數學上講，所有的樹都是相似的——連接的子圖要麼是空的，要麼只包含根，或者歸納起來——它包含根和它的孩子……

您可以按不同的“所有者”對樹節點的子節點進行分組。添加節點時，指定所有者（或 null 以使用預設的“共享”所有者）。當您遍歷您的樹時，您還指定了所有者。這是一個草圖程式碼：

class TreeNode {
   protected static readonly object SharedOwner = new object();
}

class TreeNode<T> : TreeNode {        
   private readonly T _data;
   private readonly Dictionary<object, List<TreeNode<T>>> _children;

   public TreeNode(T data) {
       this._data = data;
       _children = new Dictionary<object, List<TreeNode<T>>>();
   }

   public TreeNode<T> AddChild(T data, object owner = null) {
       if (owner == null)
           owner = SharedOwner;
       if (!_children.ContainsKey(owner))
           _children.Add(owner, new List<TreeNode<T>>());
       var added = new TreeNode<T>(data);
       _children[owner].Add(added);
       return added;
   }

   public void Traverse(Action<T> visitor, object owner = null) {
       TraverseRecursive(this, visitor, owner);
   }

   private void TraverseRecursive(TreeNode<T> node, Action<T> visitor, object owner = null) {
       visitor(node._data);
       // first traverse "shared" owner's nodes
       if (node._children.ContainsKey(SharedOwner)) {
           foreach (var sharedNode in node._children[SharedOwner]) {
               TraverseRecursive(sharedNode, visitor, owner);
           }
       }
       // then real owner's nodes
       if (owner != null && owner != SharedOwner && node._children.ContainsKey(owner)) {
           foreach (var localNode in node._children[owner]) {
               TraverseRecursive(localNode, visitor, owner);
           }
       }
   }
}

以及範例用法：

class Program {
   static void Main(string[] args) {
       // this is shared part
       var shared = new TreeNode<string>("1");
       var leaf1 = shared.AddChild("1.1").AddChild("1.1.1");
       var leaf2 = shared.AddChild("1.2").AddChild("1.2.1");
       var firstOwner = new object();
       var secondOwner = new object();
       // here we branch first time
       leaf1.AddChild("1.1.1.1", firstOwner);
       leaf2.AddChild("1.2.1.1", firstOwner);
       // and here another branch
       leaf1.AddChild("1.1.1.2", secondOwner);
       leaf2.AddChild("1.2.1.2", secondOwner);
       shared.Traverse(Console.WriteLine, firstOwner);
       shared.Traverse(Console.WriteLine, secondOwner);
       Console.ReadKey();
   }        
}

引用自：https://stackoverflow.com/questions/37065538