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.
