插入

代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def tree_insert(root:TreeNode,z:int):
    z = TreeNode(z)
    x = root
    y = None
    while x:
        y = x
        if z.val < x.val:
            x = x.left
        else:
            x = x.right
    if y == None:
        root == z
    elif z.val < y.val:
        y.left = z
    else:
        y.right = z

删除

删除节点z需要考虑四种情况

1. z只有right，直接right代替
2. z只有left，直接left代替
3. z包含left和right，且right节点只有right节点，需要寻找z的后继y，来替换z
4. 基于第3点，如果后继y是z的right，那直接替换，如果不是，齐腰进行拼接

伪代码

def transplant(root:TreeNode,u:TreeNode,v:TreeNode):
    if u.p == None:
        root = v
    elif u == u.p.left:
        u.p.left = v
    else:
        u.p.right = v
    if v != None:
        v.p = u.p

def tree_delete(root:TreeNode,z:TreeNode):
    if z.left == None:
        transplant(root,z,z.right)
    elif z.right == None:
        transplant(root,z,z.left)
    else:
        y = tree_minium(z.right)
        if y.p != z:
            transplant(root,y,y.right)
            y.right = z.right
            y.right.p = y
        transplant(root,z,y)
        y.left = z.left
        y.left.p = y