更新時間:2023-10-23 來源:黑馬程序員 瀏覽量:
二叉查找樹的作用是提高檢索數(shù)據(jù)的性能, 小的存左邊,大的存右邊,一樣的不存。但出現(xiàn)瘸子現(xiàn)象,導(dǎo)致查詢的性能與單鏈表一樣,拉低查詢速度。
這時候需要用到平衡二叉樹,在滿足查找二叉樹的大小規(guī)則下,讓樹盡可能矮小,以此提高查數(shù)據(jù)的性能。
什么是平衡二叉樹
可以從以下二叉樹中找到平衡二叉樹的特點,任意節(jié)點的左右兩個子樹的高度差不超過1,任意節(jié)點的左右兩個子樹都是一顆平衡二叉樹。
平衡二叉樹在添加元素后可能導(dǎo)致不平衡,基本策略是進行左旋,或者右旋保證平衡。旋轉(zhuǎn)可能出現(xiàn)的四種情況:
? 左左
? 左右
? 右右
? 右左
平衡二叉樹-左左
當根節(jié)點左子樹的左子樹有節(jié)點插入,導(dǎo)致二叉樹不平衡。
平衡二叉樹-左右
當根節(jié)點左子樹的右子樹有節(jié)點插入,導(dǎo)致二叉樹不平衡
平衡二叉樹-右右
當根節(jié)點右子樹的右子樹有節(jié)點插入,導(dǎo)致二叉樹不平衡
平衡二叉樹-右左
當根節(jié)點右子樹的左子樹有節(jié)點插入,導(dǎo)致二叉樹不平衡