[發明專利]一種用于二叉樹添加和刪除結點的內存分配方法

在審

• 申請號: 202011084048.7
• 申請日: 2020-10-12
• 公開（公告）號: CN112328389A
• 公開（公告）日: 2021-02-05
• 發明（設計）人: 龍恢;管志堅
• 申請（專利權）人: 長沙新弘軟件有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F12/02
• 代理公司: 長沙市標致專利代理事務所(普通合伙) 43218
• 代理人: 徐邵華

一種用于二叉樹添加和刪除結點的內存分配方法，該方法的二叉樹中每個結點包含三個指針變量，一個父結點指針和兩個子結點指針，為二叉樹設置一個對應的鏈表用于構建二叉樹的私有內存池，初始狀態下鏈表為空。當向二叉樹添加結點的操作從系統分配內存時，分配兩倍結點尺寸大小的內存塊，即地址空間中連續的兩個結點，一個首結點和一個尾結點，將首結點作為新增結點插入二叉樹，將尾結點標記為影子結點并作為空閑內存塊放入二叉樹對應的鏈表。

技術領域

本發明涉及計算機系統軟件編程領域，特別是計算機基本數據結構中用于二叉樹添加和刪除結點的內存分配方法。

背景技術

在計算機軟件編程領域，二叉樹是一種常用的數據結構，用于通過鍵值對數據進行快速檢索。常見的有AVL樹、紅黑樹（RBTree）以及二元的基數樹（RadixTree），這些二叉樹添加和刪除結點都需要通過系統的全局內存池分配和釋放內存塊，在頻繁添加和刪除結點的應用場景中直接通過系統分配和釋放內存將造成很大的開銷。常規的解決方案是為二叉樹配置一個私有的內存池，二叉樹刪除結點時不會直接通過系統釋放內存，而是先放入二叉樹的私有內存池，當私有內存池中空閑內存塊積累到一定數量時再通過系統釋放內存。這樣二叉樹在添加結點時會先從私有內存池中找空閑內存塊創建新結點，避免了頻繁從系統分配內存造成的開銷，但有一個新的問題又產生了，那就是私有內存池中存放空閑內存塊的上限是多少才合適的問題。若私有內存池中存放大量的空閑內存塊將會導致內存資源的浪費，而存放的空閑內存塊太少又起不到緩解系統開銷大的問題。

發明內容

本發明的目的是克服現有技術的上述不足而提供一種用于二叉樹添加和刪除結點時自動調整私有內存池空閑內存塊數量的內存分配方法。

本發明的技術方案是：為二叉樹設置一個對應的鏈表用于構建二叉樹的私有內存池，初始狀態下鏈表為空。二叉樹中每個結點包含三個指針變量，一個父結點指針和兩個子結點指針。當向二叉樹添加結點的操作從系統分配內存時，分配兩倍結點尺寸大小的內存塊，即地址空間中連續的兩個結點，一個首結點和一個尾結點,將首結點作為新增結點插入二叉樹，將尾結點標記為影子結點（Shadow Node）并作為空閑內存塊放入二叉樹對應的鏈表。

當向二叉樹添加結點時，若對應的鏈表不為空，則從鏈表中取出一個影子結點作為新增結點插入二叉樹。

當從二叉樹刪除結點時，若被刪除的結點是影子結點，則將影子結點設置為空閑狀態并放入二叉樹對應的鏈表。

當從二叉樹刪除結點時，若被刪除的結點不是影子結點，則檢查對應的影子結點是否被占用，若未被占用，則將對應的影子結點從鏈表中取出，同被刪除結點一并通過系統釋放其內存資源。

當從二叉樹刪除結點時，若被刪除的結點對應的影子結點已被占用，則將影子結點的三個指針變量和數據遷移到被刪除的結點，并用被刪除的結點替換掉二叉樹中對應的影子結點，然后將影子結點設置為空閑狀態并放入二叉樹對應的鏈表。另一種方案是：從鏈表中取出一個新的影子結點，將被占用的影子結點中三個指針變量和數據遷移到新的影子結點，并用新的影子結點替換掉二叉樹中被占用的影子結點，然后將被刪除的結點和對應的影子結點一并通過系統釋放其內存資源。

本發明與現有技術相比具有如下特點：發明闡述了一種用于二叉樹添和加刪除結點的內存分配方法，通過每次從系統分配兩倍結點尺寸大小的內存，將一半用于二叉樹的新增結點，另一半標記為影子結點放入私有內存池來減少頻繁添加刪除結點時的系統開銷。和現有技術相比本發明有以下優勢：一、首先保證了私有內存池中空閑內存的數量最多時不會超過二叉樹中結點的數量，且隨著二叉樹中結點數量的減少而減少。二、因為每次通過系統分配和釋放兩倍結點大小的內存，即使在最壞情況下系統開銷也要比傳統方案減少一半。三、實施方案簡單通用性強，可適用于任何種類的二叉樹，不需要預分配池也不需要通過額外的算法來管理私有內存池。

以下結合附圖和具體實施方式對本發明的詳細結構作進一步描述。

附圖說明