// Двусторонний итератор для чтения вершин в симметричном порядке.
    class ConstIterator {
      typedef TNode Node;
      friend class Treap<Node>;
      public:
        typedef ::std::bidirectional_iterator_tag iterator_category;
        typedef ptrdiff_t difference_type;
        typedef Node value_type;
        typedef const Node& reference;
        typedef const Node* pointer;

        // Не использовать, только для объявления переменных и для STL!
        ConstIterator()
          : node_(NULL),
            first_node_(NULL),
            last_node_(NULL) {}

        ConstIterator(const ConstIterator& rhv)
          : node_(rhv.node_),
            first_node_(rhv.first_node_),
            last_node_(rhv.last_node_) {
            FAST_CHECK(!node_ || (first_node_ && last_node_));
        }

        ConstIterator& operator=(const ConstIterator& rhv) {
            ConstIterator(rhv).swap(*this);
            return *this;
        }

        void swap(ConstIterator& rhv) {
            ::std::swap(this->node_, rhv.node_);
            ::std::swap(this->first_node_, rhv.first_node_);
            ::std::swap(this->last_node_, rhv.last_node_);
        }

        bool operator==(const ConstIterator& rhv) const {
            if ( last_node_ && rhv.last_node_ ) {
                // Сравнение итераторов разных деревьев.
                FAST_CHECK(first_node_ == rhv.first_node_ &&
                           last_node_ == rhv.last_node_);
            }

            // Отдельная проверка на is_end_ нужна для сравнения с end().
            if ( this->at_end() && rhv.at_end() ) {
                return true;
            }

            if ( this->node_ == rhv.node_ ) {
                // Если вылетает этот CHECK, значит, итераторы по меньшей мере
                // инвалидированы, так как указывают на одну вершину двух
                // разных деревьев.
                FAST_CHECK(this->first_node_ == rhv.first_node_ &&
                       this->last_node_ == rhv.last_node_);
                return true;
            }

            return false;
        }
        bool operator!=(const ConstIterator& rhv) const {
            return !( *this == rhv );
        }

        // @pre !at_end().
        ConstIterator& operator++() {
            FAST_CHECK(!at_end());
            if ( node_->right_child() ) {
                node_ = node_->right_child();
                GoDownByLeftChildrenToTheNodeWithNoLeftChild();

            } else {
                GoUpToParentForWhichCurrentNodeIsLeftChild();
            }
            return *this;
        }
        // @pre !at_end().
        ConstIterator operator++(int) {
            ConstIterator tmp(*this);
            ++(*this);
            return tmp;
        }

        // @pre at_begin().
        ConstIterator& operator--() {
            FAST_CHECK(!at_begin());

            // Итератор указывал за последний элемент, а теперь на него.
            if ( at_end() ) {
                // Это должно быть непустое дерево.
                FAST_CHECK(last_node_ != NULL && first_node_ != NULL);
                node_ = last_node_;
                return *this;
            }

            if ( node_->left_child() ) {
                node_ = node_->left_child();
                GoDownByRightChildrenToTheNodeWithNoRightChild();

            } else {
                GoUpToParentForWhichCurrentNodeIsRightChild();
            }
            return *this;
        }
        // @pre !at_begin().
        ConstIterator operator--(int) {
            ConstIterator tmp(*this);
            --(*this);
            return tmp;
        }

        // @pre !at_end().
        reference operator*() const {
            FAST_CHECK(!at_end());
            return *node_;
        }
        // @pre !at_end().
        pointer operator->() const {
            FAST_CHECK(!at_end());
            return node_;
        }

        bool at_begin() const {
            return node_ != NULL && node_ == first_node_;
        }
        bool at_end() const {
            return node_ == NULL;
        }

        const Node* node() const {
            return node_;
        }

      private:
        // node — текущий элемент. Может быть NULL, тогда это end-итератор.
        // first_node — указатель на первый элемент (наименьший).
        // last_node — указатель на последний элемент (наибольший).
        // Если first_node == NULL && last_node == NULL — дерево пустое.
        // Асимптотическая сложность: O(1).
        // Дополнительная память: O(1).
        ConstIterator(const Node* node,
                      const Node* first_node, const Node* last_node)
          : node_(node),
            first_node_(first_node),
            last_node_(last_node) {
            if ( node_ ) {
                FAST_CHECK(first_node_ && last_node_);
            } else {
                FAST_CHECK(at_end() && !at_begin());
                FAST_CHECK(!!first_node_ == !!last_node_);  // оба NULL или нет.
            }
        }


        void GoDownByLeftChildrenToTheNodeWithNoLeftChild() {
            while ( node_->left_child() ) {
                node_ = node_->left_child();
            }
        }
        void GoDownByRightChildrenToTheNodeWithNoRightChild() {
            while ( node_->right_child() ) {
                node_ = node_->right_child();
            }
        }

        void GoUpToParentForWhichCurrentNodeIsLeftChild() {
            while ( node_->parent() && node_->parent()->right_child()==node_ ) {
                node_ = node_->parent();
            }

            // Или parent == NULL — прошли самую последнюю вершину, конец.
            // Или parent != NULL — следующий узел.
            if ( node_->parent() ) {
                node_ = node_->parent();

            } else {
                GoDownByRightChildrenToTheNodeWithNoRightChild();
                FAST_CHECK(node_ == last_node_);
                node_ = NULL;
                FAST_CHECK(at_end());
            }
        }

        void GoUpToParentForWhichCurrentNodeIsRightChild() {
            while ( node_->parent() && node_->parent()->left_child()==node_ ) {
                node_ = node_->parent();
            }

            if ( node_->parent() ) {
                node_ = node_->parent();

            } else {
                // Вообще такого случая быть не должно, так как в operator--
                // стоит предусловие !at_begin().
                volatile bool f = false;
                (void)f;
                FAST_CHECK(f);
            }
        }

        const Node* node_;
        const Node* first_node_;
        const Node* last_node_;
    };