As an example of that, if you had a directory that contained 4.3 billion entries in it, it would take only 32 steps to find any entry in that book. Instead of having to scan each entry, we can just do it in a small number of steps. Like a sorted phone book, binary search trees enable us to find information in considerably less time. That poses a problem for computers because, like a human, if I gave you a randomly sorted phone book, and say, "Find a person in that phone book," it would take you all day. This is useful for finding information by its value.Įxample: You want to find the name of a restaurant. You can create categorization that gets more and more specific through the same hierarchy. You can work backwards and create a tree of your parents, grandparents, and great grandparents. It's binary because it can have a maximum of two ‘children.’ You can think of a tree as an ancestry tree. ![]() In particular, there's a specific type of tree that's used very widely called a binary search tree. You can round up those values together, and then you have a representation of what the user filled out.Ī third useful one is a tree. Each field has a title – like first name and last name – with a corresponding value. Some languages call it an associative array, or a dictionary, or a hash map.Įxample: If you've ever filled out a form online, like creating an account, you enter your first name, last name, email, birthday. Usually, one is called a key and it’s associated with a value. It's essentially an association between two different pieces of information. That's one of the basic ones.Īnother one that's really common for beginners to master is an object. The way you find things in an array is by its positional identifier (eg. a list of book titles, a list of grades, or a list of scores).Įxample: You need a list of alphabetical users for a particular website so that you can look them up by name. Arrays are really just a list of items (eg. And with the internet, we rely on this for everything, including:Īrrays are very common and one of the most fundamental data structures. What are data structures used for?įinding the information associated with what you want to examine is an important process of everyday life. It's not useful to use computers to solve problems of storing six books, but it is useful to use computers to look up millions of books. ![]() ![]() That's what computers are doing with large amounts of information. When you look up a book in a card catalog, signs in the library tell you where that number is located and then you look for the shelf that you would find that number on. If you think about what is happening there, it's all about storage and retrieval of information. So you'd probably rely on some sort of lookup scheme like a catalog which would tell you the approximate area where the book was located. Now, what if you had a large library of books, a thousand books, or a million books that you needed to access quickly? You'd need physical space to house that many books and it would take time to walk around, and find a book.You could lay them out on a table, and within seconds, you could identify the titles and find where they are positionally on your table. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |