[發(fā)明專(zhuān)利]一種平衡二叉樹(shù)的非遞歸高性能構(gòu)建方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110883446.3
• 申請(qǐng)日: 2021-08-03
• 公開(kāi)（公告）號(hào): CN113326271A
• 公開(kāi)（公告）日: 2021-08-31
• 發(fā)明（設(shè)計(jì)）人: 王鳳雷;王鋒平;林世穎;時(shí)春
• 申請(qǐng)（專(zhuān)利權(quán)）人: 江蘇未來(lái)智慧信息科技有限公司
• 主分類(lèi)號(hào): G06F16/22
• 分類(lèi)號(hào): G06F16/22
• 代理公司: 常州佰業(yè)騰飛專(zhuān)利代理事務(wù)所(普通合伙) 32231
• 代理人: 姜曉鈺

1.一種平衡二叉樹(shù)的非遞歸高性能構(gòu)建方法，其特征在于：建立數(shù)據(jù)庫(kù)服務(wù)器、節(jié)點(diǎn)增加服務(wù)器、節(jié)點(diǎn)刪除服務(wù)器和平衡二叉樹(shù)構(gòu)建服務(wù)器，在數(shù)據(jù)庫(kù)服務(wù)器中建立HASH表的NOSQL數(shù)據(jù)庫(kù)并提供節(jié)點(diǎn)查詢功能；

節(jié)點(diǎn)增加服務(wù)器用于接收新插入的數(shù)據(jù)，并在新數(shù)據(jù)插入的時(shí)候判斷新插入的數(shù)據(jù)的節(jié)點(diǎn)鏈表的總數(shù)據(jù)量：若總數(shù)據(jù)量到達(dá)預(yù)設(shè)新增限值，則通知平衡二叉樹(shù)構(gòu)建服務(wù)器進(jìn)行平衡二叉樹(shù)的構(gòu)建；反之則在原有的平衡二叉樹(shù)上增加節(jié)點(diǎn)；

節(jié)點(diǎn)刪除服務(wù)器用于在刪除數(shù)據(jù)的時(shí)候，判斷若節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)為平衡二叉樹(shù)，則刪除完畢判斷樹(shù)的總節(jié)點(diǎn)數(shù)，若總節(jié)點(diǎn)數(shù)小于預(yù)設(shè)刪除限值，則重新將平衡二叉樹(shù)轉(zhuǎn)化為鏈表；

平衡二叉樹(shù)構(gòu)建服務(wù)器用于在接收到節(jié)點(diǎn)增加服務(wù)器的通知后，進(jìn)行構(gòu)建平衡二叉樹(shù)，并通知數(shù)據(jù)庫(kù)服務(wù)器根據(jù)構(gòu)建的平衡二叉樹(shù)進(jìn)行數(shù)據(jù)存儲(chǔ)；

平衡二叉樹(shù)構(gòu)建服務(wù)器根據(jù)平衡因子的計(jì)算與失衡節(jié)點(diǎn)的翻轉(zhuǎn)調(diào)整方法構(gòu)建平衡二叉樹(shù)，具體包括：

對(duì)于平衡因子的定義為右子樹(shù)高減去左子樹(shù)高；對(duì)于平衡二叉樹(shù)來(lái)說(shuō)，平衡因子的取值范圍為-1、0和1；

初始節(jié)點(diǎn)為0，若增加左子樹(shù)節(jié)點(diǎn)，則平衡因子為-1，若增加右子樹(shù)節(jié)點(diǎn)，則平衡因子為1；

若平衡因子變化為-2或者2，則觸發(fā)平衡旋轉(zhuǎn)；

對(duì)于AVL樹(shù)的失衡調(diào)整包括右旋調(diào)整、左旋調(diào)整、先左旋再右旋調(diào)整和先右旋再左旋調(diào)整；

設(shè)定平衡因子的表示方法以bf_nodename為準(zhǔn)，xnode的平衡因子名稱(chēng)即為bf_xnode，ynode的平衡因子名稱(chēng)即為bf_ynode，znode的平衡因子名稱(chēng)即為bf_znode；

右旋調(diào)整的計(jì)算方法如下：

bf_znode=bf_znode–(bf_ynode–1)；

bf_ynode=bf_ynode+1；

左旋調(diào)整的計(jì)算方法如下：

bf_znode=bf_znode–(bf_yndoe+1)；

bf_ynode=bf_ynode–1；

先左旋再右旋調(diào)整的計(jì)算方法如下：

bf_ynode=-(bf_xnode×bf_xnode+bf_xnode)÷2；

bf_znode=(bf_xnode×bf_xnode–bf_xnode)÷2；

bf_xnode=0；

先右旋再左旋調(diào)整的計(jì)算方法如下：

bf_ynode=(bf_xnode×bf_xnode-bf_xnode)÷2；

bf_znode=-(bf_xnode×bf_xnode+bf_xnode)÷2；

bf_xnode=0。

2.如權(quán)利要求1所述的一種平衡二叉樹(shù)的非遞歸高性能構(gòu)建方法，其特征在于：節(jié)點(diǎn)增加服務(wù)器在增加節(jié)點(diǎn)時(shí)，按照平衡二叉樹(shù)先搜索新增節(jié)點(diǎn)所需位置，即從根節(jié)點(diǎn)開(kāi)始，如果新增節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)小，則當(dāng)前節(jié)點(diǎn)改為被比較節(jié)點(diǎn)的左子節(jié)點(diǎn)，如果大，則為右子節(jié)點(diǎn)；

再將新增節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)比較，周而復(fù)始直到當(dāng)前節(jié)點(diǎn)的下個(gè)遍歷節(jié)點(diǎn)為空，則新增節(jié)點(diǎn)會(huì)替代當(dāng)前節(jié)點(diǎn)的空節(jié)點(diǎn)；

節(jié)點(diǎn)增加后，重新計(jì)算所涉及到節(jié)點(diǎn)的平衡因子。

3.如權(quán)利要求1所述的一種平衡二叉樹(shù)的非遞歸高性能構(gòu)建方法，其特征在于：節(jié)點(diǎn)刪除服務(wù)器在刪除節(jié)點(diǎn)時(shí)，首選區(qū)分被刪節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)，如果不是則需要跟葉子節(jié)點(diǎn)置換，即，取被刪除節(jié)點(diǎn)的左子樹(shù)的最大值或者右子樹(shù)的最小值與被刪除節(jié)點(diǎn)交換，然后刪除被交換后的葉子節(jié)點(diǎn)。

4.如權(quán)利要求1所述的一種平衡二叉樹(shù)的非遞歸高性能構(gòu)建方法，其特征在于：數(shù)據(jù)庫(kù)服務(wù)器在執(zhí)行節(jié)點(diǎn)查詢時(shí)，是對(duì)平衡二叉樹(shù)的節(jié)點(diǎn)進(jìn)行查詢，包括首選將要查詢的數(shù)據(jù)與根節(jié)點(diǎn)進(jìn)行大小比較，若查詢數(shù)據(jù)小，則將目標(biāo)轉(zhuǎn)為根節(jié)點(diǎn)的左子節(jié)點(diǎn)，否則轉(zhuǎn)為右子節(jié)點(diǎn)；

然后再次進(jìn)行比較，直到找到相等的節(jié)點(diǎn)或者子節(jié)點(diǎn)為空；子節(jié)點(diǎn)為空表示查詢失敗。