erriapo / redblacktree

A self-balancing binary search tree in golang
http://godoc.org/github.com/erriapo/redblacktree
Apache License 2.0
8 stars 5 forks source link

InorderVisitor is specific to keys being of int type #3

Open erriapo opened 10 years ago

erriapo commented 10 years ago

Renamed it to be IntInorderVisitor ? Create one for string keys ?

erriapo commented 6 years ago

When testing redblacktree with string keys, the InorderVisitor 's output was not optimal.

From https://play.golang.org/p/dd1Z9U90JJ

values := []string{"d", "b", "g", "g", "c", "e", "a", "h", "f", "i", "j", "l", "k"}
data := []string{"delta", "bravo", "golang", "golf", "charlie", "echo", "alpha", "hotel", "foxtrot", "india", "juliett", "lima", "kilo"}
for i, v := range values {
  t.Put(Key{v}, data[i])
}
inorder := &rbt.InorderVisitor{}; t.Walk(inorder)
fmt.Printf("tree = %s\n", inorder)

The suboptimal output:

tree = ((((.{%!d(string=a)}.){%!d(string=b)}(.{%!d(string=c)}.)){%!d(string=d)}(.{%!d(string=e)}(.{%!d(string=f)}.))){%!d(string=g)}((.{%!d(string=h)}.){%!d(string=i)}((.{%!d(string=j)}.){%!d(string=k)}(.{%!d(string=l)}.))))