Sorry your browser is not supported!

Basically what the title says. Whats the use of binary trees and linked lists? Linked lists I sort of understand, using pointers to go through a bunch of classes or structs, but binary trees are weird. Why do you need a smaller value than the parent on the left child and an equal or greater value on the right child (or is my tutorial not making sense)? What would you use a binary tree for, anyway? Thanks.

Sounds like you're talking about binary search trees. They're useful for implementing sets. You could use a linked list, but finding a value takes a while of searching. You could use an ordered array and do a binary search (same basic principle behind it), but not expandable. Binary search trees are expandable and fast.

Now, for trees in general, lets have an example. Imagine a 3D game, with a complex scene with lots of 3D objects. Now, you can put them in an array, and just loop through it and update each object as needed. If, for example, an object is too far away, don't draw it. If there are many objects in the same place too far away, you have to loop through all of them to know not to draw them.

Now say you arranged this in a tree form (called a scene graph). You have the root, and its children are say, vehicles and buildings. They might have children too, for instance, the objects that are inside them (players riding vehicles for example). Now imagine you have a building, with lots of objects in it, and you go too far away from it and there's no need to draw it. Using the array model, you have to loop through every object in the building to know not to update it. Using this model, you simply say, "nope, building is too far away, so I won't even bother looking at it or any of it's children". Not only does this save you n loops (n = number of objects in the building), but it also saves you a distance check per loop. That's a lot of efficiency right there!

Yep, I guess you could say I liked trees from the start. [/Shawshank Redemption reference]



[edit]

Perhaps I didn't explain why binary search trees are useful. Ok,, lets say that you want to store a bunch of numbers, for quick lookup. If you use a linked list, you can just add them in order. Now, if you wanna see if a number exists in the list, you have to check the first node, second, third, etc... until you find it. Worst case scenario is that it'll take you n loops (where n is the size of the list). This is called linear complexity, O(n).

Now if you use trees, you can do it a lot faster. Once you check a node (the root for instance), you can check if the number you're looking for is greater or smaller than this one. If it's smaller, search the left 'subtree', otherwise search the right one. This means that every time you take a step, you're essentially halving the amount of data you need to check (unlike linked lists, where the amount you must check stays the same). So, in a linked list with the numbers 1 to 10, you would have to do 9 loops to find the number 9. But with a well balanced binary tree, you only have to do 3 or 4. By halving the amount of data you need to check every time, you get logarithmic complexity, O(log n).

If you think about the graphs of n (essentially y = x) and log n (y = log x), you will see that as x gets greater, y doesn't increase by as much in y = log x, where as with y = x it always increases - it's a straight line, but y = log x curves and flattens off. This is important, because it means you eventually get to a point where you can have a huge amount of data, and it will take just as long to process as it would if you only had say, half of it.

quadratic equations are the most efficient at wasting time

Augmenting what Zotoaster just said, trees are useful for other things, such as collision detection. One way to detect collision in an environment is to check every possible pair of objects for intersection.

This takes O(n²) time, which is far too long. A 1000-object scene would require nearly 500000 comparisons.

By storing the objects in a quadtree (or octree, if you're working in three dimensions), it is easy to locate all nearby objects, without having to even consider distant objects. This takes just O(n log n) time. A linked list can make it even faster, at almost O(n), but uses much more memory.

Union-find operations using linked lists take O(n) time; a binary tree reduces this to O(log n). Using more optimisations, it can be reduced even further to O(alpha(n)). Alpha is the inverse Ackermann function, which is the slowest-growing function encountered in programming, slower than log(), log(log()), or even log*(). Indeed, for all feasible values of n, alpha(n) <= 5, so it is practically as good as O(1) -- constant time.

Although Zotoaster's comments were mostly accurate, there is a slight inaccuracy in his last comment. The y = log(x) function does not flatten off, and there is never a point where doubling x leaves y unchanged. Instead, it increases y by a constant amount. log(1000000) = 20, log(2000000) = 21, and log(4000000) = 22. (Here I have used base 2 for the logarithm function; base e is more commonly used in mathematics.)

Exponential time, O(2^n) is the inverse of logarithmic time, so an exponential-time algorithm is impractically slow. Factorial time is even worse, and occurs in problems such as the Travelling Salesman Problem.

Finally, double-exponential time, such as O(2^(2^n)), is so slow that it shouldn't even be considered.

Thanks for the correction calcy, I was just going by the looks of the graph - you learn something new every day!


For a very real example, look at Sparky's collision DLL. It's famous here for being blindingly fast - but why?

Well, it works a bit like this. Imagine you want to check if a ray intersects an object, in a world filled with 100s or 1000s of objects. Well you might want to check every triangle of every object, but that's just plain dumb. If you put a box around every object, then you know if you don't intersect the box, you can't possibly intersect the object - and checking intersection for a box is very fast.

But if you have a huge object and you tend to be in the box all the time, then the box becomes useless, so, what you can do it split it into two boxes, one for either side. If you only intersect one box, ignore all the other polygons. Well, you can do the same to this box - split it in two, and check only the triangles in the intersected box.

Just keep going down like that until you've reached the last box, and with only a few checks, you have got it down to only having to check a few triangles.

So for a terrain with 100,000 polygons, you can maybe do 5 box checks, and narrow the scope down to 100 triangles. That's 105 checks, rather than 100,000. That's why trees are awesome, and good for the environment.

@Zotoaster I never thought of using a binary tree for something like vehicles and buildings and stuff. Neat idea that seems pretty useful. I also didn't think of the speed boost looking for numbers.
@Mnemonix lol
@calcy Thats a lot of information. You must be pretty smart
It'll take me a while to get it.

Thanks for the responses, guys.