# Final Flashcards Preview

## CS 261 > Final > Flashcards

Flashcards in Final Deck (69)
1
Q

How many root nodes does a tree have?

A

One

2
Q

A _____ consists of a collection of nodes connected by directed arcs.

A

Tree

3
Q

A node that points to one or more other nodes…

A

Parent

4
Q

What are the nodes that are pointed to?

A

Children

5
Q

How many parents does every node have? (except root node)

A

One

6
Q

What are nodes with no children

A

Leaf nodes

7
Q

What are the nodes with children called?

A

Interior nodes

8
Q

What are nodes that have the same parent?

A

Siblings

9
Q

Consists of its children, and their children, and so on…

A

Descendants

10
Q

A _____ rooted at a node consists of that node and all of its descendants.

A

Subtree

11
Q

A path’s _____ is equal to the number of arcs traversed.

A

Length

12
Q

A node’s _____ is equal to the maximum path length from that node to a leaf node.

A

Height

13
Q

A leaf node has a height of…

A

0

14
Q

The height of a tree is equal to…

A

The height of the root.

15
Q

A node’s _____ is equal to the path length from the root to that node.

A

Depth

16
Q

How many children can a node have?

A

Two

17
Q

For a Full Binary Tree, every internal node has _ children.

A

2

18
Q

For a Full Binary Tree, every leaf is at the same _____.

A

Depth

19
Q

What is the height of nodes for a Full Binary Tree?

A

2^h+1 - 1

20
Q

What is the height of leaves for a Full Binary Tree?

A

2^h

21
Q

Write the structs for a Tree?

A

struct Node
{
TYPE val;

struct Node *left;

struct Node *rght;

};

structBSTree

{

struct Node *root;

int cnt;

};

22
Q

If the tree is reasonably full, what is the search time for an element?

A

O(n)

23
Q

Returns elements in sorted order.

A

In-order traversal

24
Q

Write the implementation:

void add(struct BSTree *tree, TYPE val);

A
```void add(struct BSTree *tree, TYPE val)
{```

tree->cnt++;

}

25
Q

Write the implementation:

struct Node *_addNode(struct Node *cur, TYPE val);

A

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;  `

}

26
Q

Write the implementation:

void initBST(struct BinarySearchTree *tree);

A
```void initBST(struct BinarySearchTree *tree)
{ ```

tree->size = 0;

tree->root = 0;

}

27
Q

Write the implementation:

void addBST(struct BinarySearchTree *tree, TYPE newValue)

A

void addBST(struct BinarySearchTree *tree, TYPE newValue)

{

tree->size++;

}

28
Q

Write the implementation:

int sizeBST (struct binarySearchTree *tree)

A

int sizeBST (struct binarySearchTree *tree)

{

return tree->size;

}

29
Q

Write the implementation:

struct node * _nodeAddBST (struct node *current, TYPE newValue)

A

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))

return current;

}

30
Q

Write the implementation:

int containsBST (struct binarySearchTree *tree, TYPE d)

A

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. */  ```

}

}

31
Q

Write the implementation:

void removeBST (struct binarySearchTree *tree, TYPE d)

A

void removeBST (struct binarySearchTree *tree, TYPE d)

{

if (containsBST(tree, d) {
tree->root = _nodeRemoveBST(tree->root, d); tree->size–;

}

}

32
Q

Write the implementation:

TYPE _leftMostChild (struct node * current)

A

TYPE _leftMostChild (struct node * current)

{

while (current->left != 0 )

`current = current->left;  `

return current->val;

}

33
Q

Write the implementation:

struct node * _removeLeftmostChild (struct node *current)

A

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; `

}

34
Q

Write the implementation:

void _nodeRemoveBST (struct node * current, TYPE d)

A

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;

}

35
Q

Length

A

The number of arcs

traversed.

36
Q

Height

A

The maximum path length from

that node to a left node.

37
Q

Has Height 0

A

Leaf Node

38
Q

Nodes with no

children

A

Leaf Nodes

39
Q

Nodes with Children

A

Interior Nodes

40
Q

Each node has at most two children. Children are

either left or right.

A

Binary Tree

41
Q

We will store our binary trees in instances of

struct Node.

A

Each node will have a value, and a left and

right child, as opposed to the next and prev pointers of the

struct Node {

TYPE value;

struct Node * left;

struct Node * right;

}

42
Q

4 Traversals

A

Used to examine every node in a tree in sequence.

43
Q

Preorder Traversal

A

Examine a node first, then left children, then right children

44
Q

Inorder Traversal

A

Examine left children, then a node, then right children

45
Q

Postorder Traversal

A

Examine left children, then right children, then a node

46
Q

Levelorder

A

Examine all nodes of depth n first, then nodes depth n+1, etc

47
Q

Most useful Traversal in practice

A

Inorder

48
Q

Euler

tour

A

Traversal of a tree… Like a walk around the perimeter of a binary tree.

49
Q

Fast addition of new elements, search time, and removal.

A

Skip List

50
Q

Skip Lists

A

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.

51
Q

Skip Lists

A

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.

52
Q

A

The one disadvantage of the skip list is that it uses about twice as much memory as needed by the

53
Q

Binary Search Tree

A

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.

54
Q

Height-balanced binary tree

A

–Depth of all leaf nodes differ by at most 1

–With height h, contains between 2 h -1 and 2 h nodes

55
Q

Full BInary Tree

A

A binary tree in which all of the leaves have the same height and every internal node has two childeren

56
Q

Complete Binary Tree

A

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

57
Q

Binary Search Tree (BST)

A
• 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
58
Q

balanced tree

A

a tree in which the height of the subtrees are about equal

59
Q

Provenance

A

Describes origin history or how that file came to be

60
Q

Graphs

A

Comprised of vertices and edges, and represent relationships and/or connections

61
Q

Vertices (or Nodes)

A

Represent objects, states, positions or placeholders.

Each vertex is unique -> no two vertices represent object/state.

62
Q

Edges (or Arcs)

A

Edge between two vertices indicates they are connected and neighbors

Can be either directed or undirected

Can be either weighted or unweighted

63
Q

A

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)

64
Q

Edge List

A

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)

65
Q

depth-first search

A

algorithm for searching a tree, tree structure, or graph

starts at root and explores as far as branches before backtracking

66
Q

A

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.

67
Q

Traits of depth first search

A

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

68
Q

A

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

69
Q

Dijkstra’s Algorithm

A

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.