Midterm Flashcards Preview

CS 261 > Midterm > Flashcards

Flashcards in Midterm Deck (48)
Loading flashcards...
1
Q

Length

A

The number of arcs traversed.

2
Q

Height

A

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

3
Q

Has Height 0

A

Leaf Node

4
Q

Nodes with no children

A

Leaf Nodes

5
Q

Nodes with Children

A

Interior Nodes

6
Q

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

A

Binary Tree

7
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 DLink. struct Node { TYPE value; struct Node * left; struct Node * right; }

8
Q

4 Traversals

A

Used to examine every node in a tree in sequence.

9
Q

Preorder Traversal

A

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

10
Q

Inorder Traversal

A

Examine left children, then a node, then right children

11
Q

Postorder Traversal

A

Examine left children, then right children, then a node

12
Q

Levelorder

A

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

13
Q

Most useful Traversal in practice

A

Inorder

14
Q

Euler tour

A

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

15
Q

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

A

Skip List

16
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.

17
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.

18
Q

Disadvantage of Skip List

A

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

19
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.

20
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

21
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

22
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

23
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

24
Q

balanced tree

A

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

25
Q

g

Length

A

The number of arcs traversed.

26
Q

g

Height

A

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

27
Q

g

Has Height 0

A

Leaf Node

28
Q

g

Nodes with no children

A

Leaf Nodes

29
Q

g

Nodes with Children

A

Interior Nodes

30
Q

g

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

A

Binary Tree

31
Q

g

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 DLink. struct Node { TYPE value; struct Node * left; struct Node * right; }

32
Q

g

4 Traversals

A

Used to examine every node in a tree in sequence.

33
Q

g

Preorder Traversal

A

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

34
Q

g

Inorder Traversal

A

Examine left children, then a node, then right children

35
Q

g

Postorder Traversal

A

Examine left children, then right children, then a node

36
Q

g

Levelorder

A

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

37
Q

g

Most useful Traversal in practice

A

Inorder

38
Q

g

Euler tour

A

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

39
Q

g

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

A

Skip List

40
Q

g

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.

41
Q

g

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.

42
Q

g

Disadvantage of Skip List

A

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

43
Q

g

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.

44
Q

g

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

45
Q

g

Full BInary Tree

A

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

46
Q

g

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

47
Q

g

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

48
Q

g

balanced tree

A

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