完全B樹算法Java完成代碼。本站提示廣大學習愛好者：（完全B樹算法Java完成代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是完全B樹算法Java完成代碼正文
界說
在盤算機迷信中，B樹（英語：B-tree）是一種自均衡的樹，可以或許堅持數據有序。這類數據構造可以或許讓查找數據、次序拜訪、拔出數據及刪除的舉措，都在對數時光內完成。
為何要引入B樹?
起首，包含後面我們引見的紅黑樹是將輸出存入內存的一種外部查找樹。
而B樹是後面均衡樹算法的擴大，它支撐保留在磁盤或許收集上的符號表停止內部查找，這些文件能夠比我們之前斟酌的輸出要年夜的多（難以存入內存）。
既然內容保留在磁盤中，那末天然會由於樹的深渡過年夜而形成磁盤I/O讀寫過於頻仍（磁盤讀寫速度是無限制的），進而招致查詢效力低下。
那末下降樹的深度天然很主要了。是以，我們引入了B樹，多路查找樹。
特色
樹中每一個結點最多含有m個孩子（m>=2）；
除根結點和葉子結點外，其它每一個結點至多有[ceil(m / 2)]個孩子（個中ceil(x)是一個取下限的函數）；
若根結點不是葉子結點，則至多有2個孩子（特別情形：沒有孩子的根結點，即根結點為葉子結點，整棵樹只要一個根節點）；
一切葉子結點都湧現在統一層(最底層)，葉子結點為內部結點，保留內容，即key和value。
其他結點為外部結點，保留索引，即key和next。
外部結點的症結字key：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
內容結點的指針next：P[1], P[2], …, P[M]；個中P[1]指向症結字小於K[1]的子樹，P[M]指向症結字年夜於K[M-1]的子樹，其它P[i]指向症結字屬於(K[i-1], K[i])的子樹；
例如：（M=3）
查找和拔出
為了便利這裡用了一個特別的尖兵鍵，它小於其他一切鍵，用*表現。
一開端B樹只含有一個根結點，而根結點在初始化時僅含有該尖兵鍵。
外部結點中的每一個鍵都與一個結點相干聯，以此結點為根的子樹種，一切的鍵都年夜於等於與此結點聯系關系的鍵，但小於其他一切鍵。
這些商定在很年夜水平上可以或許簡化代碼。
代碼
點擊下載。
該代碼完成引入了尖兵鍵，代碼輸入則剔除它。
代碼裡含有尖兵鍵的B樹（將圖片保留到當地檢查，字會清楚些）：
代碼輸入的B樹（將圖片保留到當地檢查，字會清楚些）：
public class BTree<Key extends Comparable<Key>, Value>
{
// max children per B-tree node = M-1
// (must be even and greater than 2)
private static final int M = 4;
private Node root; // root of the B-tree
private int height; // height of the B-tree
private int n; // number of key-value pairs in the B-tree
// helper B-tree node data type
private static final class Node
{
private int m; // number of children
private Entry[] children = new Entry[M]; // the array of children
// create a node with k children
private Node(int k)
{
m = k;
}
}
// internal nodes: only use key and next
// external nodes: only use key and value
private static class Entry
{
private Comparable key;
private Object val;
private Node next; // helper field to iterate over array entries
public Entry(Comparable key, Object val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Initializes an empty B-tree.
*/
public BTree()
{
root = new Node(0);
}
/**
* Returns true if this symbol table is empty.
* @return {@code true} if this symbol table is empty; {@code false} otherwise
*/
public boolean isEmpty()
{
return size() == 0;
}
/**
* Returns the number of key-value pairs in this symbol table.
* @return the number of key-value pairs in this symbol table
*/
public int size()
{
return n;
}
/**
* Returns the height of this B-tree (for debugging).
*
* @return the height of this B-tree
*/
public int height()
{
return height;
}
/**
* Returns the value associated with the given key.
*
* @param key the key
* @return the value associated with the given key if the key is in the symbol table
* and {@code null} if the key is not in the symbol table
* @throws NullPointerException if {@code key} is {@code null}
*/
public Value get(Key key)
{
if (key == null)
{
throw new NullPointerException("key must not be null");
}
return search(root, key, height);
}
@SuppressWarnings("unchecked")
private Value search(Node x, Key key, int ht)
{
Entry[] children = x.children;
// external node到最底層葉子結點，遍歷
if (ht == 0)
{
for (int j = 0; j < x.m; j++)
{
if (eq(key, children[j].key))
{
return (Value) children[j].val;
}
}
}
// internal node遞歸查找next地址
else
{
for (int j = 0; j < x.m; j++)
{
if (j+1 == x.m || less(key, children[j+1].key))
{
return search(children[j].next, key, ht-1);
}
}
}
return null;
}
/**
* Inserts the key-value pair into the symbol table, overwriting the old value
* with the new value if the key is already in the symbol table.
* If the value is {@code null}, this effectively deletes the key from the symbol table.
*
* @param key the key
* @param val the value
* @throws NullPointerException if {@code key} is {@code null}
*/
public void put(Key key, Value val)
{
if (key == null)
{
throw new NullPointerException("key must not be null");
}
Node u = insert(root, key, val, height); //決裂後生成的右結點
n++;
if (u == null)
{
return;
}
// need to split root重組root
Node t = new Node(2);
t.children[0] = new Entry(root.children[0].key, null, root);
t.children[1] = new Entry(u.children[0].key, null, u);
root = t;
height++;
}
private Node insert(Node h, Key key, Value val, int ht)
{
int j;
Entry t = new Entry(key, val, null);
// external node內部結點，也是葉子結點，在樹的最底層，存的是內容value
if (ht == 0)
{
for (j = 0; j < h.m; j++)
{
if (less(key, h.children[j].key))
{
break;
}
}
}
// internal node外部結點，存的是next地址
else
{
for (j = 0; j < h.m; j++)
{
if ((j+1 == h.m) || less(key, h.children[j+1].key))
{
Node u = insert(h.children[j++].next, key, val, ht-1);
if (u == null)
{
return null;
}
t.key = u.children[0].key;
t.next = u;
break;
}
}
}
for (int i = h.m; i > j; i--)
{
h.children[i] = h.children[i-1];
}
h.children[j] = t;
h.m++;
if (h.m < M)
{
return null;
}
else
{ //決裂結點
return split(h);
}
}
// split node in half
private Node split(Node h)
{
Node t = new Node(M/2);
h.m = M/2;
for (int j = 0; j < M/2; j++)
{
t.children[j] = h.children[M/2+j];
}
return t;
}
/**
* Returns a string representation of this B-tree (for debugging).
*
* @return a string representation of this B-tree.
*/
public String toString()
{
return toString(root, height, "") + "\n";
}
private String toString(Node h, int ht, String indent)
{
StringBuilder s = new StringBuilder();
Entry[] children = h.children;
if (ht == 0)
{
for (int j = 0; j < h.m; j++)
{
s.append(indent + children[j].key + " " + children[j].val + "\n");
}
}
else
{
for (int j = 0; j < h.m; j++)
{
if (j > 0)
{
s.append(indent + "(" + children[j].key + ")\n");
}
s.append(toString(children[j].next, ht-1, indent + " "));
}
}
return s.toString();
}
// comparison functions - make Comparable instead of Key to avoid casts
private boolean less(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) < 0;
}
private boolean eq(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) == 0;
}
/**
* Unit tests the {@code BTree} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args)
{
BTree<String, String> st = new BTree<String, String>();
st.put("www.cs.princeton.edu", "128.112.136.12");
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.128.15");
st.put("www.yale.edu", "130.132.143.21");
st.put("www.simpsons.com", "209.052.165.60");
st.put("www.apple.com", "17.112.152.32");
st.put("www.amazon.com", "207.171.182.16");
st.put("www.ebay.com", "66.135.192.87");
st.put("www.cnn.com", "64.236.16.20");
st.put("www.谷歌.com", "216.239.41.99");
st.put("www.nytimes.com", "199.239.136.200");
st.put("www.microsoft.com", "207.126.99.140");
st.put("www.dell.com", "143.166.224.230");
st.put("www.slashdot.org", "66.35.250.151");
st.put("www.espn.com", "199.181.135.201");
st.put("www.weather.com", "63.111.66.11");
st.put("www.yahoo.com", "216.109.118.65");
System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu"));
System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));
System.out.println("simpsons.com: " + st.get("www.simpsons.com"));
System.out.println("apple.com: " + st.get("www.apple.com"));
System.out.println("ebay.com: " + st.get("www.ebay.com"));
System.out.println("dell.com: " + st.get("www.dell.com"));
System.out.println();
System.out.println("size: " + st.size());
System.out.println("height: " + st.height());
System.out.println(st);
System.out.println();
}
}
輸入：
cs.princeton.edu: 128.112.136.12
hardvardsucks.com: null
simpsons.com: 209.052.165.60
apple.com: 17.112.152.32
ebay.com: 66.135.192.87
dell.com: 143.166.224.230
size: 17
height: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.谷歌.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
以上就是本文的全體內容，願望對年夜家的進修有所贊助，也願望年夜家多多支撐。
