## Binary Search Tree

Average Case Worst Case
Space O(n) O(n)
Insert O(log(n)) O(n)
Delete O(log(n)) O(n)
Search O(log(n)) O(n)

Trees Traversal:

• In-order Traversal: left -> root -> right
• Pre-order Traversal: root -> left -> right
• Post-order Traversal: left -> right -> root

## AVL Tree

AVL trees and red-black trees are guaranteed to be balanced, so O(log(n)) is guaranteed.

Average Case Worst Case
Space O(n) O(n)
Insert O(log(n)) O(log(n))
Delete O(log(n)) O(log(n))
Search O(log(n)) O(log(n))

Applications

• Databases when deletion or insertion are not so frequent, but have to make a lot of look-ups.
• Red-Black trees are a little bit more popular, as for AVL we have to make several rotations, a little bit slower.

## Red-Black Tree

Average Case Worst Case
Space O(n) O(n)
Insert O(log(n)) O(log(n))
Delete O(log(n)) O(log(n))
Search O(log(n)) O(log(n))

Red-Black tree properties:

• Each node is either red or black
• The root node is always black
• Every red most have two black child nodes and no other children -> it must have a black parent
• Every path from a given node to any of its descendant Null nodes contains the same number of black nodes.

## Tries & Ternary Search Tree

Hash Table VS Tries

• We can replace hash tables with tries, tries are more efficient for search misses
• Hash table the key is going to be converted into an index with the help of the hash function
• Tries, we consider every single character of the key, but we return right when there is a mismatch.
• For tries there is no collision.
• Tries can provide string, so alphabetical ordering of the entries by keys. Hash table does not.
• No hash function needed for tries.

Applications

• Predictive text, auto-complete feature
• Spell checking
0%