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.