Trees Flashcards
Tree height
- length of longest path from node to leaf
- leaves have height zero
tree Depth
length of the path from the root to that node
Internal path length
sum oof the depths of all the nodes
Preorder/ inorder/postorder
preorder = node left right
in order = left node right
postorder = right left node
BST
- nodes have at most 2 kids
- all nodes in left subtree are less than key
- all nodes in right are greater
The maximum number f nodes in a binary tree of height h is
2^h+1 -1
Worst case depth for a n-node BST is
n-1
Meaning that the data was already sorted beforehand
AVL Tree
Keeps track of a balancing factor/height attribute, whereby the height of the left and right subtrees differs at most by one
AVL trees can hit -3 or 3 bf
false
Rotations in slides!
yeah!
Runtime of find, insert, remove and print in AVL tree?
All log n except print, which is always linear
Red-black trees
- each node has a color attribute, red or black
- the root is black
- leaves are black
- both children of every red node are black
- every simple path from a node to any descendant leaf has the same number of black nodes
RB tree vs AVL tree
- AVL are more rigidly balanced and require more rotations sometimes
- Red black are slightly faster
Splay tree
- self balancing tree that keeps recently used nodes close to the top
- improves performance for finding values
- great for cache data storage techniques
- easier to implement than other trees
- every find/insert/delete, you splay the tree around that node
- splay is Omega(h) height
Amortized
averaged over time! AVL as good amortized and not amortized, meaning O(log n).
Splay tree has good amortized but not actual runtime.
When to use trees?
- aren’t sorted
- less complexity, like a stack or queue
- constant time operations on attributes/retrieves
