时间戳

首页 > 解决方案 > AVL树如何在插入时平衡树

vb.net - 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

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

标签： vb.netrecursion

解决方案

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

您必须了解，从它自己的角度来看，每个节点都是它自己树的根，有点像整个二叉树是由许多较小的二叉树组成的。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 之外工作，所以我必须直接在浏览器中输入，这意味着我可能在写这篇文章时犯了一些错误。让我知道这是否没有意义，我会仔细检查更好的条件。祝你好运！

推荐阅读