Mane I finally started going over leetcode problems about trees. Trees are not fun. There are so many kinds. But the resource that helped me was AVL Trees and B trees.
Notes:
- I learned about trees today: A lot of problems can be done with recursion but if you want it to be done faster than you need an iterative solution which usually requires a stack or a queue
- AVL trees are BSTs with a built in rule of being balanced. To be balanced, an AVL tree rotates a sub tree or a branch/swaps nodes until the tree becomes balanced.
- Red/black does the same thing but also colors the nodes of the tree red and black to balance it better from the get go. There are certain rules it must follow when a node gets added. Can't have reds in a row, the root must be black, null nodes must be black, the path from a root to each leaf must pass the same amount of blacks. (Root doesn't count as one, but a null node does count as a leaf and a black to be passed)
- B Trees or B and 2B-1 trees are nodes that have more than one value and more than one child node. The ratio of the values to children are b/(2b-1). For 2/3 its a left node which is less than both values, a middle node which is between two values, and a right which is greater than two values.
No comments:
Post a Comment