STL like tree
От: sadomovalex Россия http://sadomovalex.blogspot.com
Дата: 09.03.05 11:18
Оценка: 9 (3)
Добрый день
Вот дошел до необходимости сабжа. Как выяснилось
Автор: achmed
Дата: 01.03.05
, более менее удовлетворительной реализации (и без проблем с лицензией) найти не удалось. Предсталенная здесь
Автор: m.a.g.
Дата: 14.02.03
реализация также использует не совсем законные трюки
Автор: sadomovalex
Дата: 03.03.05
. Поэтому решил написать сам:


/*
Copyright by Alex Sadomov, 2005
STL like контейнер дерево. Подерживает работу с пользовательскими аллокаторами. Реализован на основе
бинарного дерева с использованием правил:
1) каждый элемент дерева содержит помимо значения (ключа) три указателя: левый ребенок, правый ребенок, родитель
2) левый ребенок считается следующим элементом в sibling-списке
3) правый ребенок считается первым элементом в списке детей данного элемента
Подерживает два вида итераторов: const_iterator (для чтения) и iterator (для чтения и записи) (а также
reverse_iterator и const_reverse_iterator), реализованных на основе двунаправленного итератора (_Bidit).
Итераторы используются для полного обхода дерева вглубь. Для итераторов определены операторы отношения порядка.
При этом первый итератор считается меньше второго, если до второго итератора можно добраться от первого
последовательным инкрементом первого итератора. Также для итераторов определено понятие уровня - функция level()
в классе const_iterator (end() имеет нулевой уровень)

Пример дерева:
_Root - 1 - 2
        |   |
       11   3 - 4
        |   |   |
       12   10  5 - 6
        |       |   |
       13 - 14  8   7
        |   |   |
       16   15  9
        |
       17
Нумерация совпадает с обходом дерева с помощью его итератора. Оно может быть составлено след. образом:

    tree<A> t;
    tree<A>::iterator it1, it2, it3;
    it1 = t.insert(t.end(), 1);

    it2 = t.insert_child(it1, 2);
    it2 = t.insert_after(it2, 3);
    t.insert_after(it2, 10);

    it2 = t.insert_child(it2, 4);
    it2 = it3 = t.insert_after(it2, 5);
    it2 = t.insert_after(it2, 8);
    it2 = t.insert_after(it2, 9);

    it3 = t.insert_child(it3, 6);
    t.insert_after(it3, 7);

    t.push_back(11);
    t.push_back(12);
    it2 = t.insert(t.end(), 13);
    t.push_back(16);
    t.push_back(17);

    it2 = t.insert_child(it2, 14);
    t.insert_after(it2, 15);

Для вывода в выходной поток можно использовать след. оператор (не является членом класса tree<>):
template <class T>
ostream &operator<<(ostream &ostr, const tree<T>& t)
{
    for (tree<T>::const_iterator it = t.begin(); it != t.end(); ++it)
        ostr << string(it.level(), ' ') << *it << endl;
    ostr << endl;
    return ostr;
}
Т.о. дерево, сконструированное выше выводится на консоль след. образом (cout << t)
 1
  2
  3
   4
   5
    6
    7
   8
   9
  10
 11
 12
 13
  14
  15
 16
 17

Описание класса:
 - explicit tree(const _A& _Al = _A()): allocator(_Al), _Root(_Buynode()), _Size(0)
   Создает пустое дерево
    
 - explicit tree(size_type _N, const T& _V = T(), const _A& _Al = _A()): allocator(_Al), _Root(_Buynode()), _Size(0)
   Создает дерево, состоящее из _N одинаковых элементов верхнего уровня

 - tree(const _Myt& _X): allocator(_X.allocator), _Root(_Buynode()), _Size(0)
   Констуктор копирования - создает новое дерево на основе параметра. Стуктура дерева сохраняется
    
 - ~tree()
   Деструктор - освобождает память, выделенную под элементы дерева

 - _Myt& operator=(const _Myt& _X)
   операвор присваивания - сначала удаляет все элементы данного дерева, затем копирует переданное дерево и его
   структуру

 - Стандартные методы доступа к итераторам (как в обычных контейнерах)
   const_iterator begin() const
   const_iterator end() const
   iterator begin()
   iterator end()
   reverse_iterator rbegin()
   reverse_iterator rend()
   const_reverse_iterator rbegin() const
   const_reverse_iterator rend() const

 - Функции работы с элементами верхнего уровня (как в stl::list)
   void push_front(const T& _X)
   void pop_front()
   void push_back(const T& _X)
   void pop_back()

 - iterator insert(iterator _P, const T& _X = T())
   Вставляет новый элемент в позицию итератора _P. При этом элемент, находящийся до этого в данной позиции
   окажется после нового элемента (в sibling-списке). Возвращает итератор нового элемента

 - iterator insert_after(iterator _P, const T& _X = T())
   Всталяет новый элемент в позицию после итератора _P. Если передан end(), не вставляется ничего (end() - всегда
   следует после последнего - после него ничего нет). Возвращает итератор нового элемента или end() в последнем
   случае

 - void insert(iterator _P, const _Myt& t)
   Вставляет в позицию итератора _P новое дерево. При этом _P будет корнем вставляемого дерева

 - iterator insert_child(iterator _P, const T& _X = T())
   Добавляет нового ребенка к итератору _P. Если у данного элемента уже есть дети, новый ребенок добавляется
   в конец списка детей этого элемента. Возвращает итератор нового элемента

 - iterator deep_erase(iterator _P)
   Удаляет (освобождает память и вызывает деструктор) элемент, на который указывает _P, всех его детей, а также
   все следующие за данным элементом в sibling-списке (и соответственно их детей). Возвращает итератор элемента,
   следующего за элементом, который до удаления находился до переданного итератора _P

 - iterator erase(iterator _P)
   Удаляет элемент _P и всех его детей. Возвращает итератор элемента, следующего за элементом, который
   до удаления находился до переданного итератора _P

 - iterator erase(iterator _F, iterator _L)
   Удаляет элементы (и их детей), начиная с итератора _F и оканчивая итератором, предшествующим _L (_L не удаляется).
   При этом переданные итераторы должны быть одного уровня
    
 - void clear()
   Удаляет все элементы дерева

 - bool has_child(iterator _X) const
   Возвращает true, если элемент, который указывает итератор _X, имеет ребенка (в смысле трех правил в самом начале).
   В противном случае false

 - iterator get_parent(iterator _X) const
   Возвращает итератор предка элемента, на который указывает итератор _X. Если передан end(), возвращается end()

 - iterator get_child(iterator _X) const
   Возвращает итератор первого элемента в списке детей элеметна, на который указывает итератор _P. Если у переданного
   итератора (элемента) нет детей, возвращается end()

 - iterator next_sibling(iterator _X) const
   Возвращает итератор элемента, следующего в sibling-списке за элементом, на который указывает итератор _P. Если
   в sibling-списке переданный итератор (элемент) последний, возвращается end()
    
 - iterator prev_sibling(iterator _X) const
   Возвращает итератор элемента, который в sibling-списке следут до элемента, на который указывает итератор _P. Если
   в sibling-списке переданный итератор (элемент) первый, возвращается end()

 - void swap(_Myt& _X)
   Меняет местами два дерева    
*/
#ifndef _TREE_H_
#define _TREE_H_

#include <iterator>

template <class T, class _A = std::allocator<T> >
class tree
{
    struct Node;
    typedef Node* Nodeptr;
    struct Node
    {
        Nodeptr left, right, parent;
        T key;
    };

public:
    typedef tree<T, _A> _Myt;
    typedef _A allocator_type;
    typedef _A::size_type size_type;
    typedef _A::difference_type difference_type;
    typedef _A::pointer _Tptr;
    typedef _A::const_pointer _Ctptr;
    typedef _A::reference reference;
    typedef _A::const_reference const_reference;
    typedef _A::value_type value_type;

        // CLASS const_iterator
    class iterator;
    class const_iterator;
    friend class const_iterator;
    class const_iterator : public std::_Bidit<T, difference_type>
    {
    public:
            const_iterator()
                    {}
            const_iterator(Nodeptr _P)
                : _Ptr(_P) {}
            const_iterator(const iterator& _X)
                : _Ptr(_X._Ptr) {}
            
            const_reference operator*() const
                {return (_Ptr->key); }
            _Ctptr operator->() const
                {return (&**this); }
            const_iterator& operator++()
                {_Inc();
                return (*this); }
            const_iterator operator++(int)
                {const_iterator _Tmp = *this;
                ++*this;
                return (_Tmp); }
            const_iterator& operator--()
                {_Dec();
                return (*this); }
            const_iterator operator--(int)
                {const_iterator _Tmp = *this;
                --*this;
                return (_Tmp); }
            bool operator==(const const_iterator& _X) const
                {return (_Ptr == _X._Ptr); }
            bool operator!=(const const_iterator& _X) const
                {return (!(*this == _X)); }
            
            bool operator<(const const_iterator& _X) const
            {
                if (_Ptr == _X._Ptr)
                {
                    return false;
                }
                else if (_Ptr->parent == 0)
                {
                    return false;
                }

                const_iterator _T(_X);
                do {
                    ++_T;
                } while (_T._Mynode() != _Ptr && _T._Mynode()->parent != 0);

                if (_T._Mynode() == _Ptr)
                {
                    return false;
                }
                else
                {
                    return true;
                }
            };
            bool operator<=(const const_iterator& _X) const
                {return (*this == _X || *this < _X); }
            bool operator>(const const_iterator& _X) const
                {return (!(*this < _X) && !(*this == _X)); }
            bool operator>=(const const_iterator& _X) const
                {return (*this == _X || *this > _X); }

            void _Inc()
            {
                if (_Ptr->parent == 0 && _Ptr->right == _Ptr)
                {
                    return;
                }

                if (_Ptr->right != 0)
                {
                    _Ptr = _Ptr->right;
                }
                else if (_Ptr->left != 0)
                {
                    _Ptr = _Ptr->left;
                }
                else
                {
                    Nodeptr _X = 0;
                    do {
                        _X = _Ptr;
                        _Ptr = _Ptr->parent;
                    } while ((_Ptr->left == 0 || _Ptr->left == _X) && _Ptr->parent != 0);
                    
                    if (_Ptr->left != 0)
                    {
                        _Ptr = _Ptr->left;
                    }
                }
            }

            void _Dec()
            {
                if (_Ptr->parent == 0 && _Ptr->right == _Ptr)
                {
                    return;
                }
                else if (_Ptr->parent == 0)
                {
                    _Ptr = _Ptr->right;
                    while (_Ptr->left != 0)
                        _Ptr = _Ptr->left;
                    return;
                }

                if (_Ptr->parent->right == 0 || _Ptr->parent->right == _Ptr)
                {
                    _Ptr = _Ptr->parent;
                }
                else
                {
                    const_iterator _T(_Ptr->parent), _X;
                    do {
                        _X = (_T++);
                    } while (_T._Mynode() != _Ptr);
                    _Ptr = _X._Mynode();
                }
            }
            
            int level() const
                {return _Reclevel(_Ptr); }
            
            Nodeptr _Mynode() const
                {return (_Ptr); }            
    protected:
            int _Reclevel(Nodeptr _X) const
            {
                int _L = 0;
                if (_X->parent != 0 && _X->parent->right == _X)
                    _L = _Reclevel(_X->parent) + 1;
                else if (_X->parent != 0)
                    _L = _Reclevel(_X->parent);
                return _L;
            }

            Nodeptr _Ptr;
    };
        // CLASS iterator
    friend class iterator;
    class iterator : public const_iterator {
    public:
            iterator()
                {}
            iterator(Nodeptr _P)
                : const_iterator(_P) {}
            reference operator*() const
                {return (_Ptr->key); }
            _Tptr operator->() const
                {return (&**this); }
            iterator& operator++()
                {_Inc();
                return (*this); }
            iterator operator++(int)
                {iterator _Tmp = *this;
                ++*this;
                return (_Tmp); }
            iterator& operator--()
                {_Dec();
                return (*this); }
            iterator operator--(int)
                {iterator _Tmp = *this;
                --*this;
                return (_Tmp); }
            bool operator==(const iterator& _X) const
                {return (_Ptr == _X._Ptr); }
            bool operator!=(const iterator& _X) const
                {return (!(*this == _X)); }
    };

    typedef std::reverse_bidirectional_iterator<iterator, value_type, reference, _Tptr, difference_type>
        reverse_iterator;
    typedef std::reverse_bidirectional_iterator<const_iterator, value_type, const_reference, _Ctptr, difference_type>
        const_reverse_iterator;

    explicit tree(const _A& _Al = _A()): allocator(_Al), _Root(_Buynode()), _Size(0)
    {
        _Root->right = _Root;
    }
    
    explicit tree(size_type _N, const T& _V = T(), const _A& _Al = _A()): allocator(_Al), _Root(_Buynode()), _Size(0)
    {
        _Root->right = _Root;
        for (size_type i = 0; i < _N; i++)
            push_back(_V);
    }

    tree(const _Myt& _X): allocator(_X.allocator), _Root(_Buynode()), _Size(0)
    {
        _Root->right = _Root;
        insert(end(), _X);
    }
    
    ~tree()
    {
        clear();
        _Freenode(_Root);
        _Root = 0, _Size = 0;
    }

    _Myt& operator=(const _Myt& _X)
    {
        clear();
        insert(end(), _X);
    }

    const_iterator begin() const
        {return (const_iterator(_Root->right)); }
    const_iterator end() const
        {return (const_iterator(_Root)); }
    iterator begin()
        {return (iterator(_Root->right)); }
    iterator end()
        {return (iterator(_Root)); }
    reverse_iterator rbegin()
        {return (reverse_iterator(end())); }
    reverse_iterator rend()
        {return (reverse_iterator(begin())); }
    const_reverse_iterator rbegin() const
        {return (const_reverse_iterator(end())); }
    const_reverse_iterator rend() const
        {return (const_reverse_iterator(begin())); }

    size_type size() const
        {return (_Size); }
    size_type max_size() const
        {return (allocator.max_size()); }
    bool empty() const
        {return (size() == 0); }
    _A get_allocator() const
        {return (allocator); }
    reference front()
        {return (*begin()); }
    const_reference front() const
        {return (*begin()); }
    reference back()
        {return (*(--end())); }
    const_reference back() const
        {return (*(--end())); }

    void push_front(const T& _X)
        {insert(begin(), _X); }
    void pop_front()
        {erase(begin()); }
    void push_back(const T& _X)
        {insert(end(), _X); }
    void pop_back()
        {erase(--end()); }

    iterator insert(iterator _P, const T& _X = T())
    {
        if (_P._Mynode() != _Root)
        {
            Nodeptr _S = _P._Mynode();
            
            Nodeptr _N = _Buynode(_S, 0, _S->parent);
            allocator.construct(&_N->key, _X);

            if (_S == _S->parent->right)
                _N->parent->right = _N;
            else if (_S == _S->parent->left)
                _N->parent->left = _N;

            _S->parent = _N;

            ++_Size;
            return iterator(_N);
        }
        else if (_P._Mynode() == _Root && _Root->right != _Root)
        {
            Nodeptr _S = _Root->right;
            while (_S->left != 0)
                _S = _S->left;
            
            Nodeptr _N = _Buynode(_S->left, 0, _S);
            allocator.construct(&_N->key, _X);
            _S->left = _N;
            if (_N->left != 0)
                _N->left->parent = _N;

            ++_Size;
            return iterator(_N);
        }
        else
        {
            Nodeptr _N = _Buynode(0, 0, _Root);
            allocator.construct(&_N->key, _X);
            _Root->right = _N;
            ++_Size;
            return iterator(_N);
        }
    }

    iterator insert_after(iterator _P, const T& _X = T())
    {
        if (_P._Mynode() != _Root)
        {
            Nodeptr _S = _P._Mynode();
            
            Nodeptr _N = _Buynode(_S->left, 0, _S);
            allocator.construct(&_N->key, _X);

            if (_S->left != 0)
                _S->left->parent = _N;
            _S->left = _N;

            ++_Size;
            return iterator(_N);
        }
        else return end();
    }

    void insert(iterator _P, const _Myt& t)
    {
        Nodeptr _S = _P._Mynode();
        if (_S->right != 0 && _S != _Root)
        {
            deep_erase(_S->right);
        }

        Nodeptr _T = _Buynode();
        _Deepcopy(_T, t.begin()._Mynode());
        _S->right = _T->right;
        if (_T->right)
            _T->right->parent = _S;
        _Freenode(_T);
    }

    iterator insert_child(iterator _P, const T& _X = T())
    {
        Nodeptr _S = _P._Mynode();
        if (_S->right == 0 || _S == _Root)
        {
            Nodeptr _N = _Buynode(0, 0, _S);
            allocator.construct(&_N->key, _X);
            _S->right = _N;
            ++_Size;
            return iterator(_N);
        }
        else
        {
            _S = _S->right;
            while (_S->left != 0)
                _S = _S->left;

            Nodeptr _N = _Buynode(0, 0, _S);
            allocator.construct(&_N->key, _X);
            _S->left = _N;
            ++_Size;
            return iterator(_N);
        }
    }

    iterator deep_erase(iterator _P)
    {
        if (_P == end())
            return _P;

        Nodeptr _S = _P._Mynode();
        --_P;        
        _Deeperase(_S);
        ++_P;
        return _P;
    }

    iterator erase(iterator _P)
    {
        if (_P == end())
            return _P;

        Nodeptr _S = _P._Mynode();
        --_P;        
        _Suberase(_S);
        ++_P;
        return _P;
    }

    iterator erase(iterator _F, iterator _L)
    {
        if (_F._Level() != _L._Level())
            return _L;

        do {
            _F = erase(_F);
        } while (_F != _L);
        return (_F);
    }
    
    void clear()
        {deep_erase(begin()); }

    bool has_child(iterator _X) const
        {return (_X->_Mynode()->right != 0); }

    iterator get_parent(iterator _X) const
    {
        Nodeptr _S = _X._Mynode();
        if (_S->parent == 0)
        {
            return _X;
        }
        else if (_S == _S->parent->right)
        {
            return iterator(_S->parent);
        }
        else
        {
            Nodeptr _P = _S->parent;
            while (_P != _P->parent->right)
            {
                _P = _P->parent;
            };
            return iterator(_P->parent);
        }
    }

    iterator get_child(iterator _X) const
    {
        if (!has_child(_X))
            return end();
        else return iterator(_X._Mynode()->right);
    }

    iterator next_sibling(iterator _X) const
        {return (_X._Mynode()->left == 0 ? end() : _X._Mynode()->left); }
    
    iterator prev_sibling(iterator _X) const
    {
        if (_X == end())
        {
            return end();
        }
        
        Nodeptr _S = _X._Mynode();
        if (_S == _S->parent->right)
            return end();
        else return _S->parent;
    }

    void swap(_Myt& _X)
    {
        if (allocator == _X.allocator)
        {
            std::swap(_Root, _X._Root);
            std::swap(_Size, _X._Size);
        }
    }
    
    friend void swap(_Myt& _X, _Myt& _Y)
        {_X.swap(_Y); }

protected:
    Nodeptr _Buynode(Nodeptr left = 0, Nodeptr right = 0, Nodeptr parent = 0)
    {
        Nodeptr _S = (Nodeptr)allocator._Charalloc(1 * sizeof (Node));
        _S->left = left;
        _S->right = right;
        _S->parent = parent;
        return (_S);
    }
    
    void _Freenode(Nodeptr _S)
    {
        allocator.deallocate(_S, 1);
    }

    void _Deeperase(Nodeptr _S)
    {
        if (_S->right == 0 && _S->left == 0)
        {
            if (_S == _S->parent->right)
                _S->parent->right = (_S->parent != _Root ? 0 : _Root);
            else if (_S == _S->parent->left)
                _S->parent->left = 0;

            allocator.destroy(&_S->key);
            _Freenode(_S);
            --_Size;
        }
        else if (_S->right != 0)
        {
            _Deeperase(_S->right);

            if (_S->left != 0)
            {
                _Deeperase(_S->left);
            }
            _Deeperase(_S);
        }
        else if (_S->left != 0)
        {
            _Deeperase(_S->left);
            _Deeperase(_S);
        }
    }

    void _Suberase(Nodeptr _S)
    {
        if (_S->right == 0 && _S->left == 0)
        {
            _Deeperase(_S);
            return;
        }
        else if (_S->right != 0)
        {
            _Deeperase(_S->right);
        }


        if (_S == _S->parent->left)
            _S->parent->left = _S->left;
        else if (_S == _S->parent->right)
        {
            if (_S->left != 0)
                _S->parent->right = _S->left;
            else
                _S->parent->right = (_S->parent != _Root ? 0 : _Root);
        }

        if (_S->left != 0)
            _S->left->parent = _S->parent;
        
        allocator.destroy(&_S->key);
        _Freenode(_S);
        --_Size;
    }

    void _Deepcopy(Nodeptr _P, Nodeptr _B, bool _Right = true)
    {
        if (_B != 0)
        {
            Nodeptr _N = _Buynode(0, 0, _P);
            allocator.construct(&_N->key, _B->key);

            if (_Right)
                _P->right = _N;
            else
                _P->left = _N;

            ++_Size;
            
            _Deepcopy(_N, _B->right);
            _Deepcopy(_N, _B->left, false);
        }
    }

    _A allocator;
    Nodeptr _Root;
    size_type _Size;
};

#endif // _TREE_H_


Тестировал на 6-й студии за неимением других компиляторов под рукой. Класс реализовал для собственных целей, но прежде всего с учетом того,
что дерево должно быть STL like. Если будут пожелания и замеченные ошибки, просьба постить в этот топик.
"Что не завершено, не сделано вовсе" Гаусс
https://lh3.googleusercontent.com/-jIXLxlvycbk/TtKm5Xxz7JI/AAAAAAAABEA/CITKwRG1hFg/w500-h200-k/mvp_horizontal.png
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.