[發明專利]一種平衡二叉樹的非遞歸高性能構建方法

在審

• 申請號: 202110883446.3
• 申請日: 2021-08-03
• 公開（公告）號: CN113326271A
• 公開（公告）日: 2021-08-31
• 發明（設計）人: 王鳳雷;王鋒平;林世穎;時春
• 申請（專利權）人: 江蘇未來智慧信息科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 常州佰業騰飛專利代理事務所(普通合伙) 32231
• 代理人: 姜曉鈺

本發明公開了一種平衡二叉樹的非遞歸高性能構建方法，屬于計算機基礎算法技術領域，包括建立數據庫服務器、節點增加服務器、節點刪除服務器和平衡二叉樹構建服務器，在構建AVL樹時，對于AVL樹的失衡調整包括右旋調整、左旋調整、先左旋再右旋調整和先右旋再左旋調整，解決了采用非遞歸方法實現了AVL樹的增加、刪除和查詢的操作的技術問題，本發明對于項目中需要用到AVL樹的查詢場合，可以以類似于紅黑樹生成的效率生成AVL樹，以比紅黑樹高10%左右的查詢效率進行數據查詢，生成樹效率比紅黑樹算法沒有大的優勢，可以應用在對生成數據時間稍微不敏感但對查詢速度有很高要求的場合，算法耗時也比遞歸算法大幅降低。

技術領域

本發明屬于計算機基礎算法技術領域，涉及一種平衡二叉樹的非遞歸高性能構建方法。

背景技術

平衡二叉樹（AVL樹）是計算機基礎數據結構中常用的一種數據結構。該數據結構要求樹中任意一節點左右子樹的高度差不超過1。雖然現在的計算機工程應用中紅黑樹以其更方便高效的插入刪除操作和多數情況下接近平衡二叉樹的查找效率，在絕大多數場合代替了平衡二叉樹，使得平衡二叉樹更多的出現在數據結構的教學場合。但在某些對查詢速率要求非?？量痰膱龊希胶舛鏄溥€是最優的數據結構選擇。目前絕大多數關于平衡二叉樹的算法都是遞歸實現的，或者以平衡二叉樹的定義分別計算左右子樹的高度并求高度差來對子樹進行旋轉平衡。這樣的算法在樹節點數超過一定數量的規模后，效率和算法復雜度最終會讓代碼失去實際的工程可用性。

在基于HASH表的NOSQL數據庫中，當數據量到達一定量級后，處理hash節點的重復數據就變得不可避免。在傳統的方法中，一般使用鏈表將重復節點的數據串聯起來，由于鏈表本身的數據是無序排列的，所以查詢的時候需要從鏈表頭開始遍歷直到找到所需數據為止。這種情況在數據量低的時候對系統性能影響不大，一旦重復節點的紀錄數變多會嚴重影響性能。

發明內容

本發明為解決上述技術問題，本發明的目的是提供一種平衡二叉樹的非遞歸高性能構建方法，解決了采用非遞歸方法實現了AVL樹的增加、刪除和查詢的操作的技術問題。

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

一種平衡二叉樹的非遞歸高性能構建方法，建立數據庫服務器、節點增加服務器、節點刪除服務器和平衡二叉樹構建服務器，在數據庫服務器中建立HASH表的NOSQL數據庫并提供節點查詢功能；

節點增加服務器用于接收新插入的數據，并在新數據插入的時候判斷新插入的數據的節點鏈表的總數據量：若總數據量到達預設新增限值，則通知平衡二叉樹構建服務器進行平衡二叉樹的構建；反之則在原有的平衡二叉樹上增加節點；

節點刪除服務器用于在刪除數據的時候，判斷若節點數據結構為平衡二叉樹，則刪除完畢判斷樹的總節點數，若總節點數小于預設刪除限值，則重新將平衡二叉樹轉化為鏈表；

平衡二叉樹構建服務器用于在接收到節點增加服務器的通知后，進行構建平衡二叉樹，并通知數據庫服務器根據構建的平衡二叉樹進行數據存儲。

平衡二叉樹構建服務器根據平衡因子的計算與失衡節點的翻轉調整方法構建平衡二叉樹，具體包括：

對于平衡因子的定義為右子樹高減去左子樹高；對于平衡二叉樹來說，平衡因子的取值范圍為-1、0和1；

初始節點為0，若增加左子樹節點，則平衡因子為-1，若增加右子樹節點，則平衡因子為1；

若平衡因子變化為-2或者2，則觸發平衡旋轉；

對于AVL樹的失衡調整包括右旋調整、左旋調整、先左旋再右旋調整和先右旋再左旋調整；

設定平衡因子的表示方法以bf_nodename為準，xnode的平衡因子名稱即為bf_xnode，ynode的平衡因子名稱即為bf_ynode，znode的平衡因子名稱即為bf_znode；

右旋調整的計算方法如下：

bf_znode=bf_znode–(bf_ynode–1)；

bf_ynode=bf_ynode+1；