I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This video is part of my first-year Algorithms course.
The Binary Search Tree (BST) is a data structure that implements the Dictionary ADT: you ask for a key and it efficiently finds it, returning the node that contains the sought key and the associated satellite data. Additionally, given a node, it can find the node with the next key in the order, or the one with the previous key. It can also find the nodes with the smallest or the largest key in the data structure. All of these operations can be performed in time bounded by the height of the tree.
In this video we explain how to perform all of these operations and also how to delete a node from a BST while preserving the BST properties.
Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.
Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithms/
Course handout:
https://www.cl.cam.ac.uk/teaching/2021/Algorithms/2020-2021-stajano-algs-handout.pdf
My home page:
http://frank.stajano.com
Add comment