Public Class RBTree

Public root As RBTNode Dim null As RBTNode

Public Sub New(ByVal data As Integer) null = New RBTNode("-1") null.color = "black" root = New RBTNode(data) root.color = "black" root.Left = null root.Left.parent = root root.right = null root.right.parent = root End Sub

Public Sub New()

End Sub

Public Sub Insert(ByVal data As Integer)

null = New RBTNode("-1") null.color = "black"

'step one, insert a red node in the tree If root Is Nothing Then root = New RBTNode(data) root.color = "black" root.Left = null root.Left.parent = root root.right = null root.right.parent = root Else Dim newNode As New RBTNode(data) newNode.Left = null newNode.Left.parent = newNode newNode.right = null newNode.right.parent = newNode Dim current As RBTNode current = root Dim parent As RBTNode While (True) parent = current If (data < current.data) Then current = current.Left If (current.data < 0) Then parent.Left = newNode newNode.parent = parent Exit While End If Else current = current.right If current.data < 0 Then parent.right = newNode newNode.parent = parent Exit While End If End If End While 'step two, rebalance the tree rebalance(newNode)

If Not (root Is Nothing) AndAlso Not (root.parent Is Nothing) Then root = root.parent End If End If End Sub

Private Sub rebalance(ByVal current As RBTNode)

line1: If current.data = root.data Then current.color = "black" Exit Sub End If

If current.parent.color = "black" Then Exit Sub End If

If current.parent.color = "red" AndAlso Nuncle(current).color = "red" Then current.parent.color = "black" Nuncle(current).color = "black" current.parent.parent.color = "red" current = current.parent.parent GoTo line1 End If

If current.data = current.parent.right.data AndAlso current.parent.data = current.parent.parent.Left.data AndAlso current.parent.color = "red" AndAlso Nuncle(current).color = "black" Then current = current.parent current = LeftRotate(current) GoTo line1 End If

If current.data = current.parent.Left.data AndAlso current.parent.data = current.parent.parent.right.data AndAlso current.parent.color = "red" AndAlso Nuncle(current).color = "black" Then current = current.parent current = RightRotate(current) GoTo line1 End If

If current.data = current.parent.Left.data AndAlso current.parent.data = current.parent.parent.Left.data AndAlso current.parent.color = "red" AndAlso Nuncle(current).color = "black" Then current.parent.color = "black" current.parent.parent.color = "red" current = RightRotate(current.parent.parent) current = Nuncle(current.Left) GoTo line1 End If

If current.data = current.parent.right.data AndAlso current.parent.data = current.parent.parent.right.data AndAlso current.parent.color = "red" AndAlso Nuncle(current).color = "black" Then current.parent.color = "black" current.parent.parent.color = "red" current = LeftRotate(current.parent.parent) current = Nuncle(current.Left) GoTo line1 End If

End Sub

Private Function Nuncle(ByVal current As RBTNode) As RBTNode Dim uncle As RBTNode Dim grandparent As RBTNode = current.parent.parent If grandparent.Left.data = current.parent.data Then uncle = grandparent.right Else uncle = grandparent.Left End If Return uncle End Function

Private Function LeftRotate(ByVal current As RBTNode) Dim s As RBTNode = current.right Dim T As RBTNode = s.Left Dim P As RBTNode = current.parent

s.Left = current current.parent = s

current.right = T T.parent = current

If Not (P Is Nothing) Then If (P.data > s.data) Then P.Left = s s.parent = P Else P.right = s s.parent = P End If End If

Return current End Function

Private Function RightRotate(ByVal current As RBTNode) Dim s As RBTNode = current.Left Dim T As RBTNode = s.right Dim P As RBTNode = current.parent

s.right = current current.parent = s

current.Left = T T.parent = current

If Not (P Is Nothing) Then If (P.data > s.data) Then P.Left = s s.parent = P Else P.right = s s.parent = P End If End If Return current End Function

'Delete Method Public Sub Delete(ByVal item As Integer) Dim n As RBTNode n = FindFirst(item) If n IsNot Nothing Then n.bolIsDeleted = True Else

End If End Sub

Public Function FindFirst(ByVal item As Integer) As RBTNode Dim current As RBTNode = root While (current.Left.data > 0 AndAlso item < current.Left.data) Or (current.right.data > 0 AndAlso item >= current.right.data) If item < current.data Then current = current.Left Else current = current.right End If

End While

If current.data = item Then Return current Else

Console.WriteLine(" Target number: " & item & " is not in the tree.") Return Nothing End If

End Function

'By level traversal Dim q As New Queue

Public Sub Bylevel(ByVal root As RBTNode)

If Not root.bolIsDeleted Then Console.Write(root.data & " " & "color: " & root.color & "| ") If Not (root.parent Is Nothing) Then Console.Write("parent: " & root.parent.data) End If Console.WriteLine() End If If root.Left IsNot Nothing Then q.Enqueue(root.Left) End If If root.Right IsNot Nothing Then q.Enqueue(root.Right) End If

If q.Count > 0 Then Bylevel(q.Dequeue) Else Exit Sub End If

End Sub
End Class