Join Simon Allardice for an in-depth discussion in this video Understanding binary search trees (BST), part of Foundations of Programming: Data Structures.
- View Offline
…When we talk about the specific kind of binary tree called the binary search…tree, there are a few more important terms we need to be comfortable with.…Now with a binary tree, there cannot be any…more than two immediate child nodes under one node.…Now, a node could certainly have two child nodes, which…themselves each have two child nodes, which themselves each have…two child nodes, and so on and so on ad…infinitum, or at least until you run out of memory.…But those are the restrictions.…In a binary tree, a node can have a zero child nodes,…in which case it's a leaf, or a one, or a two.…
Why this limitation?…Well, for one thing, it gives us clarity.…We know that in a binary tree, any node…object can only contain two links, two references to children.…It won't contain some arbitrary array of links, maybe one,…maybe 14, maybe 574 child nodes we have to iterate over.…No, just two.…And in a binary search tree node, those two links have specific names.…They are the left child and the right child.…It may help to think about it this…
Starting with simple ways of grouping data like arrays and structs, together you'll explore gradually more complex data structures, like dictionaries, sets, hash tables, queues and stacks, links and linked lists, and trees and graphs. Simon keeps the lessons grounded in the real world and answers the "why" behind many data-structuring decisions: Why use a hash table? Why is a set useful? Why avoid arrays? When you're finished with the course, you'll have a clear understanding of data structures and understand how to use them in whatever language you're programming in, today or 5 years from now.
- What is a data structure?
- Using C-style structs and arrays
- Sorting and searching arrays
- Working with singly and doubly linked lists
- Using stacks for last-in, first-out (LIFO) structures
- Using queues for first-in, first-out (FIFO) structures
- Working with hash tables
- Understanding binary search trees (BSTs)
- Learning about graphs