not completely the same
Monday, March 8, 2021
avl trees , red black trees - built-in balancing mechanisms
algorithms for shifting while inserting or deleting built in to keep binary tree "logarithmic in height" rather than "linear in height"
inserting into a balanced binary tree is indeed big O of logn , but that depends on the prerequisite of you keeping the binary search tree balanced
source: cs50
Data structures comparison - arrays, linked lists, hash tables, tries
Arrays:
- insertion is bad - lots of shifting to fit an element in the middle (except for inserting at the end of the array, anywhere other than the end of the array is not so great)
- deletion is bad - lots of shifting after removing an element (except for deleting from the end of the array, unless we don't care about leaving empty gaps, which we usually don't want)
- lookup is great - random access, constant time
- relatively easy to sort
- relatively small size-wise
- stuck with a fixed size, no flexibility
Linked lists:
- insertion is easy - just tack onto the front
- deletion is easy - once you find the element
- lookup is bad - have to rely on linear search
- relatively difficult to sort - unless you are willing to compromise on super-fast insertion and instead sort as you construct
- relatively small size-wise
Hash tables:
- insertion is a two-step process - hash, and then add
- deletion is easy - once you find the element
- lookup is on average better than with linked lists because you have the benefit of a real-world constant factor
- not an ideal data structure if sorting is the goal - just use an array
- can run the gamut of size
source: harvard cs50 david malan
what is the running time of inserting into a binary search tree?
big O of logn
things related to binary search are often big O of logn
if you have a well-balanced binary tree, if it has a total of n nodes, then log-based-2-of-n will be the height of the tree
source: harvard, cs50, david malan
Subscribe to:
Posts (Atom)