Final Flashcards
How many root nodes does a tree have?
One
A _____ consists of a collection of nodes connected by directed arcs.
Tree
A node that points to one or more other nodes…
Parent
What are the nodes that are pointed to?
Children
How many parents does every node have? (except root node)
One
What are nodes with no children
Leaf nodes
What are the nodes with children called?
Interior nodes
What are nodes that have the same parent?
Siblings
Consists of its children, and their children, and so on…
Descendants
A _____ rooted at a node consists of that node and all of its descendants.
Subtree
A path’s _____ is equal to the number of arcs traversed.
Length
A node’s _____ is equal to the maximum path length from that node to a leaf node.
Height
A leaf node has a height of…
0
The height of a tree is equal to…
The height of the root.
A node’s _____ is equal to the path length from the root to that node.
Depth
How many children can a node have?
Two
For a Full Binary Tree, every internal node has _ children.
2
For a Full Binary Tree, every leaf is at the same _____.
Depth
What is the height of nodes for a Full Binary Tree?
2^h+1 - 1
What is the height of leaves for a Full Binary Tree?
2^h
Write the structs for a Tree?
struct Node
{
TYPE val;
struct Node *left;
struct Node *rght;
};
structBSTree
{
struct Node *root;
int cnt;
};
If the tree is reasonably full, what is the search time for an element?
O(n)
Returns elements in sorted order.
In-order traversal
Write the implementation:
void add(struct BSTree *tree, TYPE val);
void add(struct BSTree *tree, TYPE val)
{
tree->root = _addNode(tree->root, val);
tree->cnt++;
}
Write the implementation:
struct Node *_addNode(struct Node *cur, TYPE val);
struct Node *_addNode(struct Node *cur, TYPE val)
{
struct Node *newNode;
if(cur == NULL)
{
newnode = malloc(sizeof(struct Node));
assert (newnode != 0);
newnode->val = val;
newnode->left = newnode->right = 0;
return newnode;
}
if (val val)
cur->left = _addNode(cur->left,val); else cur->right = _addNode(cur->right, val); return cur;
}
Write the implementation:
void initBST(struct BinarySearchTree *tree);
void initBST(struct BinarySearchTree *tree)
{
tree->size = 0;
tree->root = 0;
}
Write the implementation:
void addBST(struct BinarySearchTree *tree, TYPE newValue)
void addBST(struct BinarySearchTree *tree, TYPE newValue)
{
tree->root = _nodeAddBst(tree->root, newValue);
tree->size++;
}
Write the implementation:
int sizeBST (struct binarySearchTree *tree)
int sizeBST (struct binarySearchTree *tree)
{
return tree->size;
}
Write the implementation:
struct node * _nodeAddBST (struct node *current, TYPE newValue)
struct node * _nodeAddBST (struct node *current, TYPE newValue)
{
struct Node *node;
if (current == 0) {
node = (struct Node *)malloc(sizeof(struct Node));
assert (node != 0);
node->value = newValue;
node->left = node->right = 0;
return node;
}
if (LT(newValue, current->value))
current->left = _addNode(current->left, newValue);
else current->right = _addNode(current->right, newValue);
return current;
}
Write the implementation:
int containsBST (struct binarySearchTree *tree, TYPE d)
int containsBST (struct binarySearchTree *tree, TYPE d)
{
struct Node *cur = tree->root;
while (cur != 0 ) {
if (EQ(d, cur->value))
return 1 ; /* Return true if value found. */ if (LT(d, cur->value)) cur = cur->left; /* Otherwise, go to the left */ else cur = cur->right; /* or right, depending on val. */
}
return 0 ; /* Return false if not found. */
}
Write the implementation:
void removeBST (struct binarySearchTree *tree, TYPE d)
void removeBST (struct binarySearchTree *tree, TYPE d)
{
if (containsBST(tree, d) {
tree->root = _nodeRemoveBST(tree->root, d); tree->size–;
}
}
Write the implementation:
TYPE _leftMostChild (struct node * current)
TYPE _leftMostChild (struct node * current)
{
while (current->left != 0 )
current = current->left;
return current->val;
}
Write the implementation:
struct node * _removeLeftmostChild (struct node *current)
struct node * _removeLeftmostChild (struct node *current)
struct Node *node;
if(current->left == 0) {
node = current->right; free(current);
return node;
}
current->left = _removeLeftMost(current->left);
return current;
}
Write the implementation:
void _nodeRemoveBST (struct node * current, TYPE d)
void _nodeRemoveBST (struct node * current, TYPE d)
{
struct Node *node;
if ( LT (val, current->val) == 0 ) { if (current->rght == 0 ) {
node = current-> left ; free (current); return node; /* Found value. */
}
current->val = _leftMost(current->rght);
current->rght = _removeLeftMost(current->rght); }
else if ( LT (val, current->val) 0 )
current-> left = _removeNode(current-> left , val);
else current->rght = _removeNode(current->rght, val); return current;
}
Length
The number of arcs
traversed.
Height
The maximum path length from
that node to a left node.
Has Height 0
Leaf Node
Nodes with no
children
Leaf Nodes
Nodes with Children
Interior Nodes
Each node has at most two children. Children are
either left or right.
Binary Tree
We will store our binary trees in instances of
struct Node.
Each node will have a value, and a left and
right child, as opposed to the next and prev pointers of the
DLink.
struct Node {
TYPE value;
struct Node * left;
struct Node * right;
}
4 Traversals
Used to examine every node in a tree in sequence.
Preorder Traversal
Examine a node first, then left children, then right children
Inorder Traversal
Examine left children, then a node, then right children
Postorder Traversal
Examine left children, then right children, then a node
Levelorder
Examine all nodes of depth n first, then nodes depth n+1, etc
Most useful Traversal in practice
Inorder
Euler
tour
Traversal of a tree… Like a walk around the perimeter of a binary tree.
Fast addition of new elements, search time, and removal.
Skip List
Skip Lists
Skip lists are a data structure that can be used in place of balanced trees.
Skip lists use probabilistic balancing rather than strictly enforced balancing
and as a result the algorithms for insertion and deletion in skip lists are
much simpler and significantly faster than equivalent algorithms for
balanced trees.
Skip Lists
Skip lists are linked lists that allow you to skip to the correct node. The performance bottleneck inherent in a sequential scan is avoided, while insertion and deletion remain relatively efficient. Average search time is O (lg n ). Worst-case search time is O ( n ), but is extremely unlikely.
Disadvantage of Skip List
The one disadvantage of the skip list is that it uses about twice as much memory as needed by the
bottommost linked list.
Binary Search Tree
A binary search tree is a binary tree that has the following additional property: for each node, the values in all descendants to the left of the node are less than or equal to the value of the node, and the values in all descendants to the right are greater than or equal.
Height-balanced binary tree
–Depth of all leaf nodes differ by at most 1
–With height h, contains between 2 h -1 and 2 h nodes
Full BInary Tree
A binary tree in which all of the leaves have the same height and every internal node has two childeren
Complete Binary Tree
a full tree up to the second last level with the last level of leaves being filled in from left to right (if last level is completely filled, the tree is full)
height h –> between 2^(h-1) and 2^h - 1 nodes
Binary Search Tree (BST)
- For each node in tree
- All data in left subtree is less
- All data in right subtree is greater Does not allow for duplicates
- If necessary add “or equal to” to ONE of above lines Shape doesn’t matter - can be anywhere from full to linear
balanced tree
a tree in which the height of the subtrees are about equal
Provenance
Describes origin history or how that file came to be
Graphs
Comprised of vertices and edges, and represent relationships and/or connections
Vertices (or Nodes)
Represent objects, states, positions or placeholders.
Each vertex is unique -> no two vertices represent object/state.
Edges (or Arcs)
Edge between two vertices indicates they are connected and neighbors
Can be either directed or undirected
Can be either weighted or unweighted
Adjacency Matrix
Representation of a graph with O(V^2) Space. Weights can be included or not
By Convention, a vertex is usually connected to itself (but not always)
Edge List
Representation graph with O(v+e) space. Weights can be included or not.
Stores only the edges > More space efficient for sparse graph
More of a list than a matrix (like the adjacency matrix)
depth-first search
algorithm for searching a tree, tree structure, or graph
starts at root and explores as far as branches before backtracking
Breadth-first search
Used with a queue, process start node, put all the neighbors on the queue which are processed before any other nodes. Neighbors of neighbors are then processed.
Traits of depth first search
Like a single person working a maze
Can take the wrong route and have to backtrack multiple times
May get lucky and find shortest route very quickly OR May get stuck going down an infinite path
Traits of breadth first search
Like a wave flowing through a maze
May not find goal quickly, but will always find it
Because it checks length 1, then 2, then 3, guaranteed to find shortest path (if it exists)
BFS will never get stuck on an infinite path
Dijkstra’s Algorithm
Given start vertex, graph and goal. Explores nodes in cost order. Records total cost to point at node, edge travelled to arrive. Overwrites these if arrived at again with smaller cost.
Open list initially start node, closed list initially empty.
Terminates when open list is empty. Start at goal and traverse back along edges.
