failing case for GoLLRB deletion on non-uniquely inserted tree

blackswan.go

package main

import (
	"fmt"
	"github.com/petar/GoLLRB/llrb"
)

func isBalanced(t *llrb.Tree) bool {
	if t == nil {
		return true
	}
	var black int // number of black links on path from root to min
	for x := t.Root(); x != nil; x = x.Left {
		if x.Black {
			black++
		}
	}
	return nodeIsBalanced(t.Root(), black)
}

func nodeIsBalanced(n *llrb.Node, black int) bool {
	if n == nil && black == 0 {
		return true
	} else if n == nil && black != 0 {
		return false
	}
	if n.Black {
		black--
	}
	return nodeIsBalanced(n.Left, black) && nodeIsBalanced(n.Right, black)
}

func main() {
	blackSwan := []int{1, 1, 1, 0}
	t := llrb.New(func(a, b interface{}) bool { return a.(int) < b.(int) })
	for _, e := range blackSwan {
		t.InsertNoReplace(e)
	}
	for _, e := range blackSwan {
		fmt.Printf("Tree is balanced before deletion: %v\n", isBalanced(t))
		t.Delete(e)
		ok := isBalanced(t)
		fmt.Printf("Tree is balanced after deletion: %v\n", ok)
		if !ok {
			return
		}
	}
}