func validateRedBlackTree(n *redBlackNode) (int, error) {
	if n == nil {
		return 1, nil
	}
	var err error
	if isRed(n) && (isRed(n.left) || isRed(n.right)) {
		err = errors.New(fmt.Sprint("red violation at node key ", n.key))
		return 0, err
	}
	leftHeight, err := validateRedBlackTree(n.left)
	if err != nil {
		return 0, err
	}
	rightHeight, err := validateRedBlackTree(n.right)
	if err != nil {
		return 0, err
	}
	if n.left != nil && n.left.key.Compare(n.key) >= 0 ||
		n.right != nil && n.right.key.Compare(n.key) <= 0 {
		err = errors.New(fmt.Sprint("binary tree violation at node key ", n.key))
		return 0, err
	}
	if leftHeight != 0 && rightHeight != 0 {
		if leftHeight != rightHeight {
			err = errors.New(fmt.Sprint("black height violation at node key ", n.key))
			return 0, err
		}
		if isRed(n) {
			return leftHeight, nil
		}
		return leftHeight + 1, nil
	}
	return 0, nil
}
counts the black height of the tree and validates it along the way
package hashring
import (
	"errors"
	"fmt"
	"math/rand"
	"strconv"
	"testing"
	"github.com/stretchr/testify/assert"
)
type treeTestInt int
func (t treeTestInt) Compare(other interface{}) int {
	return int(t) - int(other.(treeTestInt))
}
func makeTree() redBlackTree {
	tree := redBlackTree{}
	tree.Insert(treeTestInt(1), "one")
	tree.Insert(treeTestInt(2), "two")
	tree.Insert(treeTestInt(3), "three")
	tree.Insert(treeTestInt(4), "four")
	tree.Insert(treeTestInt(5), "five")
	tree.Insert(treeTestInt(6), "six")
	tree.Insert(treeTestInt(7), "seven")
	tree.Insert(treeTestInt(8), "eight")
	return tree
}
func TestEmptyTree(t *testing.T) {
	tree := redBlackTree{}
	assert.Nil(t, tree.root, "tree root is nil")
	assert.Equal(t, 0, tree.Size(), "tree has 0 nodes")
}