Using model Binary Tree code snippet, how to implement this?

Question

I have a code for Binary Tree (Not BST) from MIT 6.006 (2020, MIT OCW). By the way, I have no idea of how to add elements into the Tree using below two Classes (symbol A or T seems to be used instead of a self). Specifically,

how to insert elements into Binary_Tree
how to incorporate the build(X) function into the Binary_Tree

Could anybody give an example of how I can utilize this code?

# From Recitation 6, MIT 6.006, Spring 2020
class Binary_Node:
    def __init__(A, x): # O(1)
        A.item = x
        A.left = None
        A.right = None
        A.parent = None

    def subtree_iter(A): # O(n), in-order traversal
        if A.left:  yield from A.left.subtree_iter()
        yield A
        if A.right: yield from A.right.subtree_iter()

    def subtree_first(A): # O(h)
        if A.left:  return A.left.subtree_first()
        else:       return A

    def subtree_last(A): # O(h)
        if A.right: return A.right.subtree_last()
        else:       return A

    def successor(A): # O(h)
        if A.right: return A.right.subtree_first()
        while A.parent and (A is A.parent.right):
            A = A.parent
        return A.parent

    def predecessor(A): # O(h)
        if A.left: return A.left.subtree_last()
        while A.parent and (A is A.parent.left):
            A = A.parent
        return A.parent

    def subtree_insert_before(A, B): # O(h)
        if A.left:
            A = A.left.subtree_last()
            A.right, B.parent = B, A
        else:
            A.left,  B.parent = B, A

    def subtree_insert_after(A, B): # O(h)
        if A.right:
            A = A.right.subtree_first()
            A.left,  B.parent = B, A
        else:
            A.right, B.parent = B, A

    def subtree_delete(A): # O(h)
        if A.left or A.right:
            if A.left: B = A.predecessor()
            else:      B = A.successor()
            A.item, B.item = B.item, A.item
            return B.subtree_delete()
        if A.parent:
            if A.parent.left is A: A.parent.left  = None
            else:                  A.parent.right = None
        return A

class Binary_Tree:
    def __init__(T, Node_Type = Binary_Node):
        T.root = None
        T.size = 0
        T.Node_Type = Node_Type

    def __len__(T): return T.size

    def __iter__(T):
        if T.root:
            for A in T.root.subtree_iter():
                yield A.item

def build(X):
    A = [x for x in X]
    def build_subtree(A, i, j):
        c = (i + j) // 2
        root = self.Node_Type(A[c])
        if i < c:
            root.left = build_subtree(A, i, c - 1)
            root.left.parent = root
        if c < j:
            root.right = build_subtree(A, c + 1, j)
            root.right.parent = root
        return root
    self.root = build_subtree(A, 0, len(A) - 1)

Using model Binary Tree code snippet, how to implement this?

0 Answers