Binary Trees

You know... apparently nobody's done Binary Trees for JASS.

I'm thinking Self Balancing BSTs and regular Binary Trees would actually be quite useful.

Self Balance BST for sorted data and very fast sorting
Binary Trees for AI and more complex linked list

What do you guys think?

Do you have an immediate use for them? Like, were you already looking for them because you were thinking of using them in a specific resource? If not, I remain sceptical.

The usefulness of binary trees depends on the performance compared to hashtable..
And like every other jass data structure which doesnt use hashtable/GC we would again be limited by JASS's array limit of 8190...

Well, I had a need for them so I wrote what I needed from scratch and I'm like, wow, could use this for efficient sorting and AI.

Also I try to stay away from hashtables as much as possible =), and I'm not sure exactly how a hashtable would do the same thing as a binary tree ><.

both are used to store <key, value> pairs ?
.. i.e. attaching some data (value) to some object (key)..

I mean to say not sure what a hashtable has to do with a BST

Please don't spread this mental illness to others.

I'm just an efficiency freak, and if you are iterating through data and what not, it's much better to store that data into an array. Hashtables only use for me is an associative array for most handle ids and type ids ^_^.


c'mon, you're talking to a guy that tries to squeeze out every ounce of performance until there's nothing left to squeeze, aka dec loops vrs inc loops, inlining, array read vrs native (player[0] vrs Player(0)), and etc, lol.


So, can we get back on topic?

So, I believe that the self balancing BST would be extremely useful for a lots of forms of archiving as well as storing sorted data (player votes, etc?), Hell, it'd probably beat out leaderboards too because I bet they just do a bubble sort (lazy lazy bliz, I always say they do the worst possible thing I can think of at the time ^_^).


The regular binary tree (with an inserted condition if if Vexorian ever does modules that take parameters, which he said he'd do some day o-o) would be incredibly useful for AI : D. Not only would it make AI easier to program and read, but it'd make it run faster ;o.



So these are some of the reasons I think doing a self balancing BST module, a self balancing binary tree, and a binary tree would be really useful o-o.

there is virtually no performance gain for most of the things you've listed, in lining is good, but takes nothing returns nothing perform almost the same as inlined snippets. for(...){} was only slightly faster then for(...){DoNothing();} I'm assuming that has something to do with the fact that there is no heap allocation for parameters or something.
The hashtables natives are really good, only about twice as slow as array access. Using a hashtable as array is inadvisable [except for in jass land where you want gigantic arrays], but swearing off hashtables is silly.

There are data structures for the right job. If you have a fixed number of elements that you need to traverse, use an array, if you have an arbitrary number and you don't need random access, use a linked list, if you need associativity use a an associative array.

You are completely wrong if you think they would use a bubble sort, probably for the small amount of data they use insertion sort.


There isn't much need for a b-tree. A leaderboard has at most 16 entries in it, so you can just do selective swapping when you want to rearrange things. Can you think of a good reason for one?

AI can't access a lot of common.j functionality, and so its hard to say if you want to use it.

>AI can't access a lot of common.j functionality, and so its hard to say if you want to use it.

in-game AI.... /cough

>You are completely wrong if you think they would use a bubble sort, probably for the small amount of data they use insertion sort.

Blizzard sarcastic comment since some of JASS2 is so lazily done in the background ;o

>There are data structures for the right job. If you have a fixed number of elements that you need to traverse, use an array, if you have an arbitrary number and you don't need random access, use a linked list, if you need associativity use a an associative array.

Uh huh... but nobody's done something for easy Binary Trees, which was the point of this thread.

>The hashtables natives are really good, only about twice as slow as array access. Using a hashtable as array is inadvisable [except for in jass land where you want gigantic arrays], but swearing off hashtables is silly.

Again I'm personally a performance freak and only use hashtables when they are completely necessary (hashing huge numbers, hence name hashtable).

>there is virtually no performance gain for most of the things you've listed, in lining is good, but takes nothing returns nothing perform almost the same as inlined snippets. for(...){} was only slightly faster then for(...){DoNothing();} I'm assuming that has something to do with the fact that there is no heap allocation for parameters or something.

Uh... I personally like to have my maps run as well as possible and my resources as well as possible. If something can be improved, I improve it. The idea of good enough doesn't fit well in the world of programming ; ).

>There isn't much need for a b-tree. A leaderboard has at most 16 entries in it, so you can just do selective swapping when you want to rearrange things. Can you think of a good reason for one?


A binary tree sort is a lot faster than a selective swapping sort......

Its only faster when the data set gets large. There's a reason for things like adaptive qsort (on small sets use insertion sort, on big sets use quick sort). because usually the overhead just isn't worth it. For a mostly sorted set of 16 elements [leaderboards tend to be mostly sorted] you can get away with selective swapping and insertion, vs the overhead of removing and re-adding to a btree. Again what is a good concrete warcraft 3 reason to use one? You can write one, no one will stop you and provided you write it in Zinc or VJass it can join my dictionary and hashset in submission limbo.

No literally, the DoNothing() example won in some of my trials. It wasn't just good enough.

Jesus4lyf implemented something like this if I remember correctly, but even he couldn't find a good use.

I don't really get this... A leaderboard is generally pretty much sorted once it's set up. Why wouldn't they use bubble sort? Bubble sort should be efficient enough if the list has a low level of "unsortedness".