Как добавить с помощью функции Add(int) элемент в дерево, чтобы оно было сбалансированным? Сначала делал с помощью флажка f — поочередно налево, потом направо добавлялось. Но потом понял что при кол-ве элементов большим 7 неправильно работает.

class Element {
public:
int data;
Element* left;
Element* right;
Element();
Element(int);
};

void Tree::Add(int a) {
  if(root == NULL) {
   root = new Element(a);
      return;
  }
  AddElement(root, a);
}
void Tree::AddElement(Element* p, int a) {
if (p->left == NULL) {
 p->left = new Element(a);
 return;
}
if (p->right == NULL) {
 p->right = new Element(a);
 return;
}
if (f) {
 f=0;
 AddElement(p->right, a);
} else {
 f=1;
 AddElement(p->left, a);
}
}

Здравствуйте, Ravshan, Вы писали:

R>Как добавить с помощью функции Add(int) элемент в дерево, чтобы оно было сбалансированным? Сначала делал с помощью флажка f — поочередно налево, потом направо добавлялось. Но потом понял что при кол-ве элементов большим 7 неправильно работает.

Ну там всё не так просто, вернее всё просто не так.
Есть много способов строить сбалансированное дерево.
Один из них — АVL tree. Посмотреть как оно балансируется можно тут

Здравствуйте, Risk Server, Вы писали:

RS>Здравствуйте, Ravshan, Вы писали:

R>>Как добавить с помощью функции Add(int) элемент в дерево, чтобы оно было сбалансированным? Сначала делал с помощью флажка f — поочередно налево, потом направо добавлялось. Но потом понял что при кол-ве элементов большим 7 неправильно работает.

RS>Ну там всё не так просто, вернее всё просто не так.
RS>Есть много способов строить сбалансированное дерево.
RS>Один из них — АVL tree. Посмотреть как оно балансируется можно тут

Дело в том, что у него не поисковое дерево.

Здравствуйте, <Аноним>, Вы писали:

RS>>Ну там всё не так просто, вернее всё просто не так.
RS>>Есть много способов строить сбалансированное дерево.
RS>>Один из них — АVL tree. Посмотреть как оно балансируется можно тут

А>Дело в том, что у него не поисковое дерево.

Очень даже поисковое! Смотри внимательно.

Здравствуйте, konsoletyper, Вы писали:

K>Здравствуйте, <Аноним>, Вы писали:

RS>>>Ну там всё не так просто, вернее всё просто не так.
RS>>>Есть много способов строить сбалансированное дерево.
RS>>>Один из них — АVL tree. Посмотреть как оно балансируется можно тут

А>>Дело в том, что у него не поисковое дерево.

K>Очень даже поисковое! Смотри внимательно.

А можно все-таки пояснить, что в том дереве поискового?

Здравствуйте, _DAle_, Вы писали:

_DA>А можно все-таки пояснить, что в том дереве поискового?

Да, кажется я ошибся, посыпаю голову пеплом . Поглядел невниметельно . Только вот вопрос: а нафига вообще нужно такое дерево? Каким критериям оно должно удовлетворять? Если никаких ограничений не накладыватеся, то алгоритм добавления такой, чтобы дерево сохраняло сбалансированность, тривиален.

Здравствуйте, Ravshan, Вы писали:

R>Как добавить с помощью функции Add(int) элемент в дерево, чтобы оно было сбалансированным? Сначала делал с помощью флажка f — поочередно налево, потом направо добавлялось. Но потом понял что при кол-ве элементов большим 7 неправильно работает.

Представь себе двоичную кучу — дерево, отображённое на линейный массив послойно.
Т.е.
a1 — корень
a2,a3 — дети корня
a4...a8 — дети a2 и a3
и т.д.
(здесь удобна нумерация с единицы).

Даже в наивном исполнении, когда a_k -> a_2k,a_(2k+1), дисбаланс по высоте не превосходит 1.

Хотя по количеству — увы, может достигать 2^(h-1), где h — высота. Это в абсолютных значениях, а в относительных — всего лишь примерно 4:3.

Попробуем устранить и эту несправедливость.
Пусть полностью уравновешенное дерево имеет высоту h, и соответственно, (2^h)-1 элементов.
Начнём заполнять новый слой.
0-й (начинаем новый отсчёт с нуля, для удобства) — налево,
1-й направо
2-й налево
3-й направо

Казалось бы!
Но ведь баланс дерева означает и баланс поддеревьев. Поэтому уточним
0-й налево налево
1-й налево направо
2-й направо налево
3-й направо направо

Ага! На каждом шаге решение зависит от очередного бита, начиная с младшего!

Теперь можем забыть про массив, тем более, что в таком виде последний слой оказывается разреженным. Возвращаемся к дереву.

struct Node;
typedef Node* NodePtr; // или умный указатель - дело хозяйское

struct Node
{
    NodePtr left, right;
    Data data;
};

struct Tree
{
    NodePtr root;
    int size;

    void add(NodePtr newnode)
    {
        ++size;
        add_impl(root, size, newnode);
    }
    
    void add_impl(NodePtr& node, int index, NodePtr newnode)
    {
        if(!node)
        {
            assert(index == 1); // 0 - для самого первого узла, 1 - для всех остальных
            node = newnode;
        }
        else
            add_impl((index%2)==0 ? node->left : node->right, (index/2), newnode);
    }
    
    // можно концевую рекурсию заменить итерациями
    void add(NodePtr newnode)
    {
        NodePtr* pnode = &root;
        int index = ++size;
        while(index != 1)
        {
            pnode = &((index%2)==0 ? (*pnode)->left : (*pnode)->right);
            index /= 2;
        }
        *pnode = newnode;
    }
};

Вот, если ничего в мелочах не напутал, то должно работать.

Спасибо огроменное!