Learning Python Algorithm Notes
What distinguishes one linear structure from another is the way in which items are added and removed, in particular the location where these additions and removals occur.
To simulate the circle, we will use a queue. Assume that the child holding the potato will be at the front of the queue. Upon passing the potato, the simulation will simply dequeue and then immediately enqueue that child, putting her at the end of the line. She will then wait until all the others have been at the front before it will be her turn again. After num dequeue/enqueue operations, the child at the front will be removed permanently and another cycle will begin. This process will continue until only one name remains.
self in class definition.
- A recursion algorithm must have a base case.
- A recursion algorithm must change its state and move toward the base case.
- A recursion algorithm must call itself, recursively.
A base case is the condition that allows the algorithm to stop recusing. A base case is typically a problem that is small enough to solve directly.
To obey the second law, we must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way.
Here is a high-level outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:
- Move a tower of
height-1to an intermediate pole, using the final pole.
- Move the remaining disk to the final pole.
- Move the tower of
height-1from the intermediate pole to the final pole using the original pole.
The general name for this process of looking for another slot after a collision is rehashing. With simple linear probing, the rehash function is
rehash(pos)=(pos+1)%sizeoftablere. The “plus 3” rehash can be defined as
rehash(pos) = (pos+3)%sizeoftable.
rehash(pos) = (pos+skip)%sizeoftable.
_It is important to note that the size of the “skip” must be such that all the slots in the table will eventually be visited._ Otherwise, part of the table will be unused. To ensure this, it is often suggested that the table size be a prime number. This is the reason we have been using 11 in our examples.
A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to (to be decided) any key stored in the right sub-tree.
In the implementation of the class
TreeNode, the definition of
isLeftChild() method :
Why we should use
self.parent and ... , because this ensure the node is not the root.