Unit 2: Trees Flashcards
n-trees
trees with more than two children
n-tree application
the linux ls command
Binary tree
Tree in which each node has at most two children
Binary Search Tree
Binary tree in which all nodes are ordered from left to right
leaf
node with no children
height
- length of longest path from root to leaf
- start from bottom when determining height
depth
length from root to specific node
max number of nodes formula
2^(h+1) - 1
when is a tree full?
when its at its maximum capacity for its height
when is a tree complete?
when each node has either zero or two children and the leaves are ordered from left to right with no gaps
PostOrder traversal
Left, Right, Print
InOrder traversal
Left, Print, Right
Sequential Trees
efficiently storing a tree onto a disc
Less efficient way of representing a BT as a sequential tree
PreOrder traversal while representing null links with a /
More efficient way of representing a BT as a sequential tree
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
n-tree representation on a sequential tree
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
when is a tree balanced?
when the height of a nodes left and right children differ by no more than 1
AVL Tree
a BST that remains balanced upon inserting and deleting nodes
Rules for AVL Tree
- Find the lowest OOB node
- perform either a single or double rotation depending on the situation
when to perform a single rotation
when the new item does NOT fall between the lowest OOB node and its descendant on the out of balance path
single rotation
bring the OOB node’s child up
when to perform a double rotation
when the new item FALLS between the lowest OOB node and its descendant on the OOB path
double rotation
bring OOB node’s grandchild up, then relink any left or right children of the grandchild properly in the BST
Binary Expression
tree in which operands make up the leaves and operators make up all other nodes.
Splay tree
a BST that moves each node accessed to the root node
What happens when your grandparent is a zig-zag or zag-zig away
perform a double rotation like AVL
what happens when your grandparent is a zig-zig or zag-zag away
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
What happens when you do not have a grandparent
simply move the accessed node up and keep the tree ordered
Union
just like a struct but holds only one active value
Why does a BET use a union?
so each node can hold either an operand or an operator at one time
what is the runtime of a single zig-zag or zag-zig?
O log (n)
what is the average runtime to splay a tree completely?
O ( M log n ) where M = average # of steps to amortize
Binary Expression Tree
Postfix Notation expressed as a Expression Tree
how to evaluate a postfix expression
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
how to convert to postfix
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
how to convert postfix to BET
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
least number of leaves
1
most number of leaves
n/2
