определение
В информатике B-дерево-это дерево самобаланса, которое поддерживает данные в порядке. Эта структура данных позволяет выполнять поиск данных, последовательный доступ, вставлять данные и операции удаления в логарифмическом времени.
Зачем представлять B-Tree?
Прежде всего, включая красное и черное дерево, которое мы представили ранее, представляет собой внутреннее дерево поиска , которое хранит ввод в память .
B-Tree является расширением предыдущего алгоритма дерева баланса. Он поддерживает внешние поиски символов, сохраненные на диске или сети . Эти файлы могут быть намного больше, чем вход, который мы рассматривали ранее (трудно хранить в памяти).
Поскольку содержание хранится на диске, диск ввода/вывода читает и пишет слишком часто из -за большой глубины дерева (скорость чтения и записи диска ограничена), что приводит к неэффективной эффективности запроса.
Тогда, естественно, важно уменьшить глубину дерева. Поэтому мы вводим B-Tree, многолетнее поисковое дерево.
Функции
Каждый узел в дереве содержит больше всего м детей (M> = 2);
За исключением корневого узла и листового узла, каждый узел имеет, по крайней мере, [ceil (m/2)] детей (где Ceil (x) - это функция, которая занимает верхний предел);
Если корневой узел не является узел листьев, будет не менее 2 детей (особый случай: нет корневого узла для детей, то есть корневой узел - это листовой узел, а у всего дерева есть только один корневой узел);
Все листовые узлы появляются в одном слое (нижний слой), а листовые узлы являются внешними узлами, которые сохраняют содержание, а именно ключ и значение .
Другие узлы - это внутренние узлы, которые сохраняют индекс, а именно ключ и следующий .
Ключевые слова внутренних узлов: k [1], k [2],…, k [m-1]; и k [i] <k [i+1];
Указатели рядом с узлом содержимого: 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-дерево содержит только один корневой узел, а корневой узел содержит только клавишу Sentinel при инициативе.
Каждый ключ во внутреннем узле связан с узлом. Все ключи больше или равны ключу, связанному с этим узлом, но меньше всех других клавиш.
Эти конвенции могут значительно упростить код.
Код
Нажмите, чтобы скачать.
Эта реализация кода вводит ключ Sentinel, и вывод кода устраняет его.
B-дерево с ключом Sentinel в коде (сохраните изображение локально для просмотра, и слова будут яснее):
Вывод B-Tree кодом (сохраните изображение локально для просмотра, и слова будут яснее):
открытый класс btree <ключ расширяется сопоставимо <key>, значение> {// максимальное количество детей на узел B-Tree = M-1 // (должно быть даже 2) частный статический конечный конечный int m = 4; Частный узел корень; // корень из B-Tree Private Int Height; // высота B-Tree Private Int N; // Количество пар клавишных значений в B-Tree // Helper B-Tree Node Type Тип частного статического окончательного узла класса {private int m; // Количество детей частной входа [] дети = новая запись [m]; // массив детей // Создать узел с K Kids Private Node (int k) {m = k; }} // Внутренние узлы: только используйте клавишу и следующие // внешние узлы: только используйте клавишу и значение Private Static Class intry {private сопоставимый ключ; частный объект val; частный узел следующий; // Поле HERPER TOTETATION OUTER ARRY ARTIORS PULTICE Вход (сопоставимый ключ, объект VAL, NODE NEXT) {this.key = key; this.val = val; this.next = Далее; }} /*** Инициализирует пустую B-три. */ public btree () {root = new Node (0); } /*** Возвращает true, если эта таблица символов пуста. * @return {@code true} Если эта таблица символов пуста; {@code false} иначе */ public boolean isempty () {return size () == 0; } /*** Возвращает количество пар клавишных значений в этой таблице символов. * @return Количество пар клавишных значений в этой таблице символов */ public int size () {return n; } /*** Возвращает высоту этой B-три (для отладки). * * @return Высота этой B-Tree */ public int height () {return Height; } /*** Возвращает значение, связанное с данным ключом. * * @param ключа клавиши * @return значения, связанного с данной ключом, если ключ находится в таблице символов * и {@code null}, если ключ не находится в таблице символов * @Throws NullPointerException, если {@Code key} is {@code null} */ public get key) {if = null) {добавлять nully -newex neultex inultex inulpex inulle. нулевой"); } вернуть поиск (корень, ключ, высота); } @Suppresswarnings ("unchecked") // Внешний узел к самым низким листовым узлу, Traverse if (ht == 0) {for (int j = 0; j <xm; j ++) {if (eq (key, kids [j] .key)) {return (значение) дети [j] .val; }}} // Внутренний узел рекурсивно ищет следующий адрес else {for (int j = 0; j <xm; j ++) {if (j+1 == xm || mess (key, дети [j+1] .key)) {return search (kids [j] .next, key, ht-1); }}} return null; } /** * Вставка пара клавиш значений в таблицу символов, перезаписывая старое значение * с новым значением, если ключ уже находится в таблице символов. * Если значение равно {@code null}, это эффективно удаляет ключ из таблицы символов. * * @param ключа клавиши * @param Val значение * @Throws nullPointerException if {@code key} is {@code null} */ public void put (ключ, значение val) {if (key == null) {througe nullpointerException ("ключ не должен быть null"); } Узел u = insert (root, key, val, height); // правый узел, сгенерированный после разделения n ++; if (u == null) {return; } // необходимо разделить корневую реорганизацию корневого узла t = новый узел (2); T.Children [0] = Новая запись (root.Children [0] .Key, null, root); T.Children [1] = Новая запись (U.Children [0] .Key, NULL, U); root = t; высота ++; } private Node INSERT (Узел H, клавиша клавиши, значение val, int ht) {int j; Запись t = новая запись (ключ, val, null); // внешний узел внешнего узла, который также является листовым узлом. В нижней части дерева значение содержания сохраняется, если (ht == 0) {for (j = 0; j <hm; j ++) {if (mess (key, h.children [j] .key)) {break; }}} // Внутренний узел внутри узла является следующим адресом else {for (j = 0; j <hm; j ++) {if ((j+1 == hm) || mess (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; перерыв; }}} for (int i = hm; i> j; i--) {h.children [i] = h.children [i-1]; } H.Children [j] = t; H.M ++; if (hm <m) {return null; } else {// разделить node return split (h); }} // разделить узел в половине закрытого узла сплит (узел h) {узел t = новый узел (M/2); hm = m/2; for (int j = 0; j <m/2; j ++) {t.children [j] = h.children [m/2+j]; } return t; } /*** Возвращает строковое представление этой B-трией (для отладки). * * @return Строковое представление этой B-три. */ public String toString () {return toString (root, height, "") + "/ n"; } private String toString (Node H, int ht, String adpry) {stringBuilder s = new StringBuilder (); Вход [] дети = H.Children; if (ht == 0) {for (int j = 0; j <hm; j ++) {s.append (odent + children [j] .key + "" + дети [j] .val + "/n"); }} else {for (int j = 0; j <hm; j ++) {if (j> 0) {s.append (odent + "(" + children [j] .key + ")/n"); } s.Append (toString (дети [j] .next, ht-1, odent + "")); }} return s.toString (); } // Функции сравнения - Сделайте сопоставимым вместо ключа, чтобы избежать Casts Private Boolean Less (сопоставимый K1, сопоставимый K2) {return k1.compareto (k2) <0; } Частный логический уравнение (сопоставимый K1, сопоставимый K2) {return k1.compareto (k2) == 0; } /*** Модульные тесты {@code btree} тип данных. * * @param Args Аргументы командной строки */ 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.google.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 ("hardvardscucks.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 ("Size:" + St.size ()); System.out.println («Высота:» + St.Height ()); System.out.println (ST); System.out.println (); }} Выход:
cs.princeton.edu: 128.112.136.12
hardvardscks.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
Размер: 17
Высота: 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.google.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
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.