text: // 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)
  	}
  }
  