## 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

1 | class Node(object): |

## 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.

1 | class Node(object): |

## 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

1 | class Node(object): |