[發明專利]一種實現進程間AVL樹使用的方法及系統

在審

• 申請號: 201710832110.8
• 申請日: 2017-09-15
• 公開（公告）號: CN107656993A
• 公開（公告）日: 2018-02-02
• 發明（設計）人: 葛世飛
• 申請（專利權）人: 上海斐訊數據通信技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州千克知識產權代理有限公司33246
• 代理人: 周希良,吳輝輝

技術領域

本發明涉及AVL算法技術領域，尤其涉及一種實現進程間AVL樹使用的方法及系統。

背景技術

在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。

AVL樹的查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。AVL樹是一種效率較高的數據結構，應用比較廣泛。

但由于AVL樹采用“指針”管理左右子節點，而在現代操作系統中各進程的地址空間是獨立的，這意味著“指針”在進程間是無效的，所以現有技術的AVL樹不能在進程間使用。

傳統的AVL樹通過指針管理左右子節點，它的核心數據結構如下：

如圖1所示，圖1是傳統技術中AVL樹示意圖。

AVL樹中每一個節點抽象成AVL節點數據結構，該數據結構內存通過malloc函數分配，malloc函數返回的地址是本進程用戶空間中的虛擬地址。每棵樹有一個根節點稱為root AVLNode，根節點root AVLNode數據結構中指針lchild指向該節點的左子節點，rchild指向該節點的右子節點，如果子節點不存在，則指向NULL。每個節點AVLNode都有一個值，如圖1中根節點的值為55，各個節點根據值決定在AVL樹中的位置，左子節點的值小于根節點，右子節點的值大于根節點。

公開號為CN102521334A的專利提供了一種基于分類特性和平衡二叉樹的數據存儲、查詢方法，通過構建平衡二叉樹，創建結點；可以按照3種順序：中序、前序、后續遍歷規則，動態地將數據信息分類存儲到相應結點；輸入查詢內容，動態遍歷AVL樹，得到所需的數據信息。本發明將動態查詢的時間復雜度降低到靜態查詢級別，大大提高了存儲和查詢的效率，具有速度快、能耗低、占內存少、算法簡單的優點，而且可用多種語言實現。該方法廣泛適用于通信領域中的數據管理，尤其是物聯網通信中大數據量的數據存儲和查詢。但是該方法是通過指針管理左右子節點，不能在進程間使用。

發明內容

本發明要解決的技術問題目的在于提供一種實現進程間AVL樹使用的方法及系統，用以解決現有的AVL樹的操作系統不能在進程間使用的問題。

為了實現上述目的，本發明采用的技術方案為：

一種實現進程間AVL樹使用的方法，包括步驟：

S1、依次分配進程間AVL樹節點的值；

S2、按順序確定所述進程間AVL樹節點的索引值；

S3、根據所述進程間AVL節點的值及所述索引值建立共享內存；

S4、將所述共享內存映射到各進程的本地進程地址空間。

進一步地，步驟S3中，通過shm_open函數建立所述進程間AVL樹的共享內存。

進一步地，步驟S4中，通過mmap函數映射到各進程的本地進程地址空間。

進一步地，還包括步驟：

通過lchild值管理所述進程間AVL樹的左子節點；所述lchild值對應左子節點的索引值。

進一步地，還包括步驟：

通過rchild值管理所述進程間AVL樹的右子節點；所述rchild值對應右子節點的索引值。

一種實現進程間AVL樹使用的系統，包括：

分配模塊，用于依次分配進程間AVL樹節點的值；

編號模塊，用于按順序確定所述進程間AVL樹節點的索引值；

建立模塊，用于根據所述進程間AVL節點的值及所述索引值建立共享內存；

映射模塊，用于將所述共享內存映射到各進程的本地進程地址空間。

進一步地，所述建立模塊具體用于通過shm_open函數建立所述進程間AVL樹的共享內存。

進一步地，所述映射模塊具體用于通過mmap函數映射到各進程的本地進程地址空間。

進一步地，還包括：

左指針模塊，用于通過lchild值管理所述進程間AVL樹的左子節點；所述lchild值對應左子節點的索引值。

進一步地，還包括：

右指針模塊，用于通過rchild值管理所述進程間AVL樹的右子節點；所述rchild值對應右子節點的索引值。

本發明與傳統的技術相比，有如下優點：

本發明用共享內存的索引值管理左右子節點代替傳統的指針管理左右子節點，實現在進程間采用AVL樹管理各個節點。

附圖說明