31251 Lecture Notes - Lecture 6: Binary Search Algorithm, Binary Tree
30 Jun 2018
School
Department
Course
Professor
Binary Search Trees
Binary Search Trees (BSTs) are a simple data structure that allows fast insertion, removal and
lookup of the elements they store.
They are an ordered data structure, but because they use a binary tree, you don’t have to
reshuffle everything to put something new in. (Unlike array-like data structures, for
example.)
They follow a simple rule to find or insert:
If what you’re looking for (or what you have) has a smaller key than the current vertex, go to
the left. Otherwise, go to the right. (Special case: duplicate keys)
Insertion then is just traversing the tree to the bottom and adding the new element
wherever you stop.
Finding something mimics binary search, if you get to the bottom without finding it, it’s not
there.
Complexity of Binary Search Trees
Operation Average Case Worst Case
Space 0(n) 0(n)
Insert 0(log n) 0(n)
Remove 0(log n) 0(n)
Find 0(log n) 0(n)
At the cost of more complicated code, there are several self-balancing BST data structures which
reduce the worst case insert, remove and find to O (log n): 2-3 Trees, Red-Black Trees, AVL Trees,
Splay Trees and others. (Some material at the end if we have time, or to peruse at your leisure.)
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Binary search trees (bsts) are a simple data structure that allows fast insertion, removal and lookup of the elements they store. They are an ordered data structure, but because they use a binary tree, you don"t have to reshuffle everything to put something new in. (unlike array-like data structures, for example. ) They follow a simple rule to find or insert: If what you"re looking for (or what you have) has a smaller key than the current vertex, go to the left. Otherwise, go to the right. (special case: duplicate keys) Insertion then is just traversing the tree to the bottom and adding the new element wherever you stop. Finding something mimics binary search, if you get to the bottom without finding it, it"s not there. At the cost of more complicated code, there are several self-balancing bst data structures which reduce the worst case insert, remove and find to o (log n): 2-3 trees, red-black trees, avl trees,
