平衡二叉樹(shù)是什么？平衡二叉樹(shù)旋轉(zhuǎn)的4種情況

二叉查找樹(shù)的作用是提高檢索數(shù)據(jù)的性能， 小的存左邊，大的存右邊，一樣的不存。但出現(xiàn)瘸子現(xiàn)象，導(dǎo)致查詢的性能與單鏈表一樣，拉低查詢速度。

這時(shí)候需要用到平衡二叉樹(shù)，在滿足查找二叉樹(shù)的大小規(guī)則下，讓樹(shù)盡可能矮小，以此提高查數(shù)據(jù)的性能。

什么是平衡二叉樹(shù)

可以從以下二叉樹(shù)中找到平衡二叉樹(shù)的特點(diǎn)，任意節(jié)點(diǎn)的左右兩個(gè)子樹(shù)的高度差不超過(guò)1，任意節(jié)點(diǎn)的左右兩個(gè)子樹(shù)都是一顆平衡二叉樹(shù)。

平衡二叉樹(shù)在添加元素后可能導(dǎo)致不平衡，基本策略是進(jìn)行左旋，或者右旋保證平衡。旋轉(zhuǎn)可能出現(xiàn)的四種情況：

? 左左

? 左右

? 右右

? 右左

平衡二叉樹(shù)-左左

當(dāng)根節(jié)點(diǎn)左子樹(shù)的左子樹(shù)有節(jié)點(diǎn)插入，導(dǎo)致二叉樹(shù)不平衡。

平衡二叉樹(shù)-左右

當(dāng)根節(jié)點(diǎn)左子樹(shù)的右子樹(shù)有節(jié)點(diǎn)插入，導(dǎo)致二叉樹(shù)不平衡

平衡二叉樹(shù)-右右

當(dāng)根節(jié)點(diǎn)右子樹(shù)的右子樹(shù)有節(jié)點(diǎn)插入，導(dǎo)致二叉樹(shù)不平衡

平衡二叉樹(shù)-右左

當(dāng)根節(jié)點(diǎn)右子樹(shù)的左子樹(shù)有節(jié)點(diǎn)插入，導(dǎo)致二叉樹(shù)不平衡