1. Trees and graphs
In this video, we will study two data structures: trees and graphs.
2. Trees - definition
Let's start by defining trees.
Trees are
node-based data structures where
each node can have links to more than one node.
3. Trees - terminology
The first node of a tree is called the root. A node
4. Trees - terminology
can be the parent
5. Trees - terminology
of other nodes. These nodes are called children.
6. Trees - terminology
Trees have levels. In this tree,
7. Trees - terminology
we have these four levels.
8. Trees - binary tree
Let's introduce a special kind of tree. It is the binary tree. A binary tree is a
tree in which
each node has
zero,
one,
or two children.
9. Trees - binary tree implementation
This code shows the implementation of a TreeNode in a binary tree. With it, we can set the value for the node, the value for the left_child, and the value for the right_child.
We can build a tree like this one with this code.
10. Trees - real uses
Trees have many applications in
storing hierarchical relationships, such as
the file system of a computer,
or the structure of an HTML document. Trees are also used
in chess to store the possible moves that a rival player can make. And in general, trees appear in many
searching and sorting algorithms.
11. Graphs
A graph is a data structure formed by
a set of nodes, also called vertices. The nodes are connected
by links, also called edges. The following graph can represent a social network, where nodes represent persons and edges represent the friendship between the persons.
Trees are a type of graph.
12. Graphs - types
Graphs can be directed
when they have one specific direction. For example,
in this social network, David follows Martin, but Martin doesn't follow David.
13. Graphs - types
Graphs can also be undirected
when their edges have no direction. In this case,
we assume the relationship is mutual.
For example, we can model the friendship between Ben and Daya with undirected links, assuming that both are friends.
14. Graphs - types
Weighted graphs have
numeric values associated with the edges. These graphs
can be either directed or undirected.
The following weighted graph represents the distance between different cities.
15. Graphs vs. trees
Let's see the differences between trees and graphs. Trees
cannot have cycles. It means that the nodes cannot reference each other circularly,
while graphs can have cycles. In a tree,
all the nodes must be connected, while in graphs,
there can be
16. Graphs vs. trees
unconnected nodes.
17. Graphs - real world use-cases
Graphs can represent the user relationships in social networks, like
the friendship between two users,
if a user follows another user,
the likes,
etc. Graphs can also represent
locations and distances between these locations. With this information,
we can optimize the routes.
Graph databases use graphs to store the information that is consumed by lots of applications. As trees,
graphs appear in many searching and sorting algorithms.
18. Graphs - implementation
Graphs can be implemented as follows. The graph will have a dictionary to store all the vertices. Vertices can be added with the add_vertex method, and edges with the add_edge method.
We can build a graph like this one
with this code, using the add_vertex and add_edge methods.
We can print the vertices to check the content. Instead, we can use adjacency matrices, but these last are out of the scope of this course.
19. Let's practice!
Let's get to know trees and graphs better with some exercises!