// Validate to validate whether b is a valid red-black tree.
// return true if it's valid, false if it's not match the property of red-black tree.
// NOTE: It's better to set this func only as a test func since it's too complex and low efficiency.
Validate to validate whether b is a valid red-black tree.
return true if it's valid, false if it's not match the property of red-black tree.
NOTE: It's better to set this func only as a test func since it's too complex and low efficiency.
// Validate to validate whether b is a valid red - black tree . // return true if it ' s valid false if it ' s not match the property of red - black tree . // NOTE : It ' s better to set this func only as a test func since it ' s too complex and low efficiency .
func (rb RBTree) Validate() bool {
	if !rb.validateBinarySearchTreeProperties() {
		return false
	}
	if rb.nil().color != rbBlack || rb.nilNode.color != rbBlack {
		return false
	}
	if rb.root.color != rbBlack {
		return false
	}
	nonNilLeaves := []*treeNode{}
	valid := true
	rb.inorderTreeWalkNodes(rb.root, func(node *treeNode) {
		if node.color == rbRed {
			if node.leftChild.color != rbBlack || node.rightChild.color != rbBlack {
				valid = false
			}
		}
		if node.leftChild == rb.nil() && node.rightChild == rb.nil() {
			nonNilLeaves = append(nonNilLeaves, node)
		}
	})
	if !valid {
		return false
	}
	nonLeafNodesBH := map[*treeNode]int{} 
	for _, v := range nonNilLeaves {
		node := v.parent
		currBh := 0
		if v.color == rbBlack {
			currBh++
		}
		for node != rb.nil() {
			bh, ok := nonLeafNodesBH[node]
			if !ok {
				nonLeafNodesBH[node] = currBh
			} else {
				if bh != currBh {
					return false
				}
			}
			if node.color == rbBlack {
				currBh++
			}
			node = node.parent
		}
	}
	return true
}
func ( rb RBTree ) Validate ( ) bool { if ! rb . validateBinarySearchTreeProperties ( ) { return false } if rb . nil ( ) . color != rbBlack || rb . nilNode . color != rbBlack { return false } if rb . root . color != rbBlack { return false } nonNilLeaves := [ ] * treeNode { } valid := true rb . inorderTreeWalkNodes ( rb . root , func ( node * treeNode ) { if node . color == rbRed { if node . leftChild . color != rbBlack || node . rightChild . color != rbBlack { valid = false } } if node . leftChild == rb . nil ( ) && node . rightChild == rb . nil ( ) { nonNilLeaves = append ( nonNilLeaves , node ) } } ) if ! valid { return false } nonLeafNodesBH := map [ * treeNode ] int { } for _ , v := range nonNilLeaves { node := v . parent currBh := 0 if v . color == rbBlack { currBh ++ } for node != rb . nil ( ) { bh , ok := nonLeafNodesBH [ node ] if ! ok { nonLeafNodesBH [ node ] = currBh } else { if bh != currBh { return false } } if node . color == rbBlack { currBh ++ } node = node . parent } } return true }
Validate to validate whether b is a valid red-black tree.
Validate to validate whether b is a valid red - black tree .
//0. First of all, it should be a binary search tree //1. Every node is either RED or BLACK. // Don't need to verify. //2. Every nil node is BLACK. //5. The root node is always BLACK. //3. Every RED node has two BLACK child nodes. //4. Every path from node x (calculte without x) down to leaf node(must be rb.nil()) has the same number of BLACK nodes. //black-high for non-leaf nodes //calculate each non-leaf node's black-high until root, // start from each non-nil-leaf node