Trees general Flashcards
Binary tree
A tree where each node has at most two children
pre-order traversal
Process the root, followed by the left subtree, then the right subtree
In-order traversal
Process the left subtree, followed by the root, then the right subtree
Post-order traversal
Process the left subtree, followed by the right subtree, then the root
Complexity of most simple operations on a binary tree - best case
O(log(N)) - Tree is even/balanced
Complexity of most simple operations on a binary tree - worst case
O(N) - Tree devolves into a list
Binary search tree (BST)
Binary tree where for each element, elements less than it are in its left subtree, and elements greater than it are on its right subtree
AVL tree
A BST where the balance factor is between -1 and 1
Demonstrate a left rotation on a tree
Answer text intentionally blank
Demonstrate a right rotation on a tree
Answer text intentionally blank
How would an AVL be rebalanced if an outer subtree is larger?
Preform a rotation towards the center
How would an AVL be rebalanced if an inner subtree was larger?
Rotate away from center on that side’s child, then towards center on itself.
