The binary search tree is defined by the fact that it's binary, so that means it has at most two children at each node. Binary search tree is a very common type of a tree used in computer science. In our case, we just have one argument x. The procedure call, the left child is the name of the procedure, and subsequent children are the arguments to that procedure. The assignment statement, the left child is the variable we're assigning to, which is x, and the right child is an expression, in this case, x+2. And in those blocks, we have two different statements, an assignment statement and a procedure call. And then the statement to execute, well, it's actually multiple statements so we have a block. So the condition is x less than 0, so comparison operation, the variable x and the constant 0. And the children of the while loop are the condition that needs to be met for the while loop to continue and then the statement to execute. So we reflect that at the top, we have while, which is our while loop. While x is less than 0, x is x+2, f of x. So in order to represent code, we will do that with an abstract syntax tree. ![]() We also use trees in computer science for code. And then within each of these, we have various subcategorizations. This is part of it where we've got animals, and then below that, different types of animals, so invertebrates, reptiles, mammals, and so on. Another example of a hierarchy is the animal kingdom. So we've got, for the case of the United States, states, and then within those states, cities. And then below that, various subcomponents of the geography. And then below that, entities in the world, United States, all sorts of other things, United Kingdom. So this reflects hierarchy of geography where we have at the left hand side the top level of the hierarchy, the world. Trees are also used to reflect hierarchy. So from the bottom, you would first do 3 times z, and then you would subtract 7 from that, you'd apply the sine to that, and then you multiply that by 2. So this shows again the structure of the expression and the order in which you might evaluate it. Within the sine, what we're applying the sine to is 3z-7, so we have the minus that's happening last with a 7 and then this 3z, 3 times z. So at the top level, we have a multiplication, that's really the last thing that's done, multiplying the 2 and the sine. We can look here at a syntax tree for an expression 2sin(3z-7), we can break that up into the structure. So along the bottom of the tree, we have the words from the sentence, "I ate the cake", and the rest of the tree reflects the structure of that sentence. And the child of the verb phrase is a verb and noun phrase, where the verb is ate, and the noun phrase is a determiner and a noun, the and cake. The child of the noun phrase is the word I from the sentence. So we have at the top of the tree, the S for sentence and then children: a noun phrase and a verb phrase. So it's similar to sentence diagramming that you may have done in grade school. ![]() Now, we're going to look at a syntax tree for that, which shows the structure of the sentence. So here we have a sentence, "I ate the cake". In this lecture, we're going to talk about trees. You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space! View Syllabus What are good strategies to keep a binary tree balanced? How to implement a hash table so that the amortized running time of all operations is O(1) on average?Ĥ. How priority queues are implemented in C++, Java, and Python?ģ. What is a good strategy of resizing a dynamic array?Ģ. You will also learn typical use cases for these data structures.Ī few examples of questions that we are going to cover in this class are the following:ġ. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. In this online course, we consider the common data structures that are used in various computational problems. A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |