Week11 SLOG: Wrong understanding on Linked List

After revisiting week 8 and week 9 SLOGs, I found I made something wrong with Linked List. In these two SLOGs, I defined some concepts about Tree and Linked List and wrote some functions about them. However, I did not understand the concept about Linked List clearly because I did not consider Linked List as one kind of Tree Type.

First of all, I need to review definition of Linked List and Tree to prove what I made wrong with Linked List. Firstly, a Tree is a set of nodes with directed edges between some pair of nodes and an edge connects a parent node and a child node. Secondly, a Linked List is a linear sequence of nodes and we will keep a reference to the front of the sequence. In conclusion, Linked List can be considered as a tree like this (assuming Linked List has 6 nodes in this Tree):

 16

 ↓

 15

 ↓

 14

 ↓

 13

 ↓

 12

 ↓

 11

Each height of the tree only contains one node, and it is the maximum height that a tree can have. In addition, there is only one path that the tree has, which likes a linear sequence. Overall, Linked List is a type of tree.

Week10 SLOG: mutate Insert and Delete function

In this week, I have learned something about mutating functions like insert and delete in Binary Search Tree.

First of all, I need to define class BTNode and BST. And I also need to initialize them.

class BTNode:

    '''Binary Tree node.'''

    def __init__(self, data, left=None, right=None):

        ''' (BTNode, object, BTNode, BTNode) -> NoneType

        Create BTNode (self) with data and children left and right.

        '''

        self.data, self.left, self.right = data, left, right

Class BST:

'''Binary Search Tree node.'''

def __init__(self, root=None):

    '''(BST, BTNode or None) -> Nonetype

    Create BST with BTNode root.

    '''

    Self.root = root

Next, I mutate insert and delete methods.

def insert(node, data):

    ''' (BTNode, object) -> BTNode

    Insert data in BST rooted at node if necessary, and return new root.

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> print(b)

            14

        12

            10

    8

            6

        4

            2

    <BLANKLINE>

    '''

    return_node = node

    if not node:

        return_node = BTNode(data)

    elif data < node.data:

        node.left = insert(node.left, data)

    elif data > node.data:

        node.right = insert(node.right, data)

    else:  # nothing to do

        pass

    return return_node

def delete(node, data):

    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> b = delete(b, 12)

    >>> print(b)

            14

        10

    8

            6

        4

            2

    <BLANKLINE>

    '''

    if not node:

        pass

    elif data < node.data:

        node.left = delete(node.left, data)

    elif data > node.data:

        node.right = delete(node.right, data)

    elif not node.left:

        return_node = node.right

    elif not node.right:

        return_node = node.left

    else:

        node.data = _find_max(node.left).data

        node.left = delete(node.left, node.data)

    return return_node

Week 8 SLOG: Linked List

From the last week lectures, I learned something about linked list. 

Initially, a linked list is a linear sequence of nodes and we will keep a reference to the front of the sequence. Furthermore, in the lecture, we define two different classes which are LLNode and LinkedList. LLNode represents a single node and LinkedList represents the linked list as a whole.

First of all, we need to define LLNode class, including __init__, __str__ and __eq__ methods:

class LLNode:

     def __init__(self, value, nxt=None):

        ''' (LLNode, object, LLNode) -> NoneType

        Create LLNode (self) with data value and successor nxt.
        '''
        self.value, self.nxt = value, nxt

    def __str__(self):

        ''' (LLNode) -> str

        Return a user-friendly representation of this LLNode.

        >>> n = LLNode(4, LLNode(6))
        >>> print(n)
        4 -> 6 ->|
        '''
        if self.nxt is None:
            return '{} ->|'.format(str(self.value))
        else:
            return '{} -> {}'.format(str(self.value), str(self.nxt))

 def __eq__(self, other):

        ''' (LLNode, object) -> bool

        Return whether LLNode (self) is equivalent to other.

        >>> LLNode(3).__eq__(3)
        False
        >>> n = LLNode(4, LLNode(6))
        >>> n2 = LLNode(4, LLNode(6, None))
        >>> n.__eq__(n2)
        True
        '''
        return (type(self) == type(other) and
                (self.value, self.nxt) == (other.value, other.nxt))

And then we go to define the LinkedList class,  including __init__, __str__, __eq__  and prepend methods:

class LinkedList:
    def __init__(self):
        ''' (LinkedList) -> NoneType

        Create an empty linked list.
        '''
        self.front, self.back = None, None
        self.size = 0

    def __str__(self):
        ''' (LinkedList) -> str

        Return a human-friendly string representation of
        LinkedList (self)

        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> print(lnk)
        5 ->|
        '''
        return str(self.front)

    def __eq__(self, other):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) is equivalent to
        other.

        >>> LinkedList().__eq__(None)
        False
        >>> lnk = LinkedList()
        >>> lnk.prepend(4)
        >>> lnk2 = LinkedList()
        >>> lnk2.prepend(4)
        >>> lnk.__eq__(lnk2)
        True
        '''
        return (type(self) == type(other) and
                (self.size, self.front) == (other.size, other.front))


    def prepend(self, value):
        ''' (LinkedList, object) -> Nonetype

        Insert value at front of LLNode (self).

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> str(lnk.front)
        '2 -> 1 -> 0 ->|'
        >>> lnk.size
        3
        '''
        self.front = LLNode(value, self.front)
        if self.back is None:
            self.back = self.front
        self.size += 1

Week 8 SLOG：the Summary of Tree

Tree is an abstract data type. First of all, a tree is a set of nodes with directed edges between some pair of nodes and an edge connects a parent node and a child node. Following this, the path is a sequence of nodes n1, n2...nk where there is an edge from ni to ni+1 and the length of a path is the number of edges on it. 

In addition, it has many different parts such as leaf, internal node, subtree, height and depth.  Firstly, leaf is a node with no child. Secondly, internal node is a node with one or more children. Thirdly, subtree is a tree formed by any nodes and its descendants, and the edges connecting them. Fourthly, height is the maximum path length +1. Finally, depth equals to height of the whole tree minus the height of the tree rooted at that rode.

Initializing the class Tree:

class Tree:
    ''' Represent a Bare-bones Tree ADT'''

    def __init__(self, value=None, children=None):
        ''' (Tree, object, list) -> NoneType

        Create Tree(self) with content value and 0 or more children.
        '''

        self.value = value

        self.children = children.copy() if children else []

For the height of the tree, here is the code of it:

def height(t):
    ''' (Tree) -> int
    
    Return height of Tree t,

    >>> tn2 = Tree(2, [Tree(4), Tree(5), Tree(7), Tree(8)])
    >>> tn3 = Tree(3, [Tree(6), Tree(10)])
    >>> tn1 = Tree(1, [tn2, tn3])
    >>> height(tn1)
    3
    '''
    if not t.children:
        return 1
    else:
        return max([height(c) for c in t.children]) + 1

Furthermore, we can also analyze the tree from different sides, so we initializing the class BTNode:

class BTNode:
    '''Binary Tree node.'''

    def __init__(self, data, left=None, right=None):
        ''' (BTNode, object, BTNode, BTNode) -> NoneType

        Create BTNode (self) with data and children left and right.
        '''
        self.data, self.left, self.right = data, left, right

And here is the method of parenthesize:
def parenthesize(b):
    ''' (BTNode) -> str

    Parenthesize the expression rooted at b, so that float data is not parenthesized,
    but each pair of expressions joined by an operator are parenthesized.

    Assume:  -- b is a binary tree
             -- interior nodes contain data in {'+', '-', '*', '/'}
             -- interior nodes always have two children
             -- leaves contain float data

    >>> b = BTNode(3.0)
    >>> print(parenthesize(b))
    3.0
    >>> b = BTNode('+', BTNode('*', BTNode(3.0), BTNode(4.0)), BTNode(7.0))
    >>> print(parenthesize(b))
    ((3.0*4.0)+7.0)
    '''
    if b.right is None and b.left is None:
        return b.data
    else:
        return ("(" + str(parenthesize(b.left)) + b.data 
                + str(parenthesize(b.right)) + ")")

What's more, below is the method to find the longest path in the tree:

def list_longest_path(node):
    ''' (BTNode) -> list

    List the data in a longest path of node.

    >>> list_longest_path(None)
    []
    >>> list_longest_path(BTNode(5))
    [5]
    >>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7)))
    [5, 3, 2]
    '''
    if node is None:
        return []
    else:
        if node.left is None and not node.right is None:
            return [node.data] + list_longest_path(node.right)
        elif node.left is None and node.right is None:
            return [node.data]
        elif node.right is None and not node.left is None:
            return [node.data] + list_longest_path(node.left)
        else:
            left = list_longest_path(node.left)
            right = list_longest_path(node.right)
            if len(left) < len(right):
                return [node.data] + right
            else:
                return [node.data] + left