二分木の削除機能 in Python

Question

二分木の削除機能の実装

二分木をPythonで自作しているのですが、削除のところで詰まってしまいました。
削除を実装できたのですが、動かないです。

追加や検索は動いているので、何に問題があるのかわからず困っています。どなたか私のコードを改変して、削除機能を動かせる方はいないでしょうか。。。？

発生している問題・エラーメッセージ

# [50, 98, 54, 6, 34, 66, 63, 52, 39, 62]
# 6
# 34
# 39
# 50
# 52
# 54
# 62
# 63
# 66
# 98
# True
# 6
# 34
# 39
# 50
# 52
# 54
# 62
# 63
# 66
# 98

該当のソースコード

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val


class Tree:
    def __init__(self):
        self.root = None

    def add_list(self, l):
        for i in l:
            self.add(i)

    def add(self, val):
        if (self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):  # Private Function
        if val == node.v:
            print("Already existed in tree!")
        if (val < node.v):
            if (node.l == None):
                node.l = Node(val)
            else:
                self._add(val, node.l)
        else:
            if (node.r == None):
                node.r = Node(val)
            else:
                self._add(val, node.r)


    def find(self, val):
        if self.root != None:
            return self._find(val, self.root)
        else:
            return False


    def _find(self, val, node):
        if node == None:
            return False
        if val == node.v:
            return True
        elif val > node.v:
            return self._find(val, node.r)
        elif val < node.v:
            return self._find(val, node.l)

    def printtree(self):
        if self.root == None:
            print("Tree doesn't exist yet!")
        else:
            self._printtree(self.root)

    def _printtree(self, node):
        try:
            self._printtree(node.l)
            print(str(node.v))
            self._printtree(node.r)
        except:
            return None

    def delete(self, val):
        if self.root == None:
            print("Tree doesn't exist!")
        else:
            self._delete(val, self.root)

# はじめに探索して対象のノードを探す。 その後、子の有無によって処理を分ける。
#
# 1 子がない場合 ~~ 対象のノードは葉であるので、node.v == NoneでOK
# 2 一つの子がある場合 ~~ node = 存在する方の子(node.r or node.l)にすればOK
# 3 どちらの子もある場合 ~~ 右の子から最小の値(node.min)を探し、node.v = node._findMinとする。のちに、
#   最小の値を持つnode_minをnode_min = node.rとすればOK.
#
# はじめに_findMin関数をつくる.

    def _findMin(self, node):
        if node.l == None:
            return node.v
        else:
            return self._findMin(node.l)

# 次に_deleteMin関数を作る.

    def _deleteMin(self, node):
        if node.l == None:
            return node.r
        else:
            node.l = self._deleteMin(node.l)
            return node

    def _delete(self, val, node):
        # 削除したい値が木に存在するとき
        try:
            if val == node.v:
                # どちらの子もNone, または左の子がNoneの場合
                if node.l == None:
                    node = node.r
                # 右の子がNoneの場合
                elif node.r == None:
                    node = node.l
                # どちらの子も存在する場合
                else:
                    node.v = self._findMin(node.r)
                    node.r = self._deleteMin(node.r)
            elif val < node.v:
                self._delete(val, node.l)
            elif val > node.v:
                self._delete(val, node.r)
        # 削除したい値が木に存在しないとき
        except:
            print("Value doesn't exist in tree.")


# Test
# ________


import random

if __name__ == "__main__":
    tree = Tree()

    random.seed(0)
    l = [random.randint(1, 100) for x in range(10)]

    print(l)

    tree.add_list(l)

    # for i in l:
    #     tree.add(i)

    tree.printtree()

    print(tree.find(50))



    tree.delete(39)

    tree.printtree()

試したこと

ここを参考にしました。
Python二分木

Answer 1

if node.l == None and node.r == None:
     node.v = None
elif node.l == None: #if->elif
……

この修正では正しくないが、せめて値だけを消すことはできます。
親ノードの参照から、値を消すことが目的です。
もう一度参考リンクを読み直してみてください。