itec33 Flashcards
is a pictorial representation of a set of objects where some pairs of objects are connected by links.
graph
The interconnected objects are represented by points
vertices
links that connected the vertices
edges
Each node of the graph is represented as ___
vertex
represents a path between two vertices or a line between two vertices
edge
Two node or vertices are adjacent if they are connected to each other through an edge.
adjacency
represents a sequence of edges between the two vertices.
path
basic primary operations of a graph
add vertex
add edge
display vertex
algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
depth first traversal (dfs)
algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
breadth first traversal (bfs)
represents the nodes connected by edges.
tree
can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of
a value, together with a list of references to nodes (the “children”), with the constraints that
no reference is duplicated, and none points to the root.
tree data structure
refers to the sequence of nodes along the edges of a tree.
path
The node at the top of the tree
root
Any node except the root node has one edge upward to a node called parent.
parent
The node below a given node connected by its edge downward
child
The node which does not have any child node
leaf
represents the descendants of a node.
subtree
refers to checking the value of a node when control is on the node
visiting
means passing through nodes in a specific order.
traversing
represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2,
and so on.
levels
represents a value of a node based on which a search operation is to be carried out for a node.
keys
A node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than its parent value.
binary search tree representation
basic operations in binary search tree data structure
insert
search
preorder traversal
in-order traversal
post-order traversal
process to visit all the nodes of a tree and may print their values too.
traversal
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree.
inorder traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
pre-order traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.
post-order traversal
is a hierarchical data structure in which each node has at most two children generally referred as left child and right child.
binary tree
3 components of nodes
pointer to left subtree
pointer to right subtree
data element
It has a root node and every node has at most two children.
rooted binary tree
It is a tree in which every node in the tree has either 0 or 2 children.
full binary tree
It is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
perfect binary tree
It is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
complete binary tree
A binary tree is height balanced if it satisfies the following constraints:
- The left and right subtrees’ heights differ by at most one, AND
- The left subtree is balanced, AND
- The right subtree is balanced
balanced binary tree
It is a tree is where each parent node has only one child node. It behaves like a linked list
degenerate tree
types of binary tree
rooted
full
perfect
complete
balanced
degenerate
binary search tree operations
search
insert
delete
node with two children rules
in order predecessor
in order successor
