Б-деревья

 
0
 
Алгоритмы
ava
kjohnny | 18.11.2005, 07:21
Определяю структуру листа Б-дерева порядка 2 (n=2) следующим образом:


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


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

smile

M
0
Пользуйтесь кнопкой "код!"
sergej.z
Ответы (16)
ava
yaja | 18.11.2005, 19:08 #
Знаю сайт с визуализаторами http://rain.ifmo.ru/cat/view.php/vis/trees
Добавлено позднее:
Знаю сайт с визуализаторами на эту тему http://rain.ifmo.ru/cat/view.php/vis/trees
Нормально про этих пихтовых было написано в Кормэне Алгоритмы: Построение и Анализ
ava
Silver | 23.11.2005, 14:33 #
Стоит посмотреть Дейта "Введение в базы данных", помниться у него Б-деревья очень подробно описаны.
ava
eskaflone | 24.11.2005, 00:04 #
1. зачем нужен
Цитата
Page *p0; //Указатель на самого левого потомка страницы
если есть массив ,где все потомки?

2.
Цитата
int key; //Значение одного ключа страницы
это номер(индекс) узла или некая полезная нагрузка?
ava
eskaflone | 24.11.2005, 15:40 #

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том уровне дерева.

ЗЫ
сейчас допишу все остальные процедуры.
ava
kjohnny | 26.11.2005, 12:19 #
Цитата (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 - число ключей на этой странице.
ava
eskaflone | 26.11.2005, 12:50 #
по Кнуту :
Б-дерево n-го порядка имеет потомков от n/2 до n

попробую реализовать. Есть какие то конкретные вопросы ,или надо просто все полностью?
ava
kjohnny | 27.11.2005, 08:12 #
Цитата (eskaflone @ 26.11.2005, 12:50)
Есть какие то конкретные вопросы ,или надо просто все полностью?


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

Кнута не видел, но так не получится, т.к. число потомков строго зависит от числа ключей на странице, то есть если их максимально 4, то число потомков у данной страницы - 5, т.е. на первой странице-потомке будут все ключи, значения которых меньше первого ключа с отцовской страницы, на второй - которые больше 1, но меньше 2 ключа с отцовской и соответственно так далее. Вот такая вот ерунда, эти б-деревья.
ava
CosmoMan | 27.11.2005, 11:20 #
А зачем вообще эти бета деревья? Они работают крайне нестабильно. Сложнейшие алгоритмы на загрузку, на выгрузку, на здвиги. Отслеживание адресов.
Чем Б-деревья проигрывают массивам?
ava
kjohnny | 27.11.2005, 16:44 #
Цитата (CosmoMan @ 27.11.2005, 11:20)
А зачем вообще эти бета деревья? Они работают крайне нестабильно. Сложнейшие алгоритмы на загрузку, на выгрузку, на здвиги. Отслеживание адресов.

Чем Б-деревья проигрывают массивам?


На самом деле, лично мне они нужны вовсе как тренировочное задание по такому курсу, как "Теория графов", да и в практических задачах обычно используют их модификации, типа Б+ или Б++ деревья, те пошустрее будут.
ava
eskaflone | 28.11.2005, 09:42 #
посмотри это ,там бинарные Б-деревья (2 потомка) алгоритмы добавления и удаления надо просто обобщить.
ava
kjohnny | 05.12.2005, 12:01 #
Цитата (eskaflone @ 28.11.2005, 09:42)
посмотри это ,там бинарные Б-деревья (2 потомка) алгоритмы добавления и удаления надо просто обобщить


Не очень хорошая реализация, да и не совсем то, что надо.
ava
kjohnny | 05.12.2005, 12:13 #
В общем, потратив массу времени на поиски, ничего хорощего не нашел :hmmm взял в руки незабвенного Вирта и... в общем, все сделал сам smile о проделанной работе: smile реализован класс для работы с 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 ;-) передавайте привет Остроуховой.
ava
MakaBuka | 30.05.2007, 08:12 #
... , этот код не компилиццо, или я чего-то не догнал....
ava
Alexsiv1984 | 01.06.2007, 13:40 #
Форум ещё работает? Хотелось бы ещё информации, причём по Б-деревьям НЕ бинарным - т.е. сильноветвящимися. Очень надо!
ava
comp | 03.06.2007, 20:27 #
Читать Кормена, там всё описанно просто отлично!
ava
pompei | 18.10.2007, 08:01 #
Могу предложить свою реализацию б-дерева (я его правда с явавского TreeMap слямзил)
Написан на чистом Си. Хорошо отлажен под Линуксом, думаю под Виндой работать будет также.

Работать с ним просто:
Например мы хотим хранить в дереве отсортированные по ФИО структуры типа

typedef struct {
int id;
char *name;
char *familyName;
char *patronymic;
int eyesColor;
} MyElement;


Тогда мы должны создать функцию сравнения:

int fioCompare_MyElement( void *_a, void *_b, void *userData ) {
if (_a == _b) return 0;
MyElement *a = (MyElement *)_a;
MyElement *b = (MyElement *)_b;
int u = strcmp( a->familyName, b->familyName );
if (u) return u;
u = strcmp( a->name, b->name );
if (u) return u;
u = strcmp( a->patronymic, b->patronymic );
if (u) return u;
return a->id - b->id; // Пусть у нас будет уникальным только id
}


И создать дерево так:

UTIL_BTREE my_tree = util_btree_new( fioCompare_MyElement, NULL );


Удалить дерево можно так:

util_btree_free( my_tree, clearMyElement );

где clearMyElement - функция по удалению элемента MyElement, хотя можно передать NULL, если нам пофиг на память. Функция например такая:

void clearMyElement( void *_v, void *userData ) {
MyElement *e = (MyElement *)_v;
free( e->familyName );
free( e->name );
free( e->patronymic );
free( e );
}


Добавить элемент в дерево можно так:

MyElement *pup = newMyElement( 10, "Пупкин", "Вася", "Петрович", GREEN );

MyElement *exists;
if (exists = util_btree_put( my_tree, pup )) {
// обана, Пупкин то там уже есть
// exists - это тот самый старый Пупкин, который сидел в дереве.
// теперь в дереве сидит наш новый Пупкин pup
делаем чё-то со старым Пупкиным exists
}


Надо когото найти в дереве:
делаем так:


MyElement *gadya = newMyElement( 0, "Хренова", "Гадя", "Петрович", 0 );

MyElement *fnd = (MyElement *)util_btree_find( my_tree, gadya );

clearMyElement( gadya );

if (fnd == NULL) {
// обана, Гадя потерялась
} else {
// о-о-о, нашлась, ууаауу
fnd->eyesColor - вот они какие глазки-та у нашей Гади!!!!
}


А вот как можно посмотреть всех:

//You may use iterator like:

ITER_UBT iter; // This variable allocated in stack


for (iter_ubt_init( &iter, tree ); iter_ubt_ok( &iter ); iter_ubt_next( &iter )) {
void *value = iter_ubt_value( &iter );
//working with current value
}

//or like:

iter_ubt_init( &iter, tree );
while (iter_ubt_ok( &iter )) {
void *value = iter_ubt_value( &iter );
//working with current value
iter_ubt_next( &iter );
}

//NOTE!!!: when you deleted an item from tree, iterator would works wronge


В прикреплении реализация дерева с тестовым модулем
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить