文/玄魂
博文中引用的代碼并非是.NET源碼，而是反編譯得來，不正确之處，還望指教。
接上篇博文，當初始化一個沒有任何元素的ImmutableList<T>對象之後，對象會獲得一個EmptyNode。
下面看看添加一個元素的流程，及資料結構的變化。
測試代碼：
如上圖，在Add方法内部，會調用Node類型的Add方法，傳回一個新的的Node執行個體。Add方法源碼如下：
Add方法又調用了Insert方法，此時count=0，key=”ddd”。在Insert内部先判斷了左子樹是否為空，如果為空則建立新的Node，調用具有四個輸入參數的構造函數。
這一步很巧妙的完成了樹的構造，代碼如下：
原來的root（empty node）這裡變成新Node的左右子節點，新節點key字段（即value）被指派“ddd”，height和count都等于1，此時frozen=false。需要注意的細節是，調用Node(T key, ImmutableList<T>.Node left, ImmutableList<T>.Node right, bool frozen = false)之前傳入的this指針和函數内部的this指針指向的是不同的記憶體區域。
注意，傳入的Node對象沒有做任何修改，傳回的是新New的Node。
目前建立的Node對象的結構如下：
繼續運作，從Node類裡出來，回到ImmutableList<T>的Add方法：
在得到新的的Node後，會執行Wrap方法。
同理，内部的Node完成了樹形結構的轉換，外部的ImmutableList<T>也要完成這一轉換，傳回新的ImmutableList<T>對象，将新的Node指派到自己的root字段上，并初始化相關字段。
OK，終于又回到了Main函數中，完成了一次輪回：
ImmutableList<T>通過更新樹結構，建立ImmutableList<T>對象同時更新對Node的引用建立新的集合。樹結構雖然發生了變化，但是原來的集合對節點的引用并沒有發生變化，進而保證了集合的不變性。
繼續修改Main函數的代碼:
我們觀察執行var a3 = a2.Add("ccc")時的行為變化。
目前代碼沿着上圖所示的路徑再次來到Node類的Insert方法。
第一次執行Add時的情景上面分析過了，當Node的左右子樹不為空時，首先要判斷元素應該添加左還是右，判斷邏輯很簡單，判斷目前準備添加元素的索引是否小于等于左子樹元素的個數。由于目前左子樹隻有一個Empty節點，是以元素會被添加到右子樹上去。可以設想一下，如果再次執行添加操作，元素還是會被添加到右子樹上去，左邊會一直為空。是以在每次添加操作執行完畢之後，會調用MakeBalanced方法來使左右平衡。如果您熟悉紅黑樹的話，對保持樹的平衡時使用的扭轉算法應該不會陌生。這裡我不想深入解釋ImmutableList 的“平衡扭轉”算法，我覺得單獨拿出來一篇博文來講解會更好。
下一篇部落格中，我們繼續分析ImmutableList的其他行為的原理。
本文轉自玄魂部落格園部落格，原文連結：http://www.cnblogs.com/xuanhun/p/3159823.html，如需轉載請自行聯系原作者