[python]木構造の削除について

前提・実現したいこと

pythonの探索木構造を勉強しています。指定された番号をもつデータの木を探索し、そのデータを消す関数を作成しています。木の浅い部分で削除され、小木に２つのデータを持つ場合、複雑な入れ替わりになると思うのですが、そこも実現しどの木でも削除されるようにしたいです。

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

小木に２つのデータがある際にうまく削除されずに、小さいものを消した位置にもってこれるのですが、その小木が急に消えてしまい、よくわからなくなってしまいました。

該当のソースコード

python
1class TreeSearch:
2    def deletemin(self, curent):
3        prev = curent
4        tmp = curent.left
5        while tmp.right:
6            prev = tmp
7            tmp = tmp.right
8        prev.right = tmp.right
9        prev.left = tmp.left
10        return tmp
11
12    def delete(self, search_num):
13        curent = self.head
14        prev = self.head
15        flag = ''
16        if curent:
17            while True:
18                data = curent.num
19                if search_num < data:
20                    if curent.left is None:
21                        print('   There is no Player.')
22                        return ValueError
23                    prev = curent
24                    curent = curent.left
25                    flag = 'left'
26                elif search_num > data:
27                    if not curent.right:
28                        print('   There is no Player.')
29                        return ValueError
30                    prev = curent
31                    curent = curent.right
32                    flag = 'right'
33                elif search_num == data:
34                    if curent.right == None and curent.left == None:
35                        if flag == 'left':
36                            prev.left = None
37                        elif flag == 'right':
38                            prev.right = None
39                    elif curent.right == None:
40                        if flag == 'left':
41                            prev.left = curent.left
42                        elif flag == 'right':
43                            prev.right = curent.left
44                    elif curent.left == None:
45                        if flag == 'left':
46                            prev.left = curent.right
47                        elif flag == 'right':
48                            prev.right = curent.right
49                    else:
50                        tmp = self.deletemin(curent)
51                        print("min = %d" %tmp.num)
52                        if flag == 'left':
53                            prev.left = tmp
54                        elif flag == 'right':
55                            prev.right = tmp
56                        tmp.right = curent.right
57                        tmp.left = curent.left
58                    return True
59        else:
60            print('   There is no Player.')

python
1if curent:  # curent else 条件分岐内にroot削除処理を挿入
2            if self.head.num == search_num:
3                if self.head.right == None and self.head.left == None:
4                    self.head = None
5                    return True
6                elif self.head.right == None and self.head.left:
7                    self.head = self.head.left
8                    return True
9                elif self.head.right and self.head.left == None:
10                    self.head = self.head.right
11                    return True
12                else:
13                    head_tmp = self.head
14                    curent = self.head.right
15                    prev = None
16                    while curent.left:
17                        prev = curent
18                        curent = curent.left
19                    self.head = curent
20                    self.head.left = head_tmp.left
21                    if curent.num < prev.num:
22                        prev.left = self.head.right
23                    else:
24                        prev.right = self.head.right
25                    self.head.right = prev
26                    return True
27            else:
28                while True:
29                     ・
30                     ・
31                     ・
32                    以下続き

試したこと

関数deleteminが間違っている気がして、いろいろ処理を追加したり、rightとleftの書き間違いかと、入れ替えたりしてみたのですが、上記のコードが一番まともに動作しています。

どなたかご教授ください。

補足情報（FW/ツールのバージョンなど）

python3.8

dameo

2020/08/24 01:01

探索木にもいくつか種類があり、こればかり使われるというものもありません。なので、二分探索木ならちゃんとそう書いた方がいいかもです。回答者さんには分かるかもですが、他の質問者さんが混乱するかもしれません。

行動規範の内容に同意します

回答2件

確かにdeleteminがおかしいですね。

Python
1        prev.right = tmp.right
2        prev.left = tmp.left

tmp.rightはNoneになってるはずですし、tmp.leftはprevの右側の部分木に属すので、探索木の構造上左側には付けられません。

Python
1        prev.right = tmp.left

いろいろ試行錯誤で変えてみたようですが、これだけでいいです。

あとは、ルートが削除された場合や、削除するノードの左側の子が右側の子を持たない場合といったコーナーケースの処理が抜け落ちてるのでそれも必要でしょう。

削除するノードの子の右、左があるかないかで条件分岐し、ある場合はそのままの処理でない場合は、削除するノードの親をNoneにする？という処理でしょうか？
いまいち理解できていません。

今のコードは不必要に分岐が深くコードが分散してるので、そこがこんがらがる最大の要因じゃないかと思います。
コードがまとまるように書くと下のような感じです。削除するノードの孫世代を見る条件の追加と、flag変数を使わずprevとの比較でルートにするか左右の子にするかを決定するようにした以外は大きくは変えていません。今のコードが分散しすぎて見通しが悪くなってることがわかると思います。

Python
1    def delete(self, search_num):
2        prev = None
3        current = self.head
4        #ノードを探索
5        while current is not None:
6            data = current.num
7            if search_num < data:
8                prev = current
9                current = current.left
10            elif data < search_num:
11                prev = current
12                current = current.right
13            else:
14                break
15        
16        #見つからなかったらリターン
17        if current is None:
18            print('   There is no Player.')
19            return ValueError
20        
21        #削除するノードの代わりになるノードを設定
22        newNode = None
23        if current.right is None:
24            newNode = current.left
25        elif current.left is None:
26            newNode = current.right
27        elif current.left.right is None: #追加した条件
28            newNode = current.left
29            newNode.right = current.right
30        else:
31            newNode = self.deletemin(current)
32            print("min = %d" %newNode.num)
33            newNode.right = current.right
34            newNode.left = current.left
35            
36        #新しいノードを適切な位置に挿入
37        #flagをなくし、prevの値との比較で挿入する場所を決定
38        if prev is None:
39            self.head = newNode
40        elif search_num < prev.num:
41            prev.left = newNode
42        else:
43            prev.right = newNode
44        return True

投稿2020/08/23 01:49

編集2020/08/23 09:18

yudedako67

総合スコア2047

WindowppleMacin

2020/08/23 02:40 編集

迅速な回答ありがとうございます！ああ、簡単なことでした、、、一人で考えてるとどんどん分からなくなっていってしまいますね... ルートが削除された場合も考えて実装してみました。参考にしたものの通りでは動作しなくて、大幅に書き換えをしたところ、一応正常に動作するのですが、どこか欠陥がありそうで不安なのですが大丈夫でしょうか？質問文に追記しました！みにくかったのでまた、「削除するノードの左側の子が右側の子を持たない場合」というのは、delete内で動作するのではないでしょうか？

yudedako67

2020/08/23 04:56

値を追加する部分のコード部分は憶測ですが、修正済みのコードでも insert(2), insert(1), insert(3), delete(2) とか insert(0), insert(2), insert(1), insert(3), delete(2) はうまく動かないはずです。どちらも原因は削除するノードの子の子(つまり孫)がNoneである場合が考慮されてないことです。

WindowppleMacin

2020/08/23 05:45

確かに、何回か削除を行うと、 if curent.num < prev.num: AttributeError: 'NoneType' object has no attribute 'num' と出て、データ構造がない番地をright leftに代入してしまっているようです。削除するノードの子の右、左があるかないかで条件分岐し、ある場合はそのままの処理でない場合は、削除するノードの親をNoneにする？という処理でしょうか？いまいち理解できていません。

行動規範の内容に同意します