36686088
Description
Mind Map by camilo reina pacheco, updated more than 1 year ago
|
Created by camilo reina pacheco
almost 2 years ago
|
|
Data Structure
- Binary trees
- Definition
- Binary trees are data structures very similar
to doubly linked lists, in the sense that they
have two pointers that point to other
elements, but they do not have a linear or
sequential logical structure like those, but
branched. They look like a tree, hence their
name.
- A binary tree is a nonlinear data
structure in which each node can
point to one or at most two nodes. A
recursive definition is also usually
given that indicates that it is a
structure composed of a data and two
trees.
- Features
- Balance
- The distance of a node from the root determines how
efficiently it can be located. For example, given any node
in a tree, its children can be accessed by following only
one path. of forks or branches, the one that leads to the
desired node. Similarly, nodes in the level2 of a tree can
only be accessed by following two branches of the tree.
- The distance of a node from the root determines how
efficiently it can be located. For example, given any node
in a tree, its children can be accessed by following only
one path. of forks or branches, the one that leads to the
desired node. Similarly, nodes in the level2 of a tree can
only be accessed by following two branches of the tree.
- Complete binary trees
- A complete binary tree of depths is a tree in which
for each level, from 0 to level n-1, has a full set of
nodes, and all leaf-level nodes do not occupy the
lowest positions. left wing of the tree.
- A complete binary tree of depths is a tree in which
for each level, from 0 to level n-1, has a full set of
nodes, and all leaf-level nodes do not occupy the
lowest positions. left wing of the tree.
- Operations on binary trees
- Some of the typical operations
performed on binary trees are as
follows:
- Determine your height. Determine your number of
elements. Make a copy. Display the binary tree on the
screen or on the printer. Determine if two binary trees
are identical. Delete(remove the tree). If it is an
expression tree evaluate the expression
- Determine your height. Determine your number of
elements. Make a copy. Display the binary tree on the
screen or on the printer. Determine if two binary trees
are identical. Delete(remove the tree). If it is an
expression tree evaluate the expression
- Some of the typical operations
performed on binary trees are as
follows:
- TAD Binary Tree
- The binary tree structure constitutes an
abstract data type; the basic operations that
define the TAD binary tree are as follows:
- Data type Data that is stored in the nodes of the tree.
Operations CreateTree Initializes the tree as empty. Build
Creates a tree with a root element and two branches, left and
right that sounds like trees.
- Data type Data that is stored in the nodes of the tree.
Operations CreateTree Initializes the tree as empty. Build
Creates a tree with a root element and two branches, left and
right that sounds like trees.
- The binary tree structure constitutes an
abstract data type; the basic operations that
define the TAD binary tree are as follows:
- Balance
- Features
- Binary trees are data structures very similar
to doubly linked lists, in the sense that they
have two pointers that point to other
elements, but they do not have a linear or
sequential logical structure like those, but
branched. They look like a tree, hence their
name.
- Definition
- Graph
- Definition
- A graph is a composition of a set of
objects known as nodes that are related
to other nodes through a set of
connections known as edges.
- Graphs allow us to study the
relationships that exist between
units that interact with others.
- important
concepts
- A graph in its entirety is an ordered
pair composed of vertices (v) and
edges (e); where in the vast majority
of cases the vertices are finitely
quantized.
- The number of vertices that make
up the graph are what we know as
order
- There is also the concept of degree that corresponds to
the number of arcs to which they belong externally
and as for the edges we also get the concept of a loop
that is nothing more than an edge related in various
ways to the same node.
- A graph in its entirety is an ordered
pair composed of vertices (v) and
edges (e); where in the vast majority
of cases the vertices are finitely
quantized.
- important
concepts
- Features
- directed graph
- A directed graph, also known as a digraph,
consists of a set of vertices and edges where
each edge is unidirectionally associated
through an arrow with another.
- The edges, depending on their output or input, receive the
qualification of incoming or outgoing, the common
condition is that they always have a destination towards a
node.
- The edges, depending on their output or input, receive the
qualification of incoming or outgoing, the common
condition is that they always have a destination towards a
node.
- A directed graph, also known as a digraph,
consists of a set of vertices and edges where
each edge is unidirectionally associated
through an arrow with another.
- Undirected graph
- Undirected graphs are those that consist of a
set of vertices that are connected to a set of
edges in a non-directional way.
- This means that an edge can be
traversed from any of its points and
in any direction.
- This means that an edge can be
traversed from any of its points and
in any direction.
- Undirected graphs are those that consist of a
set of vertices that are connected to a set of
edges in a non-directional way.
- Labeled graphs
- This classification is called labeled graphs or
directed graphs with weights. This type of
graphs concentrate edges that may have
additional information where we can reflect
names, costs, values or other data.
- These graphs are also called activity networks and the
number associated with the arc is called the weight
factor. This graph is the one we most commonly use to
represent real-life situations.
- These graphs are also called activity networks and the
number associated with the arc is called the weight
factor. This graph is the one we most commonly use to
represent real-life situations.
- This classification is called labeled graphs or
directed graphs with weights. This type of
graphs concentrate edges that may have
additional information where we can reflect
names, costs, values or other data.
- directed graph
- A graph is a composition of a set of
objects known as nodes that are related
to other nodes through a set of
connections known as edges.
- Definition
- vertex in a graph
- Definition
- A graph consists of a finite set of points called vertices and a finite
set of edges, each of which connects two vertices. I know
- Topological ordering
- One of the applications of graphs is to model the relationships that exist
between the different tasks, milestones, that must be completed to
conclude a project. Among the tasks there are precedence relationships: a
task precedes the task if it needs to be completed to be able to start
- These precedence relationships are represented by a directed graph
in the that the vertices are the tasksohitosythere is an edge of the
vertexeratsi the start of the taskt depends on the termination der.
Once the graph is available, it is interesting to obtain a planning of
the tasks that constitute the project; in short, to find the topological
arrangement of the vertices that form the graph.
- Algoritmo de una
ordenación topológica
- The algorithm first looks for a vertex (a task) with no
predecessors or prerequisites; that is, it has no input
arcs. This vertex, v, becomes part of the order T; a
Then all arcs leaving v are removed, since the
prerequisite v is already has satisfied.
- The strategy is repeated: another vertex is taken without
incident arcs, it is incorporated sorting Tyse removes all
the arcs that come out of it, so on until complete the
ordination.
- Implementation of the
sorting algorithm
topological
- The coding of the algorithm depends on the representation of the
graph, with adjacency matrix adjacency lists. If the graph has
relatively few edges, the matrix of adjacency has many zeros and so
the graph is represented by adjacency lists
- In the case of dense directed graphs, for
efficiency, the matrix of adjacency.
Regardless of the representation, a Queue
is used to store the vertices with degree of
input 0
- In the case of dense directed graphs, for
efficiency, the matrix of adjacency.
Regardless of the representation, a Queue
is used to store the vertices with degree of
input 0
- The coding of the algorithm depends on the representation of the
graph, with adjacency matrix adjacency lists. If the graph has
relatively few edges, the matrix of adjacency has many zeros and so
the graph is represented by adjacency lists
- The strategy is repeated: another vertex is taken without
incident arcs, it is incorporated sorting Tyse removes all
the arcs that come out of it, so on until complete the
ordination.
- The algorithm first looks for a vertex (a task) with no
predecessors or prerequisites; that is, it has no input
arcs. This vertex, v, becomes part of the order T; a
Then all arcs leaving v are removed, since the
prerequisite v is already has satisfied.
- These precedence relationships are represented by a directed graph
in the that the vertices are the tasksohitosythere is an edge of the
vertexeratsi the start of the taskt depends on the termination der.
Once the graph is available, it is interesting to obtain a planning of
the tasks that constitute the project; in short, to find the topological
arrangement of the vertices that form the graph.
- One of the applications of graphs is to model the relationships that exist
between the different tasks, milestones, that must be completed to
conclude a project. Among the tasks there are precedence relationships: a
task precedes the task if it needs to be completed to be able to start
- A graph consists of a finite set of points called vertices and a finite
set of edges, each of which connects two vertices. I know
- Definition
- References
- https://elibro.net/es/ereader/uniminuto/50117
- https://elibro.net/es/ereader/uniminuto/50117
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.