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

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

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

什么是平衡二叉樹

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

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

? 左左

? 左右

? 右右

? 右左

平衡二叉樹-左左

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

平衡二叉樹-左右

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

平衡二叉樹-右右

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

平衡二叉樹-右左

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