Определяю структуру листа Б-дерева порядка 2 (n=2) следующим образом:

Код

struct Page                 {                         int RAmount;            //Фактическое число элементов на странице                         Page *p0;               //Указатель на самого левого потомка страницы                         struct                         {                                 int key;           //Значение одного ключа страницы                                 Page *p;        //Указатель на страницу-потомок                         } key_pt[4];          //Массив, хранящий значения ключей страницы и указатели на потомков страницы                 };                 Page *root;                  //Указатель на корень B-дерева

Так вот, структуру-то определил, класс забацал, а алгоритмом работы с ними нет (добавление ключа, удаление ключа, поиск ключа)! Почитал Вирта, че т оч сухо как-то, не понравилось. Может у кого есть какие-нибудь полезные сведения о этих пихтовых?

М	Пользуйтесь кнопкой "код!" sergej.z

Знаю сайт с визуализаторами http://rain.ifmo.ru/cat/view.php/vis/trees
Добавлено @ 19:10
Знаю сайт с визуализаторами на эту тему http://rain.ifmo.ru/cat/view.php/vis/trees
Нормально про этих пихтовых было написано в Кормэне Алгоритмы: Построение и Анализ

Стоит посмотреть Дейта "Введение в базы данных", помниться у него Б-деревья очень подробно описаны.

1. зачем нужен

Цитата

Page *p0; //Указатель на самого левого потомка страницы

если есть массив ,где все потомки?

2.

Цитата

int key; //Значение одного ключа страницы

это номер(индекс) узла или некая полезная нагрузка?

Код

program bin_trees; const n_child = 3; type PPage = ^TPage;      TPage = record                 RAmount : integer;                 data : integer;                 key_pt : array[1..n_child]of PPage;              end; var root : PPage;     ind : longint; procedure AddElement(data : integer); var ll,vr : PPage;     i,lev : integer;    procedure GetFreeElement(El : PPage;l : integer);    var i : integer;    begin       if  El^.RAmount < n_child then       begin          if l < lev then             begin                lev := l;                ll := El;             end       end else          for i := 1 to n_child do             GetFreeElement(El^.key_pt[i],l + 1);    end; begin    ll := root;    lev := maxint;    if ll = nil then       begin          new(ll);          ll^.RAmount := 0;          ll^.data := data;          for i := 1 to n_child do             ll^.key_pt[i] := nil;          root := ll;       end else          begin             GetFreeElement(root,0);             i := 1;             while ll^.key_pt[i] <> nil do inc(i);             new(vr);             ll^.key_pt[i] := vr;             ll^.RAmount := ll^.RAmount + 1;             vr^.RAmount := 0;             vr^.data := data;             for i := 1 to n_child do                vr^.key_pt[i] := nil;          end; end; procedure SetElementByKey(key : longint;data : integer); var lkey : longint;     ll,vr : PPage;     i : integer; begin    lkey := key;    ll := root;    if ll = nil then       begin          new(ll);          ll^.Ramount := 0;          ll^.data := 0;          for i := 1 to n_child do             ll^.key_pt[i] := nil;          root := ll;       end;    while lkey > 0 do       begin          if ll^.key_pt[lkey mod (n_child + 1)] = nil then             begin                ll^.RAmount := ll^.RAmount + 1;                new(vr);                vr^.RAmount := 0;                vr^.data := 0;                for i := 1 to n_child do                   vr^.key_pt[i] := nil;                ll^.key_pt[lkey mod (n_child + 1)] := vr;             end;          ll := ll^.key_pt[lkey mod (n_child + 1)];          lkey := lkey div (n_child + 1);       end;    ll^.data := data; end; begin    AddElement(5);    AddElement(6);    AddElement(7);    AddElement(8);    AddElement(9);    AddElement(10);    ind := n_child + 1;    SetElementByKey(ind * 1 + 1,100);    SetElementByKey(ind * 2 + 1,101);    SetElementByKey(ind * 2 + 2,102); end.

я немного изменил структуру данных ,убрал некоторые поля в которых не увидел надобности.
Пока только 2 процедуры добавления элемента : AddElement -- процедура сама решает куда добавить новый элемент. SetElementByKey если элемент с ключом key не существует то добавляет ,иначе изменяет элемент.

Код

key = сумма (n_child + 1)^(i - 1) * numb[i]       i=1..n-1

n_child -- количество наследников у каждого элемента. numb -- номер наследника на которого надо перейти на iтом уровне дерева.

ЗЫ
сейчас допишу все остальные процедуры.

Цитата(eskaflone @ 24.11.2005, 15:40)

type PPage = ^TPage;     TPage = record                 RAmount : integer;                 data : integer;                 key_pt : array[1..n_child]of PPage;             end;

eskaflone, все конечно хорошо, но эт не структура Б-дерева! Б-дерево - это когда есть некоторое число n (порядок б-дерева) и на каждой вершине, кроме корневой, размещено от n до 2n ключей (значений), причем все листья на одном уровне, каждая вершина имеет (m+1)-го потомка, где m - число ключей на этой странице.

по Кнуту :
Б-дерево n-го порядка имеет потомков от n/2 до n

попробую реализовать. Есть какие то конкретные вопросы ,или надо просто все полностью?

Цитата(eskaflone @ 26.11.2005, 12:50)

Есть какие то конкретные вопросы ,или надо просто все полностью?

Надо все полностью.

Кнута не видел, но так не получится, т.к. число потомков строго зависит от числа ключей на странице, то есть если их максимально 4, то число потомков у данной страницы - 5, т.е. на первой странице-потомке будут все ключи, значения которых меньше первого ключа с отцовской страницы, на второй - которые больше 1, но меньше 2 ключа с отцовской и соответственно так далее. Вот такая вот ерунда, эти б-деревья.

А зачем вообще эти бета деревья? Они работают крайне нестабильно. Сложнейшие алгоритмы на загрузку, на выгрузку, на здвиги. Отслеживание адресов.
Чем Б-деревья проигрывают массивам?

Цитата(CosmoMan @ 27.11.2005, 11:20)

А зачем вообще эти бета деревья? Они работают крайне нестабильно. Сложнейшие алгоритмы на загрузку, на выгрузку, на здвиги. Отслеживание адресов. Чем Б-деревья проигрывают массивам?

На самом деле, лично мне они нужны вовсе как тренировочное задание по такому курсу, как "Теория графов", да и в практических задачах обычно используют их модификации, типа Б+ или Б++ деревья, те пошустрее будут.

посмотри это ,там бинарные Б-деревья (2 потомка) алгоритмы добавления и удаления надо просто обобщить.

Присоединённый файл ( Кол-во скачиваний: 96 )
 TREE.zip 3,82 Kb

Цитата(eskaflone @ 28.11.2005, 09:42)

посмотри это ,там бинарные Б-деревья (2 потомка) алгоритмы добавления и удаления надо просто обобщить

Не очень хорошая реализация, да и не совсем то, что надо.

В общем, потратив массу времени на поиски, ничего хорощего не нашел взял в руки незабвенного Вирта и... в общем, все сделал сам о проделанной работе: реализован класс для работы с B-деревьями порядка 2, функции добавления и удаления ключа (со всем тем бредом, типа, балансировки, перестройки, слияния и т.д.) заимствовал у Вирта, переводил Modul-у в нормальный человеческий С++, конструктор копирования, конструктор с указанием ряда ключей, деструктор, поиск, вывод на печать сделал сам.

Вот исходный код:

Код

class B_tree {         public:                 B_tree ();                             //Конструктор "пустого" B-дерева                 B_tree (int amount, ...);       //Конструктор B-дерева, состоящего из amount элементов                 B_tree (const B_tree& b_tree);    //Конструктор копирования                 ~B_tree ();                          //Деструктор B-дерева                 void Add (int key);               //Добавление ключа key в структуру B-дерева                 bool Search (int key);          //Поиск ключа в B-дереве (true - найден, false - не найден)                 void Delete (int key);          //Удаление всех экземпляров ключа key в B-дереве, при отсутствии данного ключа структура остается без изменений                 void Print ();                       //Обход и вывод B-дерева на печать способом, используемым при составлении оглавления книг                  private:                 struct Page                 {                         int RAmount;            //Фактическое число элементов на странице                         Page *p0;               //Указатель на самого левого потомка страницы                         struct Item                         {                                 int key;           //Значение одного ключа страницы                                 Page *p;        //Указатель на страницу-потомок                                 int count;        //Число экземпляров данного ключа, хранимых на странице                         } key_pt[4];           //Массив, хранящий значения ключей страницы и указатели на потомков страницы                 } *root;                         //Указатель на корень B-дерева                 void search_add_key (int key, Page *a, bool& grow, Page::Item& v);                                                 //Рекурсивная функция, выполняющая добавление ключа key в структуру B-дерева; a - указатель на страницу, grow - "B-дерево стало выше", v - передаваемый вверх элемент                 void print_b_tree (Page *a, int level);                                                 //Рекурсивная фунцкия, выполняющая печать B-дерева с уровня level                 bool search_key (int key, Page *a);                                                 //Рекурсивная функция, выполняющая поиск ключа в B-дереве (true - ключ найден, false - не найден)                 void delete_key (int key, Page *a, bool& smallsize);                                                 //Рекурсивная функция, выполняющая удаление ключа key из структуры B-дерева, a - указатель на страницу, smallsize - "страница a мала", требуется слияние страниц                 void del (int R, Page *a, Page *q, bool& smallsize);                                                 //Рекурсивная функция, выполняющая балансировку B-дерева после удаления ключа key из его структуры, при необходимости производит слияние страниц                 void fusion (Page *father, Page *son, int R, bool& smallsize);                                                 //Функция, выполняющая слияние страниц B-дерева, father - "страница отец", son - "страница-сын отца", на которой число элементов меньше допустимого, R - индек удаляемого из страницы-отца элемента, smallsize - "страница-отец мала"                  void destroy (Page *a);            //"Деструктор" вершины a B-дерева                 void copy (Page *a, Page *b);    //Рекурсивная функция, создающая копию b страницы B-дерева a }; B_tree::B_tree() {         root = NULL; } B_tree::B_tree (int amount, ...) {         short i = 0;         root = NULL;         va_list key_vl;         va_start (key_vl, amount);         while ((key_vl != NULL) && (++i <= amount))                 Add (va_arg (key_vl, int));         va_end (key_vl); } B_tree::B_tree (const B_tree& b_tree) {         root = new Page;         if (b_tree.root != NULL)                 copy (b_tree.root, root);         else             root = NULL; } void B_tree::copy (Page *a, Page *b) {         Page *p1, *p2, *p3, *p4, *p5;         if (a != NULL)         {             b->RAmount = a->RAmount;             for (int i=0; i < a->RAmount; i++)             {                     b->key_pt[i].key = a->key_pt[i].key;                     b->key_pt[i].count = a->key_pt[i].count;             }             if ((a->RAmount >= 1) && (a->p0 != NULL))             {                     p1 = new Page;                     p2 = new Page;             }             else             {                         p1 = NULL;                     p2 = NULL;             }             if ((a->RAmount >= 2) && (a->p0 != NULL))                     p3 = new Page;             else                     p3 = NULL;             if ((a->RAmount >= 3) && (a->p0 != NULL))                     p4 = new Page;             else                     p4 = NULL;             if ((a->RAmount == 4) && (a->p0 != NULL))                     p5 = new Page;             else                     p5 = NULL;             b->p0 = p1;             b->key_pt[0].p = p2;             b->key_pt[1].p = p3;             b->key_pt[2].p = p4;             b->key_pt[3].p = p5;             if (a->RAmount >= 1)             {                     copy (a->p0, p1);                     copy (a->key_pt[0].p, p2);             }             if (a->RAmount >= 2)                     copy (a->key_pt[1].p, p3);             if (a->RAmount == 3)                     copy (a->key_pt[2].p, p4);             if (a->RAmount == 4)                     copy (a->key_pt[3].p, p5);         } } B_tree::~B_tree() {         destroy (root);         root = NULL; } void B_tree::destroy (Page *a) {         Page *p1, *p2, *p3, *p4, *p5;         if (a != NULL)         {             if (a->RAmount >= 1)             {                     p1 = a->p0;                     p2 = a->key_pt[0].p;             }             else             {                     p1 = NULL;                     p2 = NULL;             }             if (a->RAmount >= 2)                     p3 = a->key_pt[1].p;             else                     p3 = NULL;             if (a->RAmount >= 3)                     p4 = a->key_pt[2].p;             else                     p4 = NULL;             if (a->RAmount == 4)                  p5 = a->key_pt[3].p;             else                     p5 = NULL;             delete a;                  destroy (p1);         destroy (p2);         destroy (p3);         destroy (p4);         destroy (p5);         } } void B_tree::Add (int key) {         bool grow;         Page::Item u;         Page *bufer_root;         search_add_key (key, root, grow, u);         if (grow == true)         {                 bufer_root = root;                 root = new Page;                 root->p0 = NULL;                 root->key_pt[0].p = NULL;                 root->key_pt[1].p = NULL;                 root->key_pt[2].p = NULL;                 root->key_pt[3].p = NULL;                 root->RAmount = 1;                 root->p0 = bufer_root;                 root->key_pt[0] = u;         } } void B_tree::search_add_key (int key, Page *a, bool& grow, Page::Item& v) {         short i, L, R;         Page *b;         Page::Item u;                  if (a == NULL)         {                 grow = true;                 v.key = key;                 v.p = NULL;                 v.count = 1;         }         else         {                 L = 0;                 R = a->RAmount;                 while (L < R)                 {                         i = (L+R)/2;                         if (a->key_pt[i].key <= key)                                 L = i+1;                         else                                 R = i;                 }                 R = R-1;                 if ((R >= 0) && (a->key_pt[R].key == key))                         a->key_pt[R].count++;                 else                 {                         if (R == -1)                                 search_add_key (key, a->p0, grow, u);                         else                                 search_add_key (key, a->key_pt[R].p, grow, u);                         if (grow == true)                         {                                 if (a->RAmount < 4)                                 {                                         grow = false;                                         a->RAmount++;                                         for (i = a->RAmount-1; i >= R+2; i--)                                                 a->key_pt[i] = a->key_pt[i-1];                                         a->key_pt[R+1] = u;                                 }                                 else                                 {                                         b = new Page;                                         b->p0 = NULL;                                         b->key_pt[0].p = NULL;                                         b->key_pt[1].p = NULL;                                         b->key_pt[2].p = NULL;                                         b->key_pt[3].p = NULL;                                         if (R <= 1)                                         {                                                 if (R == 1)                                                         v = u;                                                 else                                                 {                                                         v = a->key_pt[1];                                                         for (i=1; i>=R+1; i--)                                                                 a->key_pt[i] = a->key_pt[i-1];                                                         a->key_pt[R+1] = u;                                                 }                                                 for (i=0; i<=1; i++)                                                         b->key_pt[i] = a->key_pt[i+2];                                         }                                         else                                         {                                                 R = R-2;                                                 v = a->key_pt[2];                                                 for (i=0; i<=R-1; i++)                                                         b->key_pt[i] = a->key_pt[i+3];                                                 b->key_pt[R] = u;                                                 for (i=R+1; i<=1; i++)                                                         b->key_pt[i] = a->key_pt[i+2];                                         }                                         a->RAmount = 2;                                         b->RAmount = 2;                                         b->p0 = v.p;                                         v.p = b;                                 }                         }                 }         } } bool B_tree::Search (int key) {         return (search_key (key, root)); } bool B_tree::search_key (int key, Page *a) {         short i, L, R;              if (a == NULL)                 return (false);         else         {                 L = 0;                 R = a->RAmount;                 while (L < R)                 {                         i = (L+R)/2;                         if (a->key_pt[i].key <= key)                                 L = i+1;                         else                                 R = i;                 }                 R = R-1;                 if ((R >= 0) && (a->key_pt[R].key == key))                         return (true);                 else                         if (R == -1)                                 search_key (key, a->p0);                         else                                 search_key (key, a->key_pt[R].p);         }                         } void B_tree::Delete (int key) {                 bool smallsize;         Page *bufer_root;         delete_key (key, root, smallsize);         if (smallsize == true)         {                 if (root->RAmount == 0)                 {                         bufer_root = root;                         root = bufer_root->p0;                         delete bufer_root;                 }         } } void B_tree::delete_key (int key, Page *a, bool& smallsize) {         short i, L, R;         Page *q;         if (a == NULL)                 smallsize = false;          else         {                 L = 0;                 R = a->RAmount;                 while (L < R)                 {                         i = (L+R)/2;                         if (a->key_pt[i].key < key)                                 L = i+1;                         else                                 R = i;                 }                 if (R == 0)                         q = a->p0;                 else                         q = a->key_pt[R-1].p;                 if ((R <= a->RAmount-1) && (a->key_pt[R].key == key))                    {                         if (q == NULL)                         {                             a->RAmount--;                             smallsize = (a->RAmount < 2);                             for (i=R; i<a->RAmount; i++)                                     a->key_pt[i] = a->key_pt[i+1];                         }                         else                         {                                 del(R, a, q, smallsize);                                 if (smallsize == true)                                         fusion (a, q, R-1, smallsize);                         }                 }                 else                 {                         delete_key (key, q, smallsize);                         if (smallsize == true)                                 fusion (a, q, R-1, smallsize);                 }         } } void B_tree::del (int R, Page *a, Page *q, bool& smallsize) {         Page *b;         b = q->key_pt[q->RAmount-1].p;         if (b != NULL)         {                 del (R, a, b, smallsize);                 if (smallsize == true)                         fusion (q, b, q->RAmount-1, smallsize);         }         else         {             q->key_pt[q->RAmount-1].p = a->key_pt[R].p;             a->key_pt[R] = q->key_pt[q->RAmount-1];             q->RAmount--;             smallsize = (q->RAmount < 2);         } } void B_tree::fusion (Page *father, Page *son, int R, bool& smallsize) {         Page *b;         int i, k, RAb, RAfather;         RAfather = father->RAmount;         if (R < RAfather-1)         {                 R++;                 b = father->key_pt[R].p;                 RAb = b->RAmount;                 k = (RAb-2+1)/2;                 son->key_pt[1] = father->key_pt[R];                 son->key_pt[1].p = b->p0;                 if (k > 0)                 {                         for (i=0; i <= k-1; i++)                                 son->key_pt[i+2] = b->key_pt[i];                         father->key_pt[R] = b->key_pt[k];                         father->key_pt[R].p = b;                         b->p0 = b->key_pt[k].p;                         RAb = RAb-k-1;                         for (i=0; i < RAb; i++)                                 b->key_pt[i] = b->key_pt[i+k+1];                         b->RAmount = RAb;                         son->RAmount = 2-1+(k+1);                         smallsize = false;                 }                 else                     {                         for (i=0; i < 2; i++)                                 son->key_pt[i+2] = b->key_pt[i];                         for (i=R; i < RAfather-1; i++)                                 father->key_pt[i] = father->key_pt[i+1];                         son->RAmount = 4;                         father->RAmount--;                         smallsize = (father->RAmount < 2);                         delete b;                 }         }         else         {                 if (R == 0)                         b = father->p0;                 else                         b = father->key_pt[R-1].p;                 RAb = b->RAmount+1;                 k = (RAb-2)/2;                 if (k > 0)                 {                         son->key_pt[k] = son->key_pt[0];                         son->key_pt[k-1] = father->key_pt[R];                         son->key_pt[k-1].p = son->p0;                         RAb = RAb-k-1;                         son->p0 = b->key_pt[RAb].p;                         father->key_pt[R] = b->key_pt[RAb];                         father->key_pt[R].p = son;                         b->RAmount--;                         son->RAmount = 2-1+k;                         smallsize = false;                 }                 else                     {                     b->key_pt[RAb-1] = father->key_pt[R];                     b->key_pt[RAb-1].p = son->p0;                     b->key_pt[RAb] = son->key_pt[0];                     b->RAmount = 4;                     father->RAmount--;                             smallsize = (father->RAmount < 2);                       delete son;                 }         } } void B_tree::Print () {         print_b_tree (root, 0);         } void B_tree::print_b_tree (Page *a, int level) {         using namespace std;         short i;         if (a != NULL)         {                 for (i=0; i<level; i++)                         cout << "---";                 for (i=0; i<a->RAmount; i++)                 {                         cout << a->key_pt[i].key; //<< "(" <<a->key_pt[i].count << ")";                         if (i != a->RAmount-1)                                 cout << ", ";                 }                 cout << endl;                 print_b_tree (a->p0, level+1);                 for (i=0; i<a->RAmount; i++)                         print_b_tree (a->key_pt[i].p, level+1);         } }

P.S. Группе 233 ИМКН ДВГУ 2006 года и последующих recpect передавайте привет Остроуховой.

Это сообщение отредактировал(а) kjohnny - 5.12.2005, 12:22

... , этот код не компилиццо, или я чего-то не догнал....

Это сообщение отредактировал(а) maxim1000 - 30.5.2007, 11:02

Форум ещё работает? Хотелось бы ещё информации, причём по Б-деревьям НЕ бинарным - т.е. сильноветвящимися. Очень надо!