TAILIEUCHUNG - 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

• Kỹ thuật lập trình
• Data structures
• Cấu trúc dữ liệu
• Binary search trees
• Dictionary data type
• Retrieving data
• Binary tree
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Red black trees
• Splay trees
• Dynamic programming