今天的博客是在上一篇博客的基礎(chǔ)上進(jìn)行的延伸。上一篇博客我們主要聊了二叉排序樹(shù)，詳情請(qǐng)戳《二叉排序樹(shù)的查找、插入與刪除》。本篇博客我們就在二叉排序樹(shù)的基礎(chǔ)上來(lái)聊聊平衡二叉樹(shù)，也叫AVL樹(shù)，AVL是發(fā)明平衡二叉樹(shù)的兩個(gè)科學(xué)家的名字的縮寫(xiě)，在此就不做深究了。其實(shí)平衡二叉樹(shù)就是二叉排序樹(shù)的一種，比二叉排序樹(shù)多了一個(gè)平衡的條件。在一個(gè)平衡二叉樹(shù)中，一個(gè)結(jié)點(diǎn)的左右子樹(shù)的深度差不超過(guò)1。

本篇博客我們就依照平衡二叉樹(shù)的特點(diǎn)，在創(chuàng)建二叉排序樹(shù)的同時(shí)要保證結(jié)點(diǎn)的左右子樹(shù)的深度差不超過(guò)1的規(guī)則。當(dāng)我們往二叉排序樹(shù)中插入結(jié)點(diǎn)時(shí)，我們要對(duì)二叉排序樹(shù)的平衡性進(jìn)行檢查，如果因插入這個(gè)新的結(jié)點(diǎn)二叉排序樹(shù)的平衡性被打破了，我們就得根據(jù)打破平衡二叉樹(shù)的類(lèi)型對(duì)二叉排序樹(shù)進(jìn)行調(diào)整使其再次進(jìn)入到平衡二叉樹(shù)的狀態(tài)。當(dāng)然，在刪除結(jié)點(diǎn)時(shí)也要二叉樹(shù)的平衡進(jìn)行檢查，發(fā)現(xiàn)不平衡時(shí)立馬進(jìn)行糾正。今天博客介紹的就是平衡二叉樹(shù)的創(chuàng)建于結(jié)點(diǎn)的刪除。廢話少說(shuō)，進(jìn)入今天博客的主題。

 

一、平衡二叉樹(shù)的結(jié)點(diǎn)

在博客的第一部分呢，我想先給出平衡二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)。當(dāng)然是在上篇博客中的二叉排序樹(shù)的結(jié)點(diǎn)上進(jìn)行修改的。下方這個(gè)AVLTreeNote就是我們本篇平衡二叉樹(shù)所使用的結(jié)點(diǎn)類(lèi)。該類(lèi)與二叉排序樹(shù)的結(jié)點(diǎn)類(lèi)差不多，就是增加了額外的三個(gè)字段。

  • depth字段用來(lái)記錄以該結(jié)點(diǎn)為根結(jié)點(diǎn)的樹(shù)的深度，因?yàn)橄路角笃胶庖蜃訒r(shí)會(huì)使用到該字段。
  • balanceFactor字段就是我們所說(shuō)的平衡因子，其實(shí)就是左子樹(shù)的深度減去右子樹(shù)的深度，因?yàn)橐豢闷胶舛鏄?shù)的左右子樹(shù)的深度差不會(huì)超過(guò)1，所以一顆平衡二叉樹(shù)的節(jié)點(diǎn)的平衡因子為-1，0，或者1。如果為其他值，那么說(shuō)明該平衡二叉樹(shù)已不再平衡，需要被平衡。
  • fatherNote字段用來(lái)指向該結(jié)點(diǎn)父節(jié)點(diǎn)，我們?cè)谡{(diào)整二叉樹(shù)的平衡時(shí)會(huì)用到該指針。

上面就是我們添加的三個(gè)字段，下方我們會(huì)分別給出depth與balanceFactor字段的計(jì)算方式。

延伸閱讀

學(xué)習(xí)是年輕人改變自己的最好方式-Java培訓(xùn),做最負(fù)責(zé)任的教育,學(xué)習(xí)改變命運(yùn),軟件學(xué)習(xí),再就業(yè),大學(xué)生如何就業(yè),幫大學(xué)生找到好工作,lphotoshop培訓(xùn),電腦培訓(xùn),電腦維修培訓(xùn),移動(dòng)軟件開(kāi)發(fā)培訓(xùn),網(wǎng)站設(shè)計(jì)培訓(xùn),網(wǎng)站建設(shè)培訓(xùn)學(xué)習(xí)是年輕人改變自己的最好方式