• # Data Structures for Pre-College Programmers: Trees and Heaps

General and Gameplay Programming

• Posted By frob

# Tree Data Structures

Trees of data are very useful for many things. Since we are a game development site, one of the most common uses of tree data structures is to subdivide space, allowing the developer to quickly find objects that are nearby without having to check every object in the game world. Even though tree data structures are fundamental to computer science, in practice most standard libraries do not directly include tree-based containers. I'll cover the reasons for that in the details.

# The Basic Tree

A tree is, well, a tree. A real life tree has a root. It has branches. And at the end of the branches it has leaves. A data structure tree starts at a root node. Each node can branch off into child nodes. If a node has no children, it is called a leaf node. When you have more than one tree, it is called a forest. Here is an example of a tree. They are generally drawn upside down from real life trees; the root node is usually drawn at the top, and the leaves are usually drawn at the bottom. One of the first questions to ask is: How many children should a node have? Many trees have up to two child nodes. These are called binary trees. The example above is a binary tree. Usually the children are called the left and right child nodes. Another common type of tree in games has four child nodes. A quadtree, which is a tree that can be used to cover a grid, will usually call the child nodes by the direction they cover: NorthWest or NW, NorthEast or NE, SouthWest or SW, and SouthEast or SE. Trees are used in many algorithms. You have already heard about binary trees. There are balanced trees and unbalanced trees. There are red-black trees, AVL trees, and many more. While the theory of a tree is nice, it suffers from some major flaws: Storage space and access speed. What is the best way to store a tree? The most basic route, simply building a linked list, is also one of the worst cases you can construct. Let's assume you want to build a balanced binary tree. You start out with this data structure:  // Tree node Node* left; Node* right; sometype data;  Fair enough. Now let's assume you want to store 1024 items in it. So for 1024 nodes you will need to store 2048 pointers. That's fine, pointers are small and you can live with the tiny space. You may recall that every time you allocate an object it consumes a small amount of additional resources. The exact amount of extra resources depends on the libraries your languge is using. Many popular compilers and tools can use the wide range from just a few bytes to store the data on the small end up to using several kilobytes of padding to help with debugging on the large end. I have worked with systems where even the smallest allocation required 4KB of memory; in this case the 1024 items would require about 4MB of memory. It usually isn't that bad, but the overhead of lots of tiny objects allocated individually will add up quickly. Next, the speed issue. Processors like it when things are right next to each other in memory. Modern processors have a piece of very fast memory --- the cache --- that usually works really well for most data. Whenever a program needs one piece of data the cache will load up that item and also all the items next to it. When something isn't loaded in the very fast memory --- called a cache miss --- it will pause the program until the data is loaded. The most direct format where every tree item is stored in its own little bucket of memory means that nothing is next to each other. Every time you travel across the tree you end up stalling your program. So if making a tree directly has these problems, we should consider a data structure that acts like a tree but doesn't have the problems. Which brings us to...

# The Heap

Just to be confusing, there are two kinds of heap. One is the memory heap. It is a huge block of memory where objects live. That is not the kind of heap I am writing about. A heap data structure in concept is the same as a tree. It has a root node, each node has child nodes, and so on. A heap adds constraints that it must always be sorted in a special way. You will need to provide a sorting function --- usually the less than operator. When objects are added or removed from a heap the structure shuffles itself to be a "complete" tree, where every level in the tree is full, except for possibly the last row where everything must be pushed on one side. This makes storage space and searches on a heap very efficient. Heaps can be stored in an array or a dynamic array so there is little space wasted per allocation. C++ provides functions such as push_heap() and pop_heap() to help you implement heaps on your own containers. Java and C# do not provide similar functionality in their standard libraries. Here are a tree and a heap with the same information:

# Why They Are Not In Standard Libraries

These are basic, fundamental, very useful data structures. Many people believe they should be included in standard libraries. A few seconds on your favorite search engine will find thousands of implementations of trees. It turns out that while trees are very useful and fundamental, there are better containers out there. There are more complex data structures that have the benefits of a tree (stability and shape) and the benefits of a heap (space and speed). The more advanced data structures are generally a combination of data tables coupled with lookup tables. The two tables combined will allow fast access, fast modification, and will perform well in both dense and sparse situations. They don't require shuffling items around when items are added or removed, and they don't consume excess memory or fragment memory after extended use.

# Conclusion

It is important to know about the tree data structures since you will rely on them many times in your career. Also important is that using these data structures directly has a few drawbacks. You can implement your own tree structures, just be aware that more compact representations exist. So why did I cover these if they aren't really used in standard libraries? They are used as the internals to the next topic: NEXT: Non-Linear Data Structures

Report Article

## User Feedback

Simple and well written.  The only question I have is if the discussion of memory and speed is really appropriate for the level of the writing?  I know it is important to get to and also leads to the heap structure but it just seems a little out of place.  Still giving it a thumbs up either way.. :)

##### Share on other sites

Where is Stacks and Queues tutorial? IT seems it's missing?

##### Share on other sites

Where is Stacks and Queues tutorial? IT seems it's missing?

Looks like the admins pushed them out in the wrong order.  Just wait a few days and it will show up.

##### Share on other sites

Where is Stacks and Queues tutorial? IT seems it's missing?

Looks like the admins pushed them out in the wrong order.  Just wait a few days and it will show up.

Can't wait for it ;D Very good articles, btw ;)

##### Share on other sites

Nice article :)

Found a little mistake I figured I'd point out:

"A heap adds constraints that it must always be sorted in a special way."

It'd sound a lot better if you removed the 'it', but then it'd still sound like you're saying the constraints themselves will be sorted in a special way.

Perhaps something like this would make more sense:

"A heap can have constraints that make it sort the data in a special way."

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 0
• 4
• 0
• 0
• 0

• 13
• 12
• 15
• 11
• 12
• ### Similar Content

• By Geonamic
In my turn-based, RPG game, Forsaken Alchemy, I plan to have voiced character monologues and dialogues play along with some character animations after every battle, and I'd like to hear your thoughts on if wording is presented to be realistic in speech patterns, how all the characters sound in personality, if they sound similar in personality to each other, and any feedback on anything. There are in-battle criteria to trigger certain quotes more often than others, but I won't bore you with them. I just wanted to put that out in case you were curious how the below criteria matters in probability.
Every quote in the solo quotes spoiler box is an instance of the character having a monologue. It's not him/her saying every single quote after one battle, so RNG will decide which of the listed solo quotes will play alone after a battle. For example,
"Yes! I won!"
and
"That was easy!"
are randomly picked per battle. The person is not saying, "Yes! I won! That was easy!"
Solo quotes:
When there's an empty line of space between dialogue, that means the next line is the start of a new dialogue. For the example below, after the second quote from Alvis is a different instance of dialogue that plays if RNG picks that to be played instead of the previous instance.
Alvis: “I wish I knew even half as much knowledge that you know.”
Victoria: “In time, you will.”
Alvis: “That’s a pretty optimistic view.”
Victoria: “For a scholar, you did well in that fight.”
Alvis: “I’m just lucky I got out of it with everything intact.”
Victoria: “You should be more confident about your keen strategies.”
Group quotes:

• By CodyOrr4
Hey everyone I am looking for JAVA DEVELOPERS & WEB DEVELOPERS! 🤓
Project Summary:
Basic Requirements: (you'll be further tested once established)
Why do I need a web developer?:
CONTACTS:

• Hello all,
I'm almost to launch a live education platform for game dev enthusiasts (Think a Live Udemy Course) to either learn or teach. It will be a closed group where only members can enter these live sessions. I'm hoping to help new game professionals gain a name and followers by directly teaching/interacting with others instead of only making videos and tutorials, and newbies to have live access to an expert instead of having to wait for his comment replies. We haven't launched yet but we are at the stage of looking for teachers who wish to join us on the beta launch of this project. Only 5 will be selected for the beta test so if you are interested in helping us achieve this or have further questions before anything please email me at andi.mi@outlook.com, well set up a live session to talk.

Cheers,

Andi

• Our children's app Abigail's Tales: First Day Butterflies is free to download this week on the iOS Store.
If your child enjoys our app please leave a review.

• By MiTi
Dear everyone, this is my newest game, please check out and give me feedback. Thanks for your consideration.

Overview: Cross n Puzz is a creative and addicting word puzzle game. It not only challenges your brain but also improve memory and other types of cognitive function.

For IOS: https://itunes.apple.com/app/crossword-puzzle-image/id1435575074