Midterm

Question 1

Length

Answer 1

The number of arcs traversed.

Question 2

Height

Answer 2

The maximum path length from that node to a left node.

Question 3

Has Height 0

Answer 3

Leaf Node

Question 4

Nodes with no children

Answer 4

Leaf Nodes

Question 5

Nodes with Children

Answer 5

Interior Nodes

Question 6

Each node has at most two children. Children are either left or right.

Answer 6

Binary Tree

Question 7

We will store our binary trees in instances of struct Node.

Answer 7

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

Question 8

4 Traversals

Answer 8

Used to examine every node in a tree in sequence.

Question 9

Preorder Traversal

Answer 9

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

Question 10

Inorder Traversal

Answer 10

Examine left children, then a node, then right children

Question 11

Postorder Traversal

Answer 11

Examine left children, then right children, then a node

Question 12

Levelorder

Answer 12

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

Question 13

Most useful Traversal in practice

Answer 13

Inorder

Question 14

Euler tour

Answer 14

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

Question 15

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

Answer 15

Skip List

Question 16

Skip Lists

Answer 16

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.

Question 17

Skip Lists

Answer 17

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.

Question 18

Disadvantage of Skip List

Answer 18

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

Question 19

Binary Search Tree

Answer 19

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.

Question 20

Height-balanced binary tree

Answer 20

–Depth of all leaf nodes differ by at most 1 –With height h, contains between 2 h -1 and 2 h nodes

Question 21

Full BInary Tree

Answer 21

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

Question 22

Complete Binary Tree

Answer 22

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

Question 23

Binary Search Tree (BST)

Answer 23

* 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

Question 24

balanced tree

Answer 24

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

Question 25

# g Length

Answer 25

The number of arcs traversed.

Question 26

# g Height

Answer 26

The maximum path length from that node to a left node.

Question 27

# g Has Height 0

Answer 27

Leaf Node

Question 28

# g Nodes with no children

Answer 28

Leaf Nodes

Question 29

# g Nodes with Children

Answer 29

Interior Nodes

Question 30

# g Each node has at most two children. Children are either left or right.

Answer 30

Binary Tree

Question 31

# g We will store our binary trees in instances of struct Node.

Answer 31

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

Question 32

# g 4 Traversals

Answer 32

Used to examine every node in a tree in sequence.

Question 33

# g Preorder Traversal

Answer 33

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

Question 34

# g Inorder Traversal

Answer 34

Examine left children, then a node, then right children

Question 35

# g Postorder Traversal

Answer 35

Examine left children, then right children, then a node

Question 36

# g Levelorder

Answer 36

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

Question 37

# g Most useful Traversal in practice

Answer 37

Inorder

Question 38

# g Euler tour

Answer 38

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

Question 39

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

Answer 39

Skip List

Question 40

# g Skip Lists

Answer 40

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.

Question 41

# g Skip Lists

Answer 41

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.

Question 42

# g Disadvantage of Skip List

Answer 42

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

Question 43

# g Binary Search Tree

Answer 43

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.

Question 44

# g Height-balanced binary tree

Answer 44

–Depth of all leaf nodes differ by at most 1 –With height h, contains between 2 h -1 and 2 h nodes

Question 45

# g Full BInary Tree

Answer 45

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

Question 46

# g Complete Binary Tree

Answer 46

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

Question 47

# g Binary Search Tree (BST)

Answer 47

\* 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

Question 48

# g balanced tree

Answer 48

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