AVL树如何在插入时平衡树

Question

我想为avl树创建一个插入函数。但是，插入函数必须是递归的，并且必须是平衡的。

我有一个向左枢轴树旋转的方法，以及一个向右枢

轴树的方法。

'Pivot left
Private Function PivoterAGauche(leNoeud As NoeudAVL) As NoeudAVL
If leNoeud Is Nothing Then
Return Nothing
ElseIf leNoeud.FilsDroit Is Nothing AndAlso leNoeud.FilsGauche Is Nothing Then
Return leNoeud
ElseIf leNoeud.FilsDroit Is Nothing Then
Return leNoeud
' ElseIf leNoeud.FilsGauche Is Nothing Then
Else 'Le leNoeud.FilsGauche existe.
Dim pivot As NoeudAVL = leNoeud.FilsGauche
leNoeud.FilsGauche = pivot.FilsDroit
pivot.FilsDroit = leNoeud
leNoeud = pivot
Return leNoeud
End If
End Function
'pivot rigth
Private Function PivoterADroite(leNoeud As NoeudAVL) As NoeudAVL
If leNoeud Is Nothing Then
Return Nothing
ElseIf leNoeud.FilsDroit Is Nothing AndAlso leNoeud.FilsGauche Is Nothing Then
Return leNoeud
ElseIf leNoeud.FilsDroit Is Nothing Then
Return leNoeud
' ElseIf leNoeud.FilsGauche Is Nothing Then
Else 'Le leNoeud.FilsGauche existe.
Dim pivot As NoeudAVL = leNoeud.FilsDroit
leNoeud.FilsDroit = pivot.FilsGauche
pivot.FilsGauche = leNoeud
leNoeud = pivot
Return leNoeud
End If
End Function

这是我制作的插入方法。我不确定何时使用左枢轴和钻机。

Private Function Inserer(leElement As T, leNoeudCourant As NoeudAVL) As NoeudAVL
Dim intBalance As Integer
'If the node does not existes
If leNoeudCourant Is Nothing Then
m_blnOperationOK = True
Return New NoeudAVL(leElement)
'If the node already existes.
ElseIf leElement.CompareTo(leNoeudCourant.Element) = 0 Then
m_blnOperationOK = False
Return leNoeudCourant
ElseIf leElement.CompareTo(leNoeudCourant.Element) < 0 Then
intBalance = Hauteur(leNoeudCourant.FilsGauche) - Hauteur(leNoeudCourant.FilsDroit)
If (intBalance = 2) Then
leNoeudCourant = PivoterAGauche(leNoeudCourant)
End If
leNoeudCourant.FilsGauche = Inserer(leElement, leNoeudCourant.FilsGauche)
ElseIf leElement.CompareTo(leNoeudCourant.Element) > 0 Then
intBalance = Hauteur(leNoeudCourant.FilsGauche) - Hauteur(leNoeudCourant.FilsDroit)
If (intBalance = 2) Then
leNoeudCourant = PivoterADroite(leNoeudCourant)
End If
leNoeudCourant.FilsDroit = Inserer(leElement, leNoeudCourant.FilsDroit)
End If
'Return current node that will become the root.
Return leNoeudCourant

如果您还有其他问题，我很乐意回答您的问题，感谢您的帮助。

Answer 1

让我们记住一些非常基本的事情：在二叉树等任务中使用递归时，您的工作区是一个节点。这意味着这个节点必须拥有它所需要的一切，才能完成你想要它做的任务。

你必须明白，从它自己的角度来看，每个节点都是它自己的树的根，有点像整个二叉树是由许多更小的二叉树构建的。O节点知道它是孩子，但不知道它是祖先。

为了能够构建一个平衡的二叉树，你的节点必须能够"知道"这些事情：

它们

• 的高度(它们下面有多少节点(。
• 如果它们变得不平衡(在当前评估的节点下，两个孩子的身高差都高于 1 级(。

这里的魔力是强大的：一旦正确实施，二叉树将始终保持平衡，而不必完全重新评估自己。这是大脑时间。

首先，让我们做高度的事情：

每个节点都必须具有高度值。此值必须作为模态变量存储在节点类中。使其成为公共属性，因为节点的父节点必须能够访问它。

Private _height As Integer = 0
Public ReadOnly Property Height As Integer
Get
Return _height
End Get
End Property

插入第一个节点(根(时，其高度为零。下面什么都没有。对于您创建的每个新节点都是如此。

当你插入另一个节点时，你通常会"给出"要插入到根的值，让递归做它的魔术。现在，在此操作期间还需要考虑其他事项：更新高度并更正平衡。

Private Function insert(ByVal key As Integer, Optional node As Node = Nothing, ) As Node
'if you are creating the root, node is nothing
If (node Is Nothing) Then
Return New Node(key)
End If
'creating new nodes when needed
If (key < node.key) Then
node.FilGauche = insert(key, node.FilGauche)
ElseIf (key > node.key) Then
node.FilDroit = insert(key, node.FilDroit)
Else
Return node
End If
're-evaluating height (accounting for null pointers) and then balancing the tree
node._height = (1 + max(If(node.FilGauche.Height IsNot Nothing, node.FilGauche.Height, 0), node.FilDroit.Height IsNot Nothing, node.FilDroit.Height))
Dim balance As Integer = If(node.FilGauche.Height IsNot Nothing, node.FilGauche.Height, 0) - If(node.FilDroit.Height IsNot Nothing, node.FilDroit.Height, 0)
' If this node becomes unbalanced, then there 
' are 4 cases Left Left Case 
If ((balance > 1) AndAlso (key < node.FilGauche.key)) Then
Return rightRotate(node)
End If
' Right Right Case 
If ((balance < -1) AndAlso (key > node.FilDroit.key)) Then
Return leftRotate(node)
End If
' Left Right Case 
If ((balance > 1) AndAlso (key > node.FilGauche.key)) Then
node.FilGauche = leftRotate(node.FilGauche)
Return rightRotate(node)
End If
' Right Left Case 
If ((balance < -1) AndAlso (key < node.FilDroit.key)) Then
node.FilDroit = rightRotate(node.FilDroit)
Return leftRotate(node)
End If
Return node
End Function

当然，您必须根据自己的具体情况调整这些想法，但这不是唯一的事情：我正在使用另一种语言的引用并在IDE之外工作，因此我必须直接在浏览器中键入，这意味着我可能犯了一些错误写这个。如果这没有意义，请告诉我，我会仔细检查更好的条件。祝你好运！