Modern OrderedMap BlackHeight

Home › OrderedMap › OrderedMap and OrderedSet › OrderedMap.BlackHeight

OrderedMap.BlackHeight

Returns the tree's black height, or -1 if its balancing rules are broken.

Syntax

BlackHeight( ) as int32

Examples

#import "std/containers"
using containers

dim m as OrderedMap( of integer, ustring )
for i as integer = 1 to 10
    m.Put( i, "v" & i )
next

'' The number of black nodes on any root-to-null path, or -1 if the
'' paths disagree -- which is precisely the red-black invariant that a
'' broken rebalance breaks.
if m.BlackHeight( ) >= 0 then print "invariant holds"

'' O(n), and nothing in normal use calls it. It lives on the container
'' rather than in the test suite because a type whose correctness rests
'' on an invariant should be able to state whether it holds.

---

Library: OrderedMap and OrderedSet
Category: OrderedMap
Documented under: Members