blob: 47126a3be967ed21df5a5bd310b96326d0a57bde [file] [log] [blame]
Scott Bakere7144bc2019-10-01 14:16:47 -07001// Copyright 2010 Petar Maymounkov. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package llrb
6
7// GetHeight() returns an item in the tree with key @key, and it's height in the tree
8func (t *LLRB) GetHeight(key Item) (result Item, depth int) {
9 return t.getHeight(t.root, key)
10}
11
12func (t *LLRB) getHeight(h *Node, item Item) (Item, int) {
13 if h == nil {
14 return nil, 0
15 }
16 if less(item, h.Item) {
17 result, depth := t.getHeight(h.Left, item)
18 return result, depth + 1
19 }
20 if less(h.Item, item) {
21 result, depth := t.getHeight(h.Right, item)
22 return result, depth + 1
23 }
24 return h.Item, 0
25}
26
27// HeightStats() returns the average and standard deviation of the height
28// of elements in the tree
29func (t *LLRB) HeightStats() (avg, stddev float64) {
30 av := &avgVar{}
31 heightStats(t.root, 0, av)
32 return av.GetAvg(), av.GetStdDev()
33}
34
35func heightStats(h *Node, d int, av *avgVar) {
36 if h == nil {
37 return
38 }
39 av.Add(float64(d))
40 if h.Left != nil {
41 heightStats(h.Left, d+1, av)
42 }
43 if h.Right != nil {
44 heightStats(h.Right, d+1, av)
45 }
46}