二分木と二分探索木については、以前の記事ですでに説明しました。
今回は、メモリリークを起こさずにバイナリツリーを削除するアルゴリズムを定式化します。
また、そのアルゴリズムをPythonで実装します。
この記事もチェック：Pythonによるバイナリサーチ(二分探索)をwhile文を使って実装する
メモリリークとは？
プログラム中のメモリーリークは、変数にメモリーを割り当てた後、それを削除し忘れると発生します。
メモリリークが発生すると、プログラムの終了時に問題が発生することがあります。
そのため、メモリへの参照を削除する前に、割り当てを削除する必要があります。
Pythonはこれらのエラーをガベージコレクションの手続きで処理しますが、プログラム中にメモリリークを引き起こすようなコードを書かないように注意する必要があります。
ここでは、メモリリークを発生させずにバイナリツリー全体を削除するアルゴリズムについて説明します。
How to delete nodes of binary tree without memory leak?
二分木の要素を削除するには、del文を使って、各ノードに割り当てられたメモリを解放すればよい。
また、メモリリークを防ぐために、ノードそのものを削除する前に、そのノードの子ノードを削除する必要があります。
こうすることで、あるノードを参照している変数が、メモリを解放する前に削除されることがないようにすることができます。
木構造全体の探索には、木構造探索アルゴリズム（in-order, pre-order, level-order, post-order など）を使用することができる。
しかし、メモリリークを避けるために、親ノードより先に子ノードを削除する必要があるため、親ノードより先に子ノードを走査する必要があります。
後順序木探索アルゴリズムでは、親ノードを訪れる前に、任意のノードの子ノードを探索します。
そこで、二分木を削除するアルゴリズムを実装するために、後順序木探索を使用することにします。
次節では、このアルゴリズムを実装するために、後順序木探索アルゴリズムを修正します。
バイナリツリーを削除するアルゴリズム
上述したように、2分木を削除するアルゴリズムは、以下のように定式化される。
- ルートから開始します。
-
- 現在のノードがNoneかどうかをチェックし、Noneの場合、戻る。そうでなければ3.に進む。
-
- 現在のノードの左側の子ノードを再帰的に削除します。
-
- 現在のノードの右の子を再帰的に削除します。
- 現在のノードを削除します。
Pythonでバイナリツリーを削除する
二分木を削除するアルゴリズムについて説明し、定式化しましたので、Pythonで実装します。
また、以下の画像で与えられた二分木に対してアルゴリズムを実行します。
出力では、各ノードが親の削除の前に削除されていることが確認できます。
from queue import Queue
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def insert(root, newValue):
# if binary search tree is empty, make a new node and declare it as root
if root is None:
root = BinaryTreeNode(newValue)
return root
# binary search tree is not empty, so we will insert it into the tree
# if newValue is less than value of data in root, add it to left subtree and proceed recursively
if newValue < root.data:
root.leftChild = insert(root.leftChild, newValue)
else:
# if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild = insert(root.rightChild, newValue)
return root
def deleteTree(root):
if root:
# delete left subtree
deleteTree(root.leftChild)
# delete right subtree
deleteTree(root.rightChild)
# traverse root
print("Deleting Node:", root.data)
del root
root = insert(None, 15)
insert(root, 10)
insert(root, 25)
insert(root, 6)
insert(root, 14)
insert(root, 20)
insert(root, 60)
print("deleting all the elements of the binary tree.")
deleteTree(root) |
コード
deleting all the elements of the binary tree.Deleting Node: 6Deleting Node: 14Deleting Node: 10Deleting Node: 20Deleting Node: 60Deleting Node: 25Deleting Node: 15 |
結果は、以下の通りになります。
この記事もチェック：Pythonでのバランスバイナリーツリー(平衡木)の実装について解説する
まとめ
今回は、修正後順序木探索アルゴリズムを使って二分木を削除するアルゴリズムについて説明しました。
Pythonで様々なアルゴリズムを実装するための記事を今後も続けていきます。