llrb-stats.go

// Copyright 2010 Petar Maymounkov. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package llrb

// GetHeight() returns an item in the tree with key @key, and it's height in the tree
func (t *LLRB) GetHeight(key Item) (result Item, depth int) {
	return t.getHeight(t.root, key)
}

func (t *LLRB) getHeight(h *Node, item Item) (Item, int) {
	if h == nil {
		return nil, 0
	}
	if less(item, h.Item) {
		result, depth := t.getHeight(h.Left, item)
		return result, depth + 1
	}
	if less(h.Item, item) {
		result, depth := t.getHeight(h.Right, item)
		return result, depth + 1
	}
	return h.Item, 0
}

// HeightStats() returns the average and standard deviation of the height
// of elements in the tree
func (t *LLRB) HeightStats() (avg, stddev float64) {
	av := &avgVar{}
	heightStats(t.root, 0, av)
	return av.GetAvg(), av.GetStdDev()
}

func heightStats(h *Node, d int, av *avgVar) {
	if h == nil {
		return
	}
	av.Add(float64(d))
	if h.Left != nil {
		heightStats(h.Left, d+1, av)
	}
	if h.Right != nil {
		heightStats(h.Right, d+1, av)
	}
}