Unit 2: Trees

Question 1

n-trees

Answer 1

trees with more than two children

Question 2

n-tree application

Answer 2

the linux ls command

Question 3

Binary tree

Answer 3

Tree in which each node has at most two children

Question 4

Binary Search Tree

Answer 4

Binary tree in which all nodes are ordered from left to right

Question 5

leaf

Answer 5

node with no children

Question 6

height

Answer 6

• length of longest path from root to leaf
• start from bottom when determining height

Question 7

depth

Answer 7

length from root to specific node

Question 8

max number of nodes formula

Answer 8

2^(h+1) - 1

Question 9

when is a tree full?

Answer 9

when its at its maximum capacity for its height

Question 10

when is a tree complete?

Answer 10

when each node has either zero or two children and the leaves are ordered from left to right with no gaps

Question 11

PostOrder traversal

Answer 11

Left, Right, Print

Question 12

InOrder traversal

Answer 12

Left, Print, Right

Question 13

Sequential Trees

Answer 13

efficiently storing a tree onto a disc

Question 14

Less efficient way of representing a BT as a sequential tree

Answer 14

PreOrder traversal while representing null links with a /

Question 15

More efficient way of representing a BT as a sequential tree

Answer 15

PreOrder traversal with internal nodes being represented with a prime mark, all null links being represented by a / however a leaf’s null links are not represented at all.
- A’ = internal Node
- B = leaf
- / = null link

Question 16

n-tree representation on a sequential tree

Answer 16

convert tree to first child/next sibling implementation, conduct preOrder traversal with all leaf nodes being represented with a ) next to it, as well as ) indicating the end of a child list

Question 17

when is a tree balanced?

Answer 17

when the height of a nodes left and right children differ by no more than 1

Question 18

AVL Tree

Answer 18

a BST that remains balanced upon inserting and deleting nodes

Question 19

Rules for AVL Tree

Answer 19

1. Find the lowest OOB node
2. perform either a single or double rotation depending on the situation

Question 20

when to perform a single rotation

Answer 20

when the new item does NOT fall between the lowest OOB node and its descendant on the out of balance path

Question 21

single rotation

Answer 21

bring the OOB node’s child up

Question 22

when to perform a double rotation

Answer 22

when the new item FALLS between the lowest OOB node and its descendant on the OOB path

Question 23

double rotation

Answer 23

bring OOB node’s grandchild up, then relink any left or right children of the grandchild properly in the BST

Question 24

Binary Expression

Answer 24

tree in which operands make up the leaves and operators make up all other nodes.

Question 25

Splay tree

Answer 25

a BST that moves each node accessed to the root node

Question 26

What happens when your grandparent is a zig-zag or zag-zig away

Answer 26

perform a double rotation like AVL

Question 27

what happens when your grandparent is a zig-zig or zag-zag away

Answer 27

move you're accessed node into the grandparent's slot, attach the nodes traversed directly to the subtree of the accessed nodes. Make sure still BST

Question 28

What happens when you do not have a grandparent

Answer 28

simply move the accessed node up and keep the tree ordered

Question 29

Union

Answer 29

just like a struct but holds only one active value

Question 30

Why does a BET use a union?

Answer 30

so each node can hold either an operand or an operator at one time

Question 31

what is the runtime of a single zig-zag or zag-zig?

Answer 31

O log (n)

Question 32

what is the average runtime to splay a tree completely?

Answer 32

O ( M log n ) where M = average # of steps to amortize

Question 33

Binary Expression Tree

Answer 33

Postfix Notation expressed as a Expression Tree

Question 34

how to evaluate a postfix expression

Answer 34

push operands onto stack, when an operator is found, pop two operands from stack and solve second (operator) first, then push result back onto stack

Question 35

how to convert to postfix

Answer 35

write out numbers, push ( and operators onto stack. If an operator is already at the top of the stack, pop it and apply the new operator if it has equal or higher precedence of the current one. When a ) is seen, push onto stack then pop all operators until ( is popped. When end of input, pop all remaining stack symbols

Question 36

how to convert postfix to BET

Answer 36

turn stack on side and push pointers to operands onto stack, when an operator is found, pop last two pointers and make them children of operator, then push pointer to operator with children onto stack. FIRST OPERAND POPPED BECOMES RIGHT CHILD AND SECOND BECOMES LEFT CHILD

Question 37

least number of leaves

Answer 37

1

Question 38

most number of leaves

Answer 38

n/2