This course is the fourth course in the specialization about learning how to develop video games using the C# programming language and the Unity game engine on Windows or Mac. Why use C# and Unity instead of some other language and game engine? Well, C# is a really good language for learning how to program and then programming professionally. Also, the Unity game engine is very popular with indie game developers; Unity games were downloaded 16,000,000,000 times in 2016! Finally, C# is one of the programming languages you can use in the Unity environment. This course assumes you have the prerequisite knowledge from the previous three courses in the specialization. You should make sure you have that knowledge, either by taking those previous courses or from personal experience, before tackling this course. The required prerequisite knowledge is listed in the "Who this class is for" section below. Throughout this course you'll build on your foundational C# and Unity knowledge by developing more robust games with better object-oriented designs using various data structures and design patterns. Data structures and design patterns are both general programming and software architecture topics that span all software, not just games. Although we'll discuss these ideas in the game domain, they also apply if you're writing a web app in ASP.NET, building a tool using WinForms, or any other software you decide to build. Module 1: Explore a Dynamic Array data structure and learn the basics of algorithm analysis Module 2: Learn about and use the common Linked List and Graph data structures Module 3: Learn about and use several additional data structures: Stacks, Queues, and Trees Module 4: Learn why design patterns are so useful and discover a number of design patterns useful in game development Module 5: Complete final peer review
Tree Analysis
Loading...
From the course by University of Colorado System
Data Structures and Design Patterns for Game Developers
8 ratings
University of Colorado System
8 ratings
Course 4 of 5 in the Specialization C# Programming for Unity Game Development
From the lesson
Stacks, Queues, and Trees
Meet the Instructors
Dr. Tim "Dr. T" ChamillardAssociate Professor
Computer Science
In this lecture,
we'll complete our algorithm analysis on our tree node and tree classes.
We'll start by looking at the AddChild method in the TreeNode class.
The Contains method for a list performs a linear search looking for
the provided argument.
And we know linear searches are order n.
So the question is order n in what?
Well, order n in the number of children that this particular node has.
This line of code is order n, where n is the number of children for the node.
The rest of these things are constant time,
adding a child is order n if in fact we have to expand the list.
And these two are obviously constant time so we have order n here and order n here,
which makes the Add(child) operation and order n operation.
Removing a node, remember our discussion of Contains?
So this is order n in the number of children for the node.
So this is order n, where n is the number of children for the node.
We null out the parent so this is constant time, but
Remove also does a linear search for the node.
So this is order n in the number of children.
And of course, this is constant time.
So we have order n and order n.
But including an order n operation in the side an if statement that has an order
n boolean expression does not mean we need to multiply them together like
we do when we have an order n operation inside a loop that executes n times.
So this is still additive.
So remove child is still order n.
Removing all the children from the node, this loop is clearly order n,
where n is the number of children the node has.
This is constant time and
this is constant time only because we're removing from the end of the list.
So we're avoiding any shifting as we go through the list removing stuff.
So because the loop executes n times, the RemoveAllChilren operation is order n.
And then converting the nodes to a string is also order n in the number
of children because we loop over each child printing out its value.
For the operations in the tree class, we'll start with the clear method, and
let's look at the easy part first.
So the easy part is the second loop that executes n times, and
RemoveAt is constant time because we're removing from the end of the list.
So this chunk of code is order n.
This line is constant time.
So the question is, what about this?
Well, clearly the loop iterates n times where, and
it's the number of nodes in the tree.
This is constant time.
We just talked about RemoveAllChildren as being order n but with the different
definition of n, n was the number of children for that particular node.
So we have to sort of think of this stuff all together.
How many times will we actually remove a child from a parent?
And it turns out that, because each node can only have
a single parent, we're only going to remove n children
in total across all the iterations of this loop.
We're only going to remove n total children inside.
So we don't have to multiply in order n here times n here to get n squared.
It actually turns out that this is order n.
So because this is order n and this is order n and
this is constant time, clear is an order n operation.
To add a node to the tree,
this costs us order n in the number of nodes in the tree.
This caused us order n in the number of children for
the parents node that were adding.
And in the worst case, the parent is the root node and
all of the children are siblings.
They all have the root node as the parent.
So in that worst case,
this would also be order n in the number of nodes in the tree.
Adding a node to the list of nodes is order and if.
We have to expand the list.
And adding a child is order n, where n is the number of
children that the parent has, which in the worst case could be n minus 1 children,
where we have a very shallow tree where the root has all the children.
And nothing goes lower than those children.
So we have a bunch of order ns here, so
the add node operation is order n.
Removing a node, remember is the most complicated method we have in this class.
Luckily to start off with, we have some constant time stuff.
We have order n for Clear.
We have more constant time stuff.
We have order n for removing the child. We have order n for removing the node from
the list of nodes because the list Remove method that does a linear search.
And then we have this interesting recursion stuff.
So everything other than this recursion,
which is to recursively prune the subtree, everything else is order n.
So we can think of everything else as sort of the body of a loop.
It's not really a loop, it's a set of recursions we're going to do but
we're going to do order n stuff on every recursion.
So the question is, how many recursions are we going to do?
And the answer is, in the worst case, we have a tree where every
parent has a single node so this is essentially a linked list.
And so there's no branching out, so in the worst case,
we're trying to remove the node just below the root.
And that means that we're going to have to recurse n minus two times
to get rid of the rest of the nodes.
So the number of recursions is order n and
the complexity of the stuff we do inside each recursion is order n.
So removing a node is actually an order n squared operation.
Finding a particular value in the tree is just a linear search.
So this is order n.
And converting the tree to a string is also order n
because here's where we iterate over all the nodes in the tree.
And that means that we're going to have an order n
conversion to the string, where n is the number of nodes in the tree.
To recap, in this lecture, we got even more practice doing algorithm analysis.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
