tailieunhanh - Lecture Data structures and other objects using C++ - Chapter 10b: Binary search trees

One of the tree applications in chapter 10 is binary search trees. In chapter 10, binary search trees are used to implement bags and sets. This presentation illustrates how another data type called a dictionary is implemented with binary search trees. | One of the tree applications in Chapter 10 is binary search trees. In Chapter 10, binary search trees are used to implement bags and sets. This presentation illustrates how another data type called a dictionary is implemented with binary search trees. Binary Search Trees This lecture shows a common application of binary trees: Binary Search Trees used to implement a dictionary data type. Before this lecture, students should have a good understanding of binary trees, and should have seen some basic container data types similar to a dictionary (for example, a bag or a set). The Dictionary Data Type A dictionary is a collection of items, similar to a bag. But unlike a bag, each item has a string attached to it, called the item's key. This lecture shows how to use a binary tree to implement an abstract data structure called a dictionary. We'll start by explaining what a dictionary is, without any reference to trees. Then we will show how the trees can be used to actually implement a dictionary. It's important to realize that trees are but one possible way to implement a dictionary, and the actual explanation of "What is a dictionary?" will not refer to trees at all. In other words, a dictionary is an abstract data type, and the trees are one of the mechanisms that can be used to implement the dictionary. So, what is a dictionary? In many ways it is like other ADTs that you have seen, such as a bag which contains a collection of items. The difference is that each item in a dictionary is attached to a string called the item's key. The Dictionary Data Type A dictionary is a collection of items, similar to a bag. But unlike a bag, each item has a string attached to it, called the item's key. Example: The items I am storing are records containing data about a state. For this example, each item that I'm putting in the dictionary is a record which contain a bunch of geographical information about a state. The Dictionary Data Type A dictionary is a collection of items, similar | One of the tree applications in Chapter 10 is binary search trees. In Chapter 10, binary search trees are used to implement bags and sets. This presentation illustrates how another data type called a dictionary is implemented with binary search trees. Binary Search Trees This lecture shows a common application of binary trees: Binary Search Trees used to implement a dictionary data type. Before this lecture, students should have a good understanding of binary trees, and should have seen some basic container data types similar to a dictionary (for example, a bag or a set). The Dictionary Data Type A dictionary is a collection of items, similar to a bag. But unlike a bag, each item has a string attached to it, called the item's key. This lecture shows how to use a binary tree to implement an abstract data structure called a dictionary. We'll start by explaining what a dictionary is, without any reference to trees. Then we will show how the trees can be used to actually implement a .