Add AVL trees #47

Ghost · 2017-02-27T02:29:01Z

ghost commented

2017-02-27 02:29:01 +00:00

(Migrated from github.com)

This adds the AVL tree data structure and abstracts treeset and treemap to use a new tree interface abstraction. The AVL tree satisifes the interface and the existing RBT implementation has been converted. RBT is still the default tree implementation but treeset.NewWithTree and treemap.NewWithTree will create a sets and maps with a tree implementation of your choice.

If you run the AVL benchmarks, you will see that--as should be expected--AVL tends to be slightly faster on Get (it's generally more balanced), faster on Put (max one rotation is needed on insertions), and much slower on Remove (multiple rotations may be necessary).

This adds the AVL tree data structure and abstracts treeset and treemap to use a new tree interface abstraction. The AVL tree satisifes the interface and the existing RBT implementation has been converted. RBT is still the default tree implementation but treeset.NewWithTree and treemap.NewWithTree will create a sets and maps with a tree implementation of your choice. If you run the AVL benchmarks, you will see that--as should be expected--AVL tends to be slightly faster on Get (it's generally more balanced), faster on Put (max one rotation is needed on insertions), and much slower on Remove (multiple rotations may be necessary).

emirpasic commented

2017-03-03 21:53:02 +00:00

(Migrated from github.com)

@spewspews Awesome! I was busy the last few months, so I finally got some free time this weekend to manage these pull requests. Thanks for contributing, I will merge this branch into development first and test and fix documentation from there before merging into master.

ghost commented

2017-03-03 23:03:14 +00:00

(Migrated from github.com)

@emirpasic Let me know if you have any questions I'd be happy to help out or revise anything.

👍 1

emirpasic (Migrated from github.com) reviewed

2017-03-03 23:52:18 +00:00

trees/avltree/LICENSE

				`@ -0,0 +1,13 @@`
				`Copyright (c) 2017 Benjamin Scher Purcell <[email protected]>`

@spewspews is it OK with you if I append this license file into the root licence?

Copyright (c) 2015, Emir Pasic
All rights reserved.

Redistribution and use in s...

-------------------------------------------------------------------------------

AVL Tree

Copyright (c) 2017 Benjamin Scher Purcell <[email protected]>

Permission to use, copy, modify, and distribute this software...

@spewspews is it OK with you if I append this license file into the [root licence](https://github.com/emirpasic/gods/blob/master/LICENSE)? ``` Copyright (c) 2015, Emir Pasic All rights reserved. Redistribution and use in s... ------------------------------------------------------------------------------- AVL Tree Copyright (c) 2017 Benjamin Scher Purcell <[email protected]> Permission to use, copy, modify, and distribute this software... ```

emirpasic (Migrated from github.com) reviewed

2017-03-03 23:55:57 +00:00

trees/binaryheap/binaryheap.go

					
				@ -24,3 +24,4 @@

					var _ containers.Container = (*Heap)(nil)

				}

				// Heap holds elements in an array-list

What's the reason for making this a container? The Tree interface is anyways simply a Container, no additional methods provided.

emirpasic (Migrated from github.com) reviewed

2017-03-03 23:56:46 +00:00

sets/treeset/iterator.go

					
				@ -8,3 +8,3 @@

					"github.com/emirpasic/gods/containers"

					rbt "github.com/emirpasic/gods/trees/redblacktree"

					"github.com/spewspews/gods/trees"

				)

I will change this to reference this repo as to keep the zero-dependencies policy if that's OK

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:06:01 +00:00

trees/redblacktree/redblacktree.go

				`@ -46,17 +47,27 @@ type Node struct {`

Maybe exposing the Comparator is easier than hiding it an then providing a getter for it? Based on my Java experience, I found getters/setters to be evil.

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:10:49 +00:00

trees/redblacktree/redblacktree.go

					
				@ -235,3 +266,3 @@

					for node != nil {

						compare := tree.Comparator(key, node.Key)

						compare := tree.comparator(key, node.Key)

						switch {

Left() returns this, do you think it would be more obvious to have a duplicate function Min()?

Also I learnt that returning the node rather than key-value pair when working with trees makes more sense, as opposed to maps where you expect the key-value pair.

Left() returns this, do you think it would be more obvious to have a duplicate function Min()? Also I learnt that returning the node rather than key-value pair when working with trees makes more sense, as opposed to maps where you expect the key-value pair.

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:11:46 +00:00

trees/redblacktree/redblacktree.go

Same as above, Right() is the same as Max(). Maybe a duplicate functions isn't too bad? However, I'd appreciate if it returned a node.

Ghost reviewed

2017-03-04 00:12:17 +00:00

trees/avltree/LICENSE

				`@ -0,0 +1,13 @@`
				`Copyright (c) 2017 Benjamin Scher Purcell <[email protected]>`

totally fine

Ghost reviewed

2017-03-04 00:13:07 +00:00

sets/treeset/iterator.go

					
				@ -8,3 +8,3 @@

					"github.com/emirpasic/gods/containers"

					rbt "github.com/emirpasic/gods/trees/redblacktree"

					"github.com/spewspews/gods/trees"

				)

these all need to be changed, but only after this gets merged in. Otherwise it won't build against the current state of the base repo

Ghost reviewed

2017-03-04 00:14:48 +00:00

trees/redblacktree/redblacktree.go

				`@ -46,17 +47,27 @@ type Node struct {`

This is a mistake of mine from an earlier version where I had the new Tree interface have a getter for the comparator in order to make new trees. It can be undone.

Ghost reviewed

2017-03-04 00:15:41 +00:00

trees/binaryheap/binaryheap.go

					
				@ -24,3 +24,4 @@

					var _ containers.Container = (*Heap)(nil)

				}

				// Heap holds elements in an array-list

I modified the tree container to provide sorted binary tree specific functionality in order to abstract the tree that is used by bidimap, treemap, treeset, etc.

Ghost reviewed

2017-03-04 00:16:36 +00:00

trees/redblacktree/redblacktree.go

Left and right are basically non-abstracted versions. I figured that the bidiset, treeset, treemap that use the tree interface wouldn't want to know about nodes. They just care about their keys and values. Feel free to change any way you want.

Ghost reviewed

2017-03-04 00:16:59 +00:00

trees/redblacktree/redblacktree.go

					
				@ -235,3 +266,3 @@

					for node != nil {

						compare := tree.Comparator(key, node.Key)

						compare := tree.comparator(key, node.Key)

						switch {

Totally up to you and see below.

Ghost reviewed

2017-03-04 00:18:25 +00:00

trees/redblacktree/redblacktree.go

If we go with returning a node, then we need to create a node interface that can be used by the maps and sets that use the abstracted tree interface. Perhaps not worth the price of abstraction?

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:22:50 +00:00

trees/trees.go

					
				@ -16,0 +21,4 @@

					Keys() []interface{}

					Min() (interface{}, interface{})

					Max() (interface{}, interface{})

I see now why you wanted to make the binary heap a container, so the others can implement the interface.

However, I think that binary heap is still a tree conceptually and should stay that way despite it's internal implementation that has no notion of nodes.

Also forcing an Iterator() function on all trees makes it a harder job to implement a new tree. These features should be implemented bit-by-bit, a tree, then an iterator, then perhaps an enumerable, etc. but not all at once. Having this strict interface would make contributors life hard and, as seen with the binary heap, not all trees adhere to a key-value logic, some are only values.

I see now why you wanted to make the binary heap a container, so the others can implement the interface. However, I think that binary heap is still a tree conceptually and should stay that way despite it's internal implementation that has no notion of nodes. Also forcing an Iterator() function on all trees makes it a harder job to implement a new tree. These features should be implemented bit-by-bit, a tree, then an iterator, then perhaps an enumerable, etc. but not all at once. Having this strict interface would make contributors life hard and, as seen with the binary heap, not all trees adhere to a key-value logic, some are only values.

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:27:39 +00:00

trees/redblacktree/redblacktree.go

I agree that adding too many layers of abstraction is not that great, but maps can simply work with key-values, whereas nodes are more intrinsic to trees.

We can add the Min()/Max(), I honestly have nothing against duplication, especially if somebody might find those easier to think of than of Left/Right.

I agree that adding too many layers of abstraction is not that great, but maps can simply work with key-values, whereas nodes are more intrinsic to trees. We can add the Min()/Max(), I honestly have nothing against duplication, especially if somebody might find those easier to think of than of Left/Right.

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:29:25 +00:00

trees/binaryheap/binaryheap.go

					
				@ -24,3 +24,4 @@

					var _ containers.Container = (*Heap)(nil)

				}

				// Heap holds elements in an array-list

Yeah, I realized that towards the end, so I left another comment below in Tree interface.

emirpasic (Migrated from github.com) reviewed

2017-03-04 00:36:02 +00:00

trees/avltree/avltree.go

					
				@ -0,0 +319,4 @@

					s.c[a] = rotate(-c, s.c[a])

					p := rotate(c, s)

					if r.p != p || s.p != p {

						panic("doublerot: bad parents")

This should not happen or am I missing something? :/

Ghost reviewed

2017-03-04 00:42:51 +00:00

trees/avltree/avltree.go

					
				@ -0,0 +319,4 @@

					s.c[a] = rotate(-c, s.c[a])

					p := rotate(c, s)

					if r.p != p || s.p != p {

						panic("doublerot: bad parents")

You are not missing anything. It will never happen. Feel free to remove it but I always shy to leaving those things in.

Ghost reviewed

2017-03-04 00:46:59 +00:00

trees/trees.go

					
				@ -16,0 +21,4 @@

					Keys() []interface{}

					Min() (interface{}, interface{})

					Max() (interface{}, interface{})

I agree. Then redblacktree and avltree will satisfy the interface say OrderedTree and keep Tree the same as container? And then treeset/treemap etc. will have an OrderedTree as its backing store?

Ghost reviewed

2017-03-04 00:48:36 +00:00

trees/redblacktree/redblacktree.go

To be honest, I have felt pretty ambivalent about the whole abstraction thing. In my opinion, at this point I'm leaning more towards just keeping treeset/treemap/bidimap using a redblacktree and not an interface. If someone wants to use the avltree then they can just build their own thing around it.

Ghost reviewed

2017-03-04 00:50:55 +00:00

trees/trees.go

					
				@ -16,0 +21,4 @@

					Keys() []interface{}

					Min() (interface{}, interface{})

					Max() (interface{}, interface{})

See my comment above about how I am feeling about abstraction.

emirpasic (Migrated from github.com) reviewed

2017-03-04 01:02:35 +00:00

trees/redblacktree/redblacktree.go

I've only quickly scanned through the code, it looks good. Howerver it's 2AM overhere. bedtime, so I will play with this branch tomorrow and add the documentation/examples to the README and wrap it up into master. Definitely a nice addition to gods, so good job! :)

Ghost reviewed

2017-03-04 01:52:46 +00:00

trees/redblacktree/redblacktree.go

Have a good night! Let me know what you want to do with keeping the abstraction layer. I think it's silly at this point and if you agree then I will just back those changes out. Avltree would simply be a stand-alone container and nothing else would change. Alternatively if you want to keep the abstraction, then I agree we should make an OrderedTree that redblacktree and avltree will implement and I don't mind making that change either.

Sign in to join this conversation.

No reviewers