今天的博客是在上一篇博客的基礎(chǔ)上進(jìn)行的延伸。上一篇博客我們主要聊了二叉排序樹，詳情請戳《二叉排序樹的查找、插入與刪除》。本篇博客我們就在二叉排序樹的基礎(chǔ)上來聊聊平衡二叉樹，也叫AVL樹，AVL是發(fā)明平衡二叉樹的兩個(gè)科學(xué)家的名字的縮寫，在此就不做深究了。其實(shí)平衡二叉樹就是二叉排序樹的一種，比二叉排序樹多了一個(gè)平衡的條件。在一個(gè)平衡二叉樹中，一個(gè)結(jié)點(diǎn)的左右子樹的深度差不超過1。
本篇博客我們就依照平衡二叉樹的特點(diǎn)，在創(chuàng)建二叉排序樹的同時(shí)要保證結(jié)點(diǎn)的左右子樹的深度差不超過1的規(guī)則。當(dāng)我們往二叉排序樹中插入結(jié)點(diǎn)時(shí)，我們要對二叉排序樹的平衡性進(jìn)行檢查，如果因插入這個(gè)新的結(jié)點(diǎn)二叉排序樹的平衡性被打破了，我們就得根據(jù)打破平衡二叉樹的類型對二叉排序樹進(jìn)行調(diào)整使其再次進(jìn)入到平衡二叉樹的狀態(tài)。當(dāng)然，在刪除結(jié)點(diǎn)時(shí)也要二叉樹的平衡進(jìn)行檢查，發(fā)現(xiàn)不平衡時(shí)立馬進(jìn)行糾正。今天博客介紹的就是平衡二叉樹的創(chuàng)建于結(jié)點(diǎn)的刪除。廢話少說，進(jìn)入今天博客的主題。
一、平衡二叉樹的結(jié)點(diǎn)
在博客的第一部分呢，我想先給出平衡二叉樹的結(jié)點(diǎn)結(jié)構(gòu)。當(dāng)然是在上篇博客中的二叉排序樹的結(jié)點(diǎn)上進(jìn)行修改的。下方這個(gè)AVLTreeNote就是我們本篇平衡二叉樹所使用的結(jié)點(diǎn)類。該類與二叉排序樹的結(jié)點(diǎn)類差不多，就是增加了額外的三個(gè)字段。
- depth字段用來記錄以該結(jié)點(diǎn)為根結(jié)點(diǎn)的樹的深度，因?yàn)橄路角笃胶庖蜃訒r(shí)會使用到該字段。
- balanceFactor字段就是我們所說的平衡因子，其實(shí)就是左子樹的深度減去右子樹的深度，因?yàn)橐豢闷胶舛鏄涞淖笥易訕涞纳疃炔畈粫^1，所以一顆平衡二叉樹的節(jié)點(diǎn)的平衡因子為-1，0，或者1。如果為其他值，那么說明該平衡二叉樹已不再平衡，需要被平衡。
- fatherNote字段用來指向該結(jié)點(diǎn)父節(jié)點(diǎn)，我們在調(diào)整二叉樹的平衡時(shí)會用到該指針。
上面就是我們添加的三個(gè)字段，下方我們會分別給出depth與balanceFactor字段的計(jì)算方式。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式