ALDS1_8_C: Binary Search Tree III (続き)
削除したノードのところに(どっちでもいいけど)左の子をつなぎ直して、
右の子は左の子の右端のノードの右につなぐ
だと、削除前より木が深くなっちゃったりするのでよくなさそう
左の子の右端のノードを削除したノードのところにつなぐ
こっちで行こう
まず削除対象のノードを見つけないといけないな
find
がTrue/False
を返すようにしてたけど、ノードを返すようにすれば
そのまま使えそう
見つからなければNone
確かNone
がFalse
扱いでNone
以外はTrueになるんだったよね
parent
が覚えてあるとやっぱり楽だな
で、さらに考えてみると
削除したノードの左の子に右の子があるかどうかで分けなければ
いけないような気がする
削除したノードの左の子に右の子がないときは
左の子を親につなぎ直して
左の子の右に親の右の子をつなぎ直す
右の子があるときは、
右端のノードの親は削除したノードの親
右端のノードの右の子は削除したノードの右の子
右端のノードの左端のノードの左の子は削除したノードの左の子
もう死にそう
コードにしてみた(一部省略)
from sys import stdin
class Node():
:
def rightmost_child(self):
x = self
while x.right is not None:
x = x.right
return x
def leftmost_child(self):
x = self
while x.left is not None:
x = x.left
return x
class Tree():
:
def find(self, key):
x = self.root
while x is not None:
if key == x.key:
return x
elif key < x.key:
x = x.left
else:
x = x.right
return None
def delete(self, key):
x = self.find(key)
if x.left is None and x.right is None:
if x.parent.left == x:
x.parent.left = None
else:
x.parent.right = None
elif x.left is None:
if x.parent.left == x:
x.parent.left = x.right
else:
x.parent.right = x.right
x.right.parent = x.parent
elif x.right is None:
if x.parent.left == x:
x.parent.left = x.left
else:
x.parent.right = x.left
x.left.parent = x.parent
elif x.left.right is None:
x.left.parent = x.parent
if x.parent.left == x:
x.parent.left = x.left
else:
x.parent.right = x.left
x.left.right = x.right
x.right.parent = x.left
else:
y = x.left.rightmost_child()
z = y.leftmost_child()
y.parent.right = None
if x.parent.left == x:
x.parent.left = y
else:
x.parent.right = y
y.parent = x.parent
x.right.parent = y
y.right = x.right
x.left.parent = z
z.left = x.left
:
def main():
_ = int(stdin.readline())
T = Tree()
for line in stdin:
cmd, *args = line.split()
if cmd == "insert":
T.insert(Node(int(args[0])))
elif cmd == "find":
print("yes" if T.find(int(args[0])) else "no")
elif cmd == "delete":
T.delete(int(args[0]))
elif cmd == "print":
T.print_inorder()
T.print_preorder()
いちおう動いてるけど合ってる自信はまったくなし
やってみると#3でWA
しかし間違っているのかと言うと二分探索木としては間違ってない気もする
これはつなぎ直し方の方針が違うだけかもしれない
そろそろあきらめて問題最後まで読むか