BST存在的問(wèn)題

BST的性質(zhì)有可能導(dǎo)致所有的數(shù)據(jù)都插在了同一個(gè)鏈路上，導(dǎo)致沒(méi)有一個(gè)節(jié)點(diǎn)有左子樹(shù)，都是右子樹(shù)，像是一個(gè)鏈表，失去了它的lgn的性質(zhì)

AVL的性質(zhì)

AVL是作者的名字縮寫(xiě)

每個(gè)左子樹(shù)的高度與右子樹(shù)的高度差值不大于1

如果是AVL+BST需要只需要在BST的基礎(chǔ)上加上AVL的性質(zhì)，AVL本身需要去維護(hù)高度

另為在一個(gè)高度為h的AVL中節(jié)點(diǎn)的最少的數(shù)量，有

一個(gè)AVL樹(shù)，除去根節(jié)點(diǎn)這層，至少包含的左右兩部分為:一邊是高度為h-1,另一邊是高度為h-2

從上式可得：，即h<2lgn,因而得到AVL的高度肯定是lgn

AVL樹(shù)+BST的插入

插入過(guò)程中，一旦出現(xiàn)層級(jí)超過(guò)1的情況，需要進(jìn)行旋轉(zhuǎn)，而對(duì)應(yīng)出現(xiàn)2層的高度差別，只會(huì)出現(xiàn)如下4種

• 情況1：

1 \ 2 \ 3 需要進(jìn)行一次左旋2 / \ 1 3 復(fù)制代碼

• 情況2

1 \ 3 / 2 先右旋 1 \ 2 \ 3 再左旋2 / \ 1 3 復(fù)制代碼

• 情況3

3 / 2 / 1 右旋2 / \ 1 3 復(fù)制代碼

• 情況4

3 / 1 \ 2 對(duì)1進(jìn)行左旋3 / 2 / 1 再右旋2 / \ 1 3 復(fù)制代碼

保持平衡的算法為

def _reblance(self,node):while node is not None:self._update_height(node)if self._height(node.left) - self._height(node.right) >=2://左子樹(shù)要高nodeL = node.left if self._height(nodeL.left) < self._height(nodeL.right)://情況4self._left_roate(nodeL)//情況3+情況4self._right_roate(node)elif self._height(node.right) - self._height(node.left) >=2://右子樹(shù)要高nodeR = node.right if self._height(nodeR.left) > self._height(nodeR.right)://情況2self._right_roate(nodeR)//情況1+情況2self._left_roate(node)node = node.parent 復(fù)制代碼

左旋

def _left_roate(self,node):'''當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)高度-左節(jié)點(diǎn)高度>=2從上到下，按照父子一對(duì)一對(duì)處理'''pivot = node.rightpivot.parent = node.parent if node == self.root:self.root = pivotelse:if node.parent.left is node:pivot.parent.left = pivotelse:pivot.parent.right = pivottempNode = pivot.leftpivot.left = nodenode.parent = pivotnode.right = tempNodeif tempNode is not None:tempNode.parent = nodeself._update_height(pivot)self._update_height(node) 復(fù)制代碼

右旋

def _right_roate(self,node):'''當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)高度-右節(jié)點(diǎn)高度>=2右旋表示左邊節(jié)點(diǎn)高'''pivot=node.left pivot.parent = node.parentif node == self.root:self.root=pivotelse:if node.parent.left is node:pivot.parent.left = pivotelse:pivot.parent.right = pivotnode.parent = pivottempNode = pivot.right pivot.right = nodenode.left = tempNodeif tempNode is not None:tempNode.parent = nodeself._update_height(pivot)self._update_height(node) 復(fù)制代碼

代碼詳情

總結(jié)

以上是生活随笔為你收集整理的AVL树：解决BST可能导致的长链问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。