什么是平衡二叉樹？為空樹或左右子樹高差絕對值不大于1，左右子樹均為平衡二叉樹。常用的算法有紅黑樹、AVL、swap、伸縮樹等。在平衡二叉搜索樹中，我們可以看到它的高度一般保持在O（log2n），這大大

什么是平衡二叉樹？

為空樹或左右子樹高差絕對值不大于1，左右子樹均為平衡二叉樹。常用的算法有紅黑樹、AVL、swap、伸縮樹等。在平衡二叉搜索樹中，我們可以看到它的高度一般保持在O（log2n），這大大降低了操作的時(shí)間復(fù)雜度。

在平衡二叉樹中,插入一個(gè)節(jié)點(diǎn)后引起不平衡,設(shè)離插入節(jié)點(diǎn)最近的不平衡點(diǎn)是A，并且已知A的左右孩子的平衡節(jié)點(diǎn)？

由于節(jié)點(diǎn)a右子樹的平衡因子為0，只能是插入左子樹的節(jié)點(diǎn)，即節(jié)點(diǎn)a左子樹加高。如果平衡因子的定義是左子樹的高度右子樹的高度，則節(jié)點(diǎn)a的平衡因子必須為零如果平衡因子的定義是右子樹的高度左子樹的高度，則a的平衡因子必須為-2，并且需要向右旋轉(zhuǎn)，即，RR旋轉(zhuǎn)

兩者的重點(diǎn)不同

！平衡二叉樹就是追求絕對平衡。我們無法知道每次插入節(jié)點(diǎn)后的旋轉(zhuǎn)次數(shù)。這樣，實(shí)現(xiàn)條件更加嚴(yán)格，復(fù)雜度非常高。恰恰相反，紅黑樹只追求一般的平衡。在與平衡二叉樹的時(shí)間復(fù)雜度相同的情況下，插入3到4次就可以達(dá)到平衡，相對簡單。