CSC 148 Python Week 10 Slog: Efficiency of Algorithms

Today in class, we learnt more about Efficiency of Algorithms. Because we can solve Binary Search Tree insertion in both iterative and recursive way, the professor today want to show us which is a more efficient way. Basically, we will consider two factors in analyzing the efficiency here. The first one is how large is the extra memory of these two algorithm and the time it takes to do two algorithms. We can find out that in doing iterative way, we do not need much extra memory as the for loop will always have a constant extra memory to store. However, for recursive way, we can see that if the tree is balanced, which means that the right and left side have similar amount of children, there will still be O(lgn) larger amount of extra time than iterative way. For the time they spend, we can see that for iterative way, there will be n number of time but for recursive way it will take 2 to the power of n number of time. This means that in a Binary Search Tree inserting new value algorithm, recursive algorithm is not efficient. However, recursion is a very powerful technique for problems that are naturally recursive. So different methods will work better for different problems. 

Here is a graph of the comparison between Recursive and Iteration and I find it very helpful.

CSC 148 Python Week 9 Slog: Binary Search Tree How to Delete

Last week, we have already learnt the structure of Binary Tree. A binary tree consists of a finite set of nodes that is either empty, or consists of one specially designated node called the root of the binary tree, and the elements of two disjoint binary trees called the left subtree and right subtree of the root. We know that when inserting a new node to a tree, we first need to make comparison with the root of each node. If the new node is smaller than the root, it will be placed to its left subtree. Otherwise, it will be placed to its right subtree. It will continue this comparison until the new node find an empty place to be placed. This kind of structure is easy to trace in an "Insert" algorithm. However, from my perspective, it is hard to think about how deletion work in Binary Search Tree. After the class, I find out that there are three possible cases to consider and according to the Professor， there are three ways to solve deletion problems. 

• Deleting a node with no children: simply remove the node from the tree.
• Deleting a node with one child: remove the node and replace it with its child.
• Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If you choose in-order successor of a node, as right sub tree is not NIL (Our present case is node has 2 children), then its in-order successor is node with least value in its right sub tree, which will have at a maximum of 1 sub tree, so deleting it would fall in one of first 2 cases.

Here, we can see that using this picture, we can understand this algorithm better. 

From this example, we can see that when we are dealing with more complicated binary tree deletion like deleting node with two subtrees, we can either use the largest node in left subtree or use the smallest node in right subtree. From this lesson, I find out that using tree diagram and tracing will help us better learn this subject. Because binary tree is an ordered tree, we can use this to apply to other data set so that it will save us a lot of time to search for a certain number. Also, in class, we also learnt about the importance of a balanced tree. A balanced tree, which have similar number of right and left trees will be the best and most efficient in doing searching.

CSC 148 Python Week 8 Slog: Tree Traversals vs Linked List

Today in the class, we learnt tree traversal. In computer science tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting each node in a tree data structure exactly once. There are many similarity and difference between Tree and Linked List. Like linked lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes and we also learnt deeply in class. These references are referred to as the left and right subtrees. Like list nodes, tree nodes also contain cargo. However, compared to linked lists and other one-dimensional arrays, which have a linear order, tree structures can be traversed in many different ways. In class, we learnt inorder, preorder and postorder for depth-first searching, as well as level order for breadth first searching. Here are the graphs for these models:

Inorder 

                                                                           

Postorder

Preorder

Level Order

From these examples, we know more about how tree traversal works. In terms of how to write the code for binary tree search and tree traversal, I find that most of the parts are using recursion algorithm to solve the problems. Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node as it is not a linear data structure. This is often done via a stack (LIFO) or queue (FIFO). As a tree is a recursive data structure, traversal is usually defined by recursion. Thus, I find out that the knowledge are all inter-related and we need to learn all of these methods to understand each other.