Binary Search Trees: Samuel's tutorial
Samuel's tutorial on binary search trees (traversals, search, insertion and deletion).
Timestamps:
00:00 - Brief guide to Binary Search Trees
03:23 - Tree traversals
06:41 - Binary Search Tree Queries (minimum, maximum, search)
10:42 - Binary Search Tree Insertion
12:58 - Binary Search Tree Deletion
Detailed description:
This video describes Binary Search Trees, starting with a brief summary of the history of their invention in the late 1950s and early 1960s, their complexity for the operations of search, insert and delete, and the "Binary Search Tree Property" that characterises their structure.
Next, we discuss traversal algorithms: inorder, preorder and postorder traversal, and how each of them can be implemented as a recursive function with linear complexity in the number of nodes.
We then turn to query functions: finding the minimum and maximum node in a subtree, searching for a node with a given key, and finding the inorder predecessor of a given node.
We discuss Binary Search Tree insertion and how it can be implemented in O(h) runtime, where h is the height of the tree.
Finally, we describe the slightly more intricate case of node deletion, focusing on the four cases that must be handled to implement this operation.
Python code for a minimalist implementation can be found here: https://github.com/albanie/algorithms...
Topics: #datastructures #binarysearchtree #coding
Slides (pdf): https://samuelalbanie.com/files/diges...
References for papers mentioned in the video can be found at
http://samuelalbanie.com/digests/2022...
Recommended further reading on this topic:
D. Sheehy, "A First Course on Data Structures in Python", https://donsheehy.github.io/datastruc...
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press. https://mitpress.mit.edu/978026204630...
Knuth, D. E. "The Art of Computer Programming, volume 3: Sorting and Searching", (Second Edition) 1998 https://www-cs-faculty.stanford.edu/~...
Further content from me:
YouTube: / @samuelalbanie1
Twitter: / samuelalbanie