資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究資料結構中的B樹插入
在這裡，我們將瞭解如何在B樹中執行插入操作。假設我們有一個如下所示的B樹：
B樹示例 −
插入元素的思路與BST非常相似，但我們需要遵循一些規則。每個節點有m個子節點和m-1個元素。如果我們將一個元素插入到一個節點中，則有兩種情況。如果節點的元素少於m-1，則新元素將直接插入到該節點中。如果它有m-1個元素，那麼透過取所有元素以及將要插入的元素，然後取它們的中間值，並將中間值透過執行相同的標準傳送到該節點的根節點，然後從節點的左半部分和右半部分建立兩個單獨的列表。
假設我們要將79插入到樹中。首先，它將與根節點進行比較，它大於56。然後它將進入最右邊的子樹。現在它小於81，因此移動到左子樹。之後，它將被插入到根節點。現在有三個元素[66, 78, 79]。中位數是78，所以78將向上移動，根節點變為[79, 81]，節點的元素將被分成兩個節點。一個將包含66，另一個將包含79。
插入79後的B樹。
演算法
BTreeInsert(root, key)−
輸入 − 樹的根節點以及要插入的鍵。我們將假設該鍵不在列表中。
x := Read root if x is full, then y := new node z := new node Locate the middle object oi, stored in x, move the objects to the left of oi in to node y Move the object to the right of oi into node z. If x is an index node, then move the child pointers accordingly x->child[1] := address of y x->child[2] := address of z end if
更新於: 2020年8月11日
701 次檢視
廣告