CSC148H1 F SLOG
Monday 18 November 2013
Sunday 3 November 2013
Binary Search Tree Delete
A binary search tree is an ordered tree, where the left child must only contain values smaller than the root and the right child must contain only values larger than the root. This makes searching for values in the tree much more efficient. Instead of potentially having to look at every single node to find some value, you simply compare it to the root. This means the number of comparisons you need to make is equivalent to the depth of the tree where that value is or would be if it were in the tree.
When deleting a value from a binary search tree, there are three cases to account for. The first, and simplest case is deleting a leaf (that is, a node with no children). When deleting a leaf, all you have to do is find that value in the tree, remove it and then replace it with an empty node. The second case is deleting an internal node with one child. This case requires finding and removing the value and then replacing it with its own child, where replacing it refers to giving its parent a new left or right. The final, and most complicated case, involves deleting an internal node with 2 children. In this case, you need to make sure you are replacing it with a value that is higher than everything on the left side and lower than everything on the right side. You are left with two options for what to do. You may either replace the node with the highest value on the left side, or with the lowest value on the right side. In class we learned to replace the node with the maximum node on the left side, because we had already defined a function which would return the maximum node in a tree. However, this is not the only way.
I can't say which method is better, because they appear to be about equivalent.
When deleting a value from a binary search tree, there are three cases to account for. The first, and simplest case is deleting a leaf (that is, a node with no children). When deleting a leaf, all you have to do is find that value in the tree, remove it and then replace it with an empty node. The second case is deleting an internal node with one child. This case requires finding and removing the value and then replacing it with its own child, where replacing it refers to giving its parent a new left or right. The final, and most complicated case, involves deleting an internal node with 2 children. In this case, you need to make sure you are replacing it with a value that is higher than everything on the left side and lower than everything on the right side. You are left with two options for what to do. You may either replace the node with the highest value on the left side, or with the lowest value on the right side. In class we learned to replace the node with the maximum node on the left side, because we had already defined a function which would return the maximum node in a tree. However, this is not the only way.
I can't say which method is better, because they appear to be about equivalent.
Sunday 27 October 2013
Built-in __repr__ and Internal Functions
__repr__ not __str__
This past week, we learned about a built-in function which was, to me, entirely new. It was presented to us in class under the heading "prefer repr to str" as follows:repr is supposed to provide explicit information about an object and is returned when the class object itself is meant to be returned and str is what you want returned when print() is called on it. However, as we learned in lecture, repr acts as the substitute for str when no str method is defined for that class. So, classes should always have a repr method, whereas str is optional.
Internal functions
We also learned about defining functions under other function headers. At first this seemed like an entirely useless technique especially when the instructor mentioned that it is very hard to access the internal function individually from elsewhere. But, I made sure to clear up my conclusion and the answer I received was that a function with a generic name doing almost identical tasks might be required in many different functions in a file. This way, these internal functions can share a name yet have a slightly different implementation, which could be a very useful tool for programmers coding complicated classes.Monday 21 October 2013
The Thing About Recursion
Recursive data structures
Over the past few lectures, we've learned about different types of recursive data structures, mainly trees and linked lists. Trees are essentially linked lists in which each list has two or more sub-lists.Leap of faith
Something that has been concerning me a bit has been the language used when the online textbook suggests implementing a method which involves recursion. It refers to assuming that the recursive call works is taking a leap of faith. As long as there is a base case for how to actually act on the data when the data is there to be acted upon, there should be no leap of faith involved.The fear of recursion
That being said, it does always feel like recursion is something strange and unusual which seems to miraculously work. However, the feeling, when carefully examined is due to an unfounded fear. The fear is simply that the function you are calling is not complete. When you type the call into the function, sure, that is the case. But by the time you call the function, it is supposedly finished. The call is simply returning to the beginning of the function and passing a new value. Recursive data structures are very useful and not too hard to wrap your head around. It just takes some getting used to.Monday 14 October 2013
Object-Oriented Programming and Recursion
Object-Oriented Programming
Object-oriented programming (OOP) languages focus on creating objects (or classes) that contain data. Each object has methods associated with it that perform tasks specific to the data structure being used. Before the advent of OOP, programming languages focused on allowing the user to write procedures that operated on data. OOP is useful because specific data structures often have very specific ways in which data can be operated upon, and the methods defined for any object will reflect this. Methods that are apprpriate across multiple classes can be inherited to save a programmer from code duplication. OOP also allows programs to correspond more closely to objects in the real world. It seems that object-oriented programming is a very useful tool for computer programmers.Recursion
Recursion is defined as defining something in terms of itself. In programming, recursion is referred to as a function that calls itself inside of itself. It is often used to analyze data that is organized recursively, such as data structures that have miniature versions of the same data structure contained within. For many problems in programming, recursion is the easiest and sometimes the only way to solve them. Otherwise, one would have to access each substructure in a new way. Recursive programs must also include some kind of exit condition, or the result may be an infinitely looping function call. Recursive programming mimics many structures in nature, such as trees, where each branch can be conceived of as a smaller tree.
Subscribe to:
Posts (Atom)