Pythonを使ってB+ツリーの削除操作コードを書く
Bツリーの概念
B ツリーの削除操作では、まず削除されたノードの場所を見つけて、次にノードのキーの数を決定する必要があります。
ノード内のキーの数が最小数を超えた場合は、ノードを直接削除してください。
以下に示すように、「40」を削除します。
ノード内に正確な最小数のキーがある場合、削除には兄弟ノードから借用し、中間キーを追加する必要があります。兄弟ノードから親ノードへ。以下に示すように、「5」を削除します:
コンテンツ ノードを削除します。ノード内のキーの数が最小数を超えている場合は、単に削除します。リーフ ノードからキーを削除し、内部ノードからキーを削除します。内部ノードの空いたスペースを順序サクセサで埋めます。以下に示すように、「45」を削除します:
コンテンツ ノードを削除します。ノード内に正確な最小数のキーがある場合は、コンテンツ ノードを削除します。キーと直接 兄弟はキーを借用し、借用したキーでインデックス内の空のスペースを埋めます。以下に示すように、「35」を削除します。
#コンテンツ ノードを削除し、親ノードの上に空白スペースを生成します。キーを削除した後、空のスペースをその兄弟とマージし、親ノードの空のスペースを順序サクセサーで埋めます。以下に示すように、「25」を削除します。
木の高さを縮小させる削除操作は、以下に示すように、「55」を削除します。
#Python は B ツリー削除操作を実装します
import math
# 创建节点
class Node:
def __init__(self, order):
self.order = order
self.values = []
self.keys = []
self.nextKey = None
self.parent = None
self.check_leaf = False
# 插入叶子
def insert_at_leaf(self, leaf, value, key):
if (self.values):
temp1 = self.values
for i in range(len(temp1)):
if (value == temp1[i]):
self.keys[i].append(key)
break
elif (value < temp1[i]):
self.values = self.values[:i] + [value] + self.values[i:]
self.keys = self.keys[:i] + [[key]] + self.keys[i:]
break
elif (i + 1 == len(temp1)):
self.values.append(value)
self.keys.append([key])
break
else:
self.values = [value]
self.keys = [[key]]
# B+树
class BplusTree:
def __init__(self, order):
self.root = Node(order)
self.root.check_leaf = True
# 插入节点
def insert(self, value, key):
value = str(value)
old_node = self.search(value)
old_node.insert_at_leaf(old_node, value, key)
if (len(old_node.values) == old_node.order):
node1 = Node(old_node.order)
node1.check_leaf = True
node1.parent = old_node.parent
mid = int(math.ceil(old_node.order / 2)) - 1
node1.values = old_node.values[mid + 1:]
node1.keys = old_node.keys[mid + 1:]
node1.nextKey = old_node.nextKey
old_node.values = old_node.values[:mid + 1]
old_node.keys = old_node.keys[:mid + 1]
old_node.nextKey = node1
self.insert_in_parent(old_node, node1.values[0], node1)
def search(self, value):
current_node = self.root
while(current_node.check_leaf == False):
temp2 = current_node.values
for i in range(len(temp2)):
if (value == temp2[i]):
current_node = current_node.keys[i + 1]
break
elif (value < temp2[i]):
current_node = current_node.keys[i]
break
elif (i + 1 == len(current_node.values)):
current_node = current_node.keys[i + 1]
break
return current_node
# 查找节点
def find(self, value, key):
l = self.search(value)
for i, item in enumerate(l.values):
if item == value:
if key in l.keys[i]:
return True
else:
return False
return False
# 在父级插入
def insert_in_parent(self, n, value, ndash):
if (self.root == n):
rootNode = Node(n.order)
rootNode.values = [value]
rootNode.keys = [n, ndash]
self.root = rootNode
n.parent = rootNode
ndash.parent = rootNode
return
parentNode = n.parent
temp3 = parentNode.keys
for i in range(len(temp3)):
if (temp3[i] == n):
parentNode.values = parentNode.values[:i] + \
[value] + parentNode.values[i:]
parentNode.keys = parentNode.keys[:i +
1] + [ndash] + parentNode.keys[i + 1:]
if (len(parentNode.keys) > parentNode.order):
parentdash = Node(parentNode.order)
parentdash.parent = parentNode.parent
mid = int(math.ceil(parentNode.order / 2)) - 1
parentdash.values = parentNode.values[mid + 1:]
parentdash.keys = parentNode.keys[mid + 1:]
value_ = parentNode.values[mid]
if (mid == 0):
parentNode.values = parentNode.values[:mid + 1]
else:
parentNode.values = parentNode.values[:mid]
parentNode.keys = parentNode.keys[:mid + 1]
for j in parentNode.keys:
j.parent = parentNode
for j in parentdash.keys:
j.parent = parentdash
self.insert_in_parent(parentNode, value_, parentdash)
# 删除节点
def delete(self, value, key):
node_ = self.search(value)
temp = 0
for i, item in enumerate(node_.values):
if item == value:
temp = 1
if key in node_.keys[i]:
if len(node_.keys[i]) > 1:
node_.keys[i].pop(node_.keys[i].index(key))
elif node_ == self.root:
node_.values.pop(i)
node_.keys.pop(i)
else:
node_.keys[i].pop(node_.keys[i].index(key))
del node_.keys[i]
node_.values.pop(node_.values.index(value))
self.deleteEntry(node_, value, key)
else:
print("Value not in Key")
return
if temp == 0:
print("Value not in Tree")
return
# 删除条目
def deleteEntry(self, node_, value, key):
if not node_.check_leaf:
for i, item in enumerate(node_.keys):
if item == key:
node_.keys.pop(i)
break
for i, item in enumerate(node_.values):
if item == value:
node_.values.pop(i)
break
if self.root == node_ and len(node_.keys) == 1:
self.root = node_.keys[0]
node_.keys[0].parent = None
del node_
return
elif (len(node_.keys) < int(math.ceil(node_.order / 2)) and node_.check_leaf == False) or (len(node_.values) < int(math.ceil((node_.order - 1) / 2)) and node_.check_leaf == True):
is_predecessor = 0
parentNode = node_.parent
PrevNode = -1
NextNode = -1
PrevK = -1
PostK = -1
for i, item in enumerate(parentNode.keys):
if item == node_:
if i > 0:
PrevNode = parentNode.keys[i - 1]
PrevK = parentNode.values[i - 1]
if i < len(parentNode.keys) - 1:
NextNode = parentNode.keys[i + 1]
PostK = parentNode.values[i]
if PrevNode == -1:
ndash = NextNode
value_ = PostK
elif NextNode == -1:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
else:
if len(node_.values) + len(NextNode.values) < node_.order:
ndash = NextNode
value_ = PostK
else:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
if len(node_.values) + len(ndash.values) < node_.order:
if is_predecessor == 0:
node_, ndash = ndash, node_
ndash.keys += node_.keys
if not node_.check_leaf:
ndash.values.append(value_)
else:
ndash.nextKey = node_.nextKey
ndash.values += node_.values
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
self.deleteEntry(node_.parent, value_, node_)
del node_
else:
if is_predecessor == 1:
if not node_.check_leaf:
ndashpm = ndash.keys.pop(-1)
ndashkm_1 = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [value_] + node_.values
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
p.values[i] = ndashkm_1
break
else:
ndashpm = ndash.keys.pop(-1)
ndashkm = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [ndashkm] + node_.values
parentNode = node_.parent
for i, item in enumerate(p.values):
if item == value_:
parentNode.values[i] = ndashkm
break
else:
if not node_.check_leaf:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [value_]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndashk0
break
else:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [ndashk0]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndash.values[0]
break
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
if not node_.check_leaf:
for j in node_.keys:
j.parent = node_
if not parentNode.check_leaf:
for j in parentNode.keys:
j.parent = parentNode
# 输出B+树
def printTree(tree):
lst = [tree.root]
level = [0]
leaf = None
flag = 0
lev_leaf = 0
node1 = Node(str(level[0]) + str(tree.root.values))
while (len(lst) != 0):
x = lst.pop(0)
lev = level.pop(0)
if (x.check_leaf == False):
for i, item in enumerate(x.keys):
print(item.values)
else:
for i, item in enumerate(x.keys):
print(item.values)
if (flag == 0):
lev_leaf = lev
leaf = x
flag = 1
record_len = 3
bplustree = BplusTree(record_len)
bplustree.insert('5', '33')
bplustree.insert('15', '21')
bplustree.insert('25', '31')
bplustree.insert('35', '41')
bplustree.insert('45', '10')
printTree(bplustree)
if(bplustree.find('5', '34')):
print("Found")
else:
print("Not found")ログイン後にコピー
以上がPythonを使ってB+ツリーの削除操作コードを書くの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
AI Hentai Generator
AIヘンタイを無料で生成します。
人気の記事
アサシンのクリードシャドウズ：シーシェルリドルソリューション
3週間前
By DDD
Windows11 KB5054979の新しいものと更新の問題を修正する方法
2週間前
By DDD
Atomfallのクレーンコントロールキーカードを見つける場所
3週間前
By DDD
R.E.P.O.で節約説明した（そしてファイルを保存）
1 か月前
By 尊渡假赌尊渡假赌尊渡假赌
アサシンクリードシャドウ - 鍛冶屋を見つけて武器と鎧のカスタマイズを解除する方法
4週間前
By DDD
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
Gmailメールのログイン入り口はどこですか？
7569
15
7569
15
CakePHP チュートリアル
1386
52
1386
52
Steamのアカウント名の形式は何ですか
87
11
87
11
NYTの接続はヒントと回答です
28
108
28
108
INNODBフルテキスト検索機能を説明します。
Apr 02, 2025 pm 06:09 PM
INNODBのフルテキスト検索機能は非常に強力であり、データベースクエリの効率と大量のテキストデータを処理する能力を大幅に改善できます。 1）INNODBは、倒立インデックスを介してフルテキスト検索を実装し、基本的および高度な検索クエリをサポートします。 2）一致を使用してキーワードを使用して、ブールモードとフレーズ検索を検索、サポートします。 3）最適化方法には、単語セグメンテーションテクノロジーの使用、インデックスの定期的な再構築、およびパフォーマンスと精度を改善するためのキャッシュサイズの調整が含まれます。
Alter Tableステートメントを使用してMySQLのテーブルをどのように変更しますか？
Mar 19, 2025 pm 03:51 PM
この記事では、MySQLのAlter Tableステートメントを使用して、列の追加/ドロップ、テーブル/列の名前の変更、列データ型の変更など、テーブルを変更することについて説明します。
MySQLでインデックスを使用するよりも、フルテーブルスキャンがいつ速くなるのでしょうか？
Apr 09, 2025 am 12:05 AM
完全なテーブルスキャンは、MySQLでインデックスを使用するよりも速い場合があります。特定のケースには以下が含まれます。1）データボリュームは小さい。 2）クエリが大量のデータを返すとき。 3）インデックス列が高度に選択的でない場合。 4）複雑なクエリの場合。クエリプランを分析し、インデックスを最適化し、オーバーインデックスを回避し、テーブルを定期的にメンテナンスすることにより、実際のアプリケーションで最良の選択をすることができます。
Windows 7にMySQLをインストールできますか？
Apr 08, 2025 pm 03:21 PM
はい、MySQLはWindows 7にインストールできます。MicrosoftはWindows 7のサポートを停止しましたが、MySQLは引き続き互換性があります。ただし、インストールプロセス中に次のポイントに注意する必要があります。WindowsのMySQLインストーラーをダウンロードしてください。 MySQL（コミュニティまたはエンタープライズ）の適切なバージョンを選択します。インストールプロセス中に適切なインストールディレクトリと文字セットを選択します。ルートユーザーパスワードを設定し、適切に保ちます。テストのためにデータベースに接続します。 Windows 7の互換性とセキュリティの問題に注意してください。サポートされているオペレーティングシステムにアップグレードすることをお勧めします。
INNODBのクラスターインデックスと非クラスターインデックス（セカンダリインデックス）の違い。
Apr 02, 2025 pm 06:25 PM
クラスター化されたインデックスと非クラスター化されたインデックスの違いは次のとおりです。1。クラスター化されたインデックスは、インデックス構造にデータを保存します。これは、プライマリキーと範囲でクエリするのに適しています。 2.非クラスター化されたインデックスストアは、インデックスキー値とデータの行へのポインターであり、非プリマリーキー列クエリに適しています。
人気のあるMySQL GUIツール（MySQL Workbench、PhpMyAdminなど）は何ですか？
Mar 21, 2025 pm 06:28 PM
記事では、MySQLワークベンチやPHPMyAdminなどの人気のあるMySQL GUIツールについて説明し、初心者と上級ユーザーの機能と適合性を比較します。[159文字]
MySQLの大きなデータセットをどのように処理しますか？
Mar 21, 2025 pm 12:15 PM
記事では、MySQLで大規模なデータセットを処理するための戦略について説明します。これには、パーティション化、シャード、インデックス作成、クエリ最適化などがあります。
ドロップテーブルステートメントを使用してMySQLにテーブルをドロップするにはどうすればよいですか？
Mar 19, 2025 pm 03:52 PM
この記事では、ドロップテーブルステートメントを使用してMySQLのドロップテーブルについて説明し、予防策とリスクを強調しています。これは、バックアップなしでアクションが不可逆的であることを強調し、回復方法と潜在的な生産環境の危険を詳述しています。
