AVL树如何在插入时平衡树

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

我有一个将树向左旋转的方法 PivoterAGauche 和一个将树向右旋转的方法 PivoterADroite。

    '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

如果您有更多问题，我很乐意回答您的问题，感谢您的帮助。

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

你必须明白，从它自己的角度来看，每个节点都是它自己的树的根，有点像整个二叉树是由许多较小的二叉树构建的。 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 之外进行工作，因此我必须直接在浏览器中输入内容，这意味着我可能会写这篇文章时犯了一些错误。如果这没有意义，请告诉我，我会在更好的条件下仔细检查。祝你好运！