Week 10

test.

Week 9

'''
This week we talk about the main idea for three sorts,
which is selection sort, merge sort, and quick sort.
Selection Sort is a simple and intuitive sorting algorithm.
First, find the smallest unsorted sequence (large) elements
stored in the collating sequence of the starting position,
and then again from the remaining unsorted elements continue
to look for the smallest (large) elements, and then sorted into
the end of the sequence. And so on until all the elements are sorted.
Merge sort, divide the list in half, sort the halves, then merge the
sorted results, i think it should be easy done by use recursion. By the way,
the efficiency of merger sort is just after quick sort, it is a stable s
sorting algorithm, generally used for general disorder, but each child is
relatively orderly sequence.
Quick sort, which is fastest in almost all case , but not the worst case.
the main idea of quick sort is choose a pivot; decide where the pivot goes
with respect to the rest of the list, repeat on the partition.
'''

Week 8

''' In the class we talking about the 'big O' notation,
which describes the limiting behavior of the function
when the argument trends towards a particular value of infinity
example :
f(x)= 3x^4 - 2x^3 + 1 ;
if we wanna simply function , using O notation, the highest growth rate is
3x^4, and we take x^4 from 3x^4. Thus, we say that f(x) is a 'big-O' of (x^4),
can be write as f(x)=O(x^4).
And from class we know O(1) ∈ O(lg n) ∈ O(n) ∈ O(n^2) ∈ O(n^3) ∈ O(2^n) ∈ O(n^n)
Also we learn the binary search tree(BST), there is some properties of BST(from Wikipedia):

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

The binary search is, on average, much fast than linear search. The number of binary search comparisons
in a list of size n is x=log_2 (n). the logarithm base two of n.
'''

'''
class BST:
    def __init__(self, container=[]):
        self.root = None
        for item in container:
            self.insert(item)

    def __str__(self):
        return BST._str("",self.root)

    def _str(indent, root):
        if root is None:
            return ""
        else:
            return (BST._str(indent + "\t", root.right) +
                    indent + repr(root.item) + "\n" +
                    BST._str(indent + "\t", root.left))
    def insert(self, item):
        parent, current = None, self.root
        while current is not None and current.item != item:
            if item < current.item:
                parent, current = current, current.left
            else:
                parent, current = currrnt, curren.right

        if current is None:
            parent = _BSTNode(item)
            if parent is None:
                self.root = current
            elif item < parent.item:
                parent.left = current
            else:
                parent.right = current


class _BSTNode:
    """A node in a BST."""

    def __init__(self, item, left=None, right=None):
        """(_BSTNode, object, _BSTNode, _BSTNode) -> NoneType
        Initialize this node to store item and have children left and right.
        """
        self.item = item
        self.left = left
        self.right = right
'''
'''
x = _BSTNode(1,_BSTNode(2,_BSTNode(4),_BSTNode(7)),_BSTNode(3,_BSTNode(6),_BSTNode(5)))
print(x)
y = BST([1,2,3,4])
y.insert(2)
y.insert(1)
y.insert(9)
y.insert(5)
y.insert(4)
print(y._str(y.root))
'''

class BTNode:
    """Binary Tree node."""
    """initial the Binary tree node"""
    def __init__(self: 'BTNode', data: object,
                 left: 'BTNode'=None, right: 'BTNode'=None) -> None:
        """Create BT node with data and children left and right."""
        self.data, self.left, self.right = data, left, right

    def __repr__(self: 'BTNode') -> str:
        """Represent this node as a string."""
        return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
                ', ' + repr(self.right) + ')')

    def is_leaf(self: 'BTNode') -> bool:
        """Is this node a leaf?"""
        return self.data and not self.left and not self.right
 
"""
        this line equal to
        if self.data != None and self.left == None and self.right == None:
               return True
        else:
               return False
        >>>x=BTNode(1)
        >>>print(x.is_leaf())
           True
"""


"""binary search tree ADT"""

class BST:
    """Binary search tree."""

    def __init__(self: 'BST', root: BTNode=None) -> None:
        """Create BST with BTNode root.
        initial self to None, if dont hv BTNode
        """
        self._root = root

    def __repr__(self: 'BST') -> str:
        """Represent this binary search tree."""
        return 'BST(' + repr(self._root) + ')'

    def find(self: 'BST', data: object) -> BTNode:
        """Return node containing data, otherwise return None."""
        return _find(self._root, data)

    def insert(self: 'BST', data: object) -> None:
        """Insert data, if necessary, into this tree.

        >>> b = BST()
        >>> b.insert(8)
        >>> b.insert(4)
        >>> b.insert(2)
        >>> b.insert(6)
        >>> b.insert(12)
        >>> b.insert(14)
        >>> b.insert(10)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
    """
        def __insert(node, data):
            return_node = node
            if not node:
                return_node = BTNode(data)
            elif node.data > data:
                node.left = __insert(node.left, data)
            elif node.data < data:
                node.right = __insert(node.right, data)
            else:
                pass
            return return_node
             
        self._root = __insert(self._root, data)

    def delete(self: 'BST', data: object) -> None:
        """Remove, if there, node containing data.

        >>> b = BST()
        >>> b.insert(8)
        >>> b.insert(4)
        >>> b.insert(2)
        >>> b.insert(6)
        >>> b.insert(12)
        >>> b.insert(14)
        >>> b.insert(10)
        >>> b.delete(12)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(10, None, BTNode(14, None, None))))
        >>> b.delete(14)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(10, None, None)))
        """
        def __find_max(node):
            return __find_max(node.right) if node.right else node
        def __delete(node, data):
            return_node = node
            if not node:
                pass
            elif node.data > data:
                node.left = __delete(node.left, data)
            elif node.data < data:
                node.right = __delete(node.right, data)
            else:
                if not node.right:
                    return_node = node.left
                elif not node.left:
                    return_node = node.right
                else:
                    node.data = __find_max(node.left).data
                #go throught the left side and dine max again and replace as None
                    node.left = __delete(node.left, node.data)
            return return_node
                 
        self._root = __delete(self._root, data)

    def height(self: 'BST') -> int:
        """Return height of this tree."""
        return _height(self._root)
    def insert2(self, data):
        return_node = self._root
        if not self._root:
            return_node = BTNode(data)
        elif self._root > data:
            self._root.left = self.insert2(self.left, data)
        elif self._root < data:
            self._root.right = self.insert2(self.right, data)
        else:
            pass
     
       


def _insert(node: BTNode, data: object) -> BTNode:
    """Insert data in BST rooted at node, if necessary, and return root."""
    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 _find(node: BTNode, data: object):
    """Return the node containing data, or else None."""
    if not node or node.data == data:
        return node
    else:
        return (_find(node.left, data) if (data < node.data)
                else _find(node.right, data))


def _delete(node: BTNode, data: object) -> BTNode:
    """Delete, if exists, node with data and return resulting tree."""
    # Algorithm for _delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node
    return_node = node
    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


def _find_max(node: BTNode) -> BTNode:
    """Find and return maximal node, assume node is not None"""
    return _find_max(node.right) if node.right else node


def _height(node):
    """Return height of tree rooted at node."""
    # use max to get the deeper node
    return 1 + max(_height(node.left), _height(node.right)) if node else -1

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    b = BST()
    b.insert(8)
    b.insert(4)
    b.insert(2)
    b.insert(1)
    b.insert(6)
    b.insert(5)
    b.insert(7)
    b.insert(10)
    b.insert(9)
    b.insert(12)
    print(b)
    b.delete(4)
    print(b)
    print('1')
    b.delete(14)
    print(b)
    print(b.height())
    a = BTNode(2)
    print(_find_max(a).data)