binary-search - ノード値が二分探索木で指定された値より大きいことを見つける方法

Question

私は赤黒の木を持っており、基本的な操作は挿入、削除、順序通りのトラバース、ポストオーダー、プリオーダーなどです。

指定した値より大きいツリー内のノードを返すことができるメソッドを作成したいと考えています。未満でも同じです。

誰でも疑似コード/アルゴリズムを教えてもらえますか(おそらく同じことを意味します)

乾杯

Answer 1

以下は、指定された値以上のノードの昇順でノードを表示するために問題なくテストする作成したコードです。誰かが私のコードを確認して改善を推奨し、可能であれば、LessThan メソッドでこれを行う方法を推奨してください。現在、私の LessThan メソッドは降順で返され、昇順で取得する方法がわかりません。乾杯。

 // --------------------------------------------------------------------------------
// GetNodesGreaterThan
// --------------------------------------------------------------------------------
/** \fn void  RedBlackTree<T>::GetNodesGreaterThan(T &data)
 *  \brief This method checks to see if tree is empty otherwise calls the 
 *          recursive the GreaterThan method.
 *  \param templated
 *  \return void
 */
template <class T>
void  RedBlackTree<T>::GetNodesGreaterThan(T &data)
{
    GreaterThan(m_root, data);
}

// --------------------------------------------------------------------------------
// GreaterThan
// --------------------------------------------------------------------------------
/** \fn void RedBlackTree<T>::GreaterThan(NodeType<T> *p, const T &data) const
 *  \brief This method finds the nodes in the tree that are greater than  or equal to 
 *          a specified value and puts nodes into a list.
 *  \param templated pointer
 *  \param constant template
 *  \return void
 */
template <class T>
void RedBlackTree<T>::GreaterThan(NodeType<T> *p, const T &data) const
{
    if ( p != NULL)                                         // we have hit a leaf node
    {
        if ((p->m_data == data) || (data < p->m_data)){     // record the node whos value is
            GreaterThan(p->m_lLink, data);                  // move down left link
            //cout << p->m_data << " ";                     // Display data (debug purpose)
        }
        GreaterThan(p->m_rLink, data);                      // move down right link 
    }
}

// --------------------------------------------------------------------------------
// GetNodesLessThan
// --------------------------------------------------------------------------------
/** \fn void  RedBlackTree<T>::GetNodesLessThan(T &data)
 *  \brief This method checks to see if tree is empty otherwise calls the 
 *          recursive the LessThan method.
 *  \param template
 *  \return void
 */
template <class T>
void  RedBlackTree<T>::GetNodesLessThan(T &data)
{
    ClearList();                                            // clears the node list
    LessThan(m_root, data);
}

// --------------------------------------------------------------------------------
// LessThan
// --------------------------------------------------------------------------------
/** \fn void RedBlackTree<T>::LessThan(NodeType<T> *p, const T &data) const
 *  \brief This method finds the nodes in the tree that are less than  or equal to 
 *          a specified value and puts nodes into a list.
*  \param templated pointer
 *  \param constant template
 */
template <class T>
void RedBlackTree<T>::LessThan(NodeType<T> *p, const T &data) const
{
    if ( p != NULL)
    {
        if ((p->m_data == data) || (data > p->m_data)){     // record the node whos value is
            LessThan(p->m_rLink, data);                     // move down left link
            //cout << p->m_data << " ";                     // Display data (debug purpose)
            //m_list[m_countOfElements] = p->m_data;            // add to list
            //m_countOfElements++;                              // increment # of elements
        }
        LessThan(p->m_lLink, data);                         // move down left link
    }
}