C++11: Բինար որոնման ծառեր

Այս գրառման մեջ ես ներկայացնում եմ բինար որոնման ծառի (binary search tree, BST) դասի ծրագրավորումը C++11 լեզվով։ Բինար որոնման ծառերն առանձնանում են նրանով, ամեն մի հանգույցի պարունակած արժեքը ավելի մեծ է քան նրա ձախ ենթածառի արժեքները և ավելի փոքր է, քան նրա աջ ենթածառի արժեքները։

Քանի որ բինար ծառի ամեն մի հանգույցը կարող է ունենալ առավելագույնը երկու ենթածառ, հանգույցը ներկայացնող շաբլոնային դասը կարելի է ներկայացնել հետևյալ տեսքով.

template<typename T>
class Node {
public:
  T data;
  Node* cleft;
  Node* cright;

public:
  Node( const T& val )
    : data(val), cleft(nullptr), cright(nullptr)
  {}
};

data դաշտը նախատեսված է հանգույցի տվյալների համար, cleft դաշտը ձախ ենթածառի ցուցիչն է, cright դաշտը՝ աջ ենթածառինը։ Հարմարության համար սահմանված է նաև կոնստրուկտոր, որը տրված արժեքը վերագրում է data փոփոխականին, իսկ աջ ու ձախ ենթածառերիո ցուցիչներին վերագրում է զրոյական ցուցիչի nullptr հաստատունը։

Ծառի մոդելը նույնպես ծրագրավորված է շաբլոնային դասի տեսքով։ Որպես ինտերֆեյսային մեթոդներ նախատեսել եմ հետևյալները.

• Կոնստրուկտորներ, որոնցից մեկը ստեղծում է դատարկ ծառ, իսկ մյուսը ծառն արժեքավորում է արժեքավորող ցուցակով (initializer list) trva] արժեքներով։
• Add մեթոդը տրված արժեքն ավելացնում է ծառի մեջ՝ ըստ այն պայմանի, որ ամեն մի հանգույցի ձախ ենթածառի բոլոր արժեքները պիտի լինեն ավելի փոքր, իսկ աջ ենթածառինն՝ ավելի մեծ, քան դիտարկվող հանգույցինն է։
• Contains մեթոդը դրական պատասխան է տալիս, եթե ծառը պարունակում է տրված արժեքը։
• Remove մեթոդը ծառից հեռացնում է տրված արժեքով հանգույցը՝ պահպանելով բինար ծառի վերը նշված հատկությունը։
• Preorder, Inorder և Postorder մեթոդները անցնում են ծառի բոլոր հանգույցներով՝ կիրառելով համապատասխանաբար գագաթ-ձախ-աջ, ձախ-գագաթ-աջ և ձախ-աջ-գագաթ եղանակները։ Այս մեթոդներն արգումենտում ստանում են ֆունկցիա, որը կիրառվում է բոլոր հանգույցների data դաշտի նկատմամբ։

Բինար ծառը ներկայացված է իր արմատը ցույց տվող root ցուցիչով։ Դատարկ ծառի դեպքում այս ցուցիչն ունի nullptr արժեքը։ (Node դասը կարող է հայտարարվել նաև Tree դասի ներսում։)

template<typename T>
class Tree {
protected:
  Node<T>* root;

Կոնստրուկտորներից առաջինը արմատի ցուցիչին վերագրում է զրոյական արժեք։

public:
  Tree()
    : root(nullptr)
  {}

Երկրորդ կոնստրուկտորը արգումենտում սպասում է արժեքավորող ցուցակ և այդ ցուցակի տարրերը հերթականությամբ ավելացնում է ծառի մեջ։

  Tree( std::initializer_list<T> els )
    : Tree()
  {
    for( auto e : els )
      Add( e );
  }

Add, Contains, Remove, Preorder, Inorder, Postorder արտաքին (public) մեթոդներն իրականում թաղանթներ (wrapper) են addValue, search, traverse և removeNode ներքին (private) մեթոդների համար։

  // ծառում ավելացնում է val նոր արժեքը
  void Add( const T& val )
  { addValue( val, root ); }

  // ստուգում է val արժեքի առկայությունը ծառում
  bool Contains( const T& val )
  { return nullptr != search( val, root ); }
  
  // ծառից հեռացնում է val արժեքը
  void Remove( const T& val )
  { removeNode( val, root ); }

  // ծառի հանգույցներն անցնում է գագաթ-ձախ-աջ եղանակով և 
  // հանգույցի արժեքի նկատմամբ կիրառում է operation ֆունկցիան
  void Preorder( std::function<void(T)> operation )
  { traverse( root, T_Preorder, operation ); }
  
  // ծառի հանգույցներն անցնում է ձախ-գագաթ-աջ եղանակով և 
  void Inorder( std::function<void(T)> operation )
  { traverse( root, T_Inorder, operation ); }
  
  // ծառի հանգույցներն անցնում է ձախ-աջ-գագաթ եղանակով և 
  void Postorder( std::function<void(T)> operation )
  { traverse( root, T_Postorder, operation ); }

Վերջին երեք մեթոդներում T_Preorder, T_Inorder և T_Postorder իդենտիֆիկատորները սահմանված են հետևյալ կերպ.

protected:
  enum Order { T_Preorder, T_Inorder, T_Postorder };

Հիմա տեսնենք, թե իրականում ինչպես են կատարվում բինար ծառերին յուրահատուկ գործողությունները։ Եվ, քանի որ ծառն ինքնին ռեկուրսիվ կառուցվածք է, բոլոր գործողություններն իրականացված են ռեկուրսիվ տեսքով (չնայած ոչինչ չէր խանգարում դրանք իրականացնել առանց ռեկուրսիայի)։

Սկսեմ արժեքի ավելացման գործողությունից։ addValue մեթոդը ստանում է ավելացվող արժեքը և այն ծառի արմատի հղումը, որի մեջ պետք է ավելացնել նոր հանգույց՝ տրված արժեքով։ Դիտարկվում են երեք դեպքեր. i. եթե տրված արմատը դատարկ է, ապա ստեղծվում է նոր հանգույց և կապվում է այդ արմատին, ii. եթե տրված արժեքը փոքր է տրված արմատի արժեքից, ապա արժեքն ավելացվում է ձախ ենթածառում, iii. եթե տրված արժեքը մեծ է արմատի արժեքից, ապա այն ավելացվում է աջ ենթածառում։ Քանի որ ծառը կրկնվող արժեքներ չի կարող պարունակել, տրված արժեքի ու տրված արմատի արժեքների հավասարության դեպքը պարզապես չի դիտարկվում։

  void addValue( const T& val, Node<T>*& tree )
  {
    if( tree == nullptr )           // i
      tree = new Node<T>(val);
    else if( val < tree->data )     // ii
      addValue( val, tree->cleft );
    else if( val > tree->data )     // iii
      addValue( val, tree->cright );
  }

Հաջորդ պարզ գործողությունը ծառում տրված արժեքը պարունակող հանգույցի որոնումն է։ search մեթոդը ստանում է որոնվող արժեքը և այն արմատը, որից պետք է սկսել որոնումը և վերադարձնում է կա՛մ nullptr, եթե հանգույցի չի գտնվել, կա՛մ գտնված հանգույցի ցուցիչը։ Այս մեթոդի վերնագրի տարօրինակ գրառումը նույնպես C++11 ստանդարտի նորամությություններից է։ decltype(root) արտահայտությունն ասում է, որ մեթոդի վերադարձրած արժեքն ու նրա երկրորդ tree արգումենտը պետք է ունենան նոււյն տիպը, ինչ տիպ տրված է ծառի root արմատին։ Այս մեթոդում առանձնացված է այն դեպքը երբ տրված արմատը զրոյական է. վերդարձվում է nullptr։ i. Եթե տրված արժեքը հավասար է արմատի արժեքին, ապա արմատը ներկայացնող հանգույցը հենց որոնվող հանգույցն է։ ii. եթե val-ը փոքր է արմատի արժեքից, ապա որոնումը շարունակել ձախ ենթածառում, iii. հակառակ դեպքում որոնումը շարունակել աջ ենթածառում։

  decltype(root) search( const T& val, decltype(root) tree )
  {
    if( tree == nullptr )
      return nullptr;
    if( val == tree->data )
      return tree;
    if( val < tree->data )
      return search( val, tree->cleft );
    return search( val, tree->cright );
  }

Բնականաբար decltype(root) արտահայտության օգտագործումն ամենևին էլ պարտադիր չէր այս պարագայում։ Ես այն օգտագործել եմ միայն ցուցադրման նպատակով։ Կարելի է պարզապես բացահայտ գրել Node<T>*, որը հենց հանգույցի ցուցիչի տիպն է։

Համեմատաբար ավելի բարդ է ծառից տրված արժեքը պարունակող հանգույցը հեռացնելու գործողությունը։ Այս գործողությունը պետք է կատարել այնպես, որ բինար որոնման ծառը շարունակի պահպանել իր հատկությունները։ removeNode մեթոդը նույնպես ունի ռեկուրսիվ կառուցվածք, որտեղ նորից առանձնացված է տրված արմատի դատարկ լինելու դեպքը։ (Ավելի ճիշտ ասած, սա որոնող-հեռացնող մեթոդ է։) Այն դեպքում, երբ որոնումը կանգ է առել տրված արժեքը պարունակող հանգույցի վրա, դիտարկվում են քայլերի չորս տարբերակներ.

• Երբ հանգույցը ենթածառեր չունի՝ տերև է: Այս դեպքում ազատվում է հանգույցի զբաղեցրած հիշողությունը և նրա հասցեն զրոյացվում է։
• Երբ հանգույցն ունի միայն ձախ ենթածառ։ Այս դեպքում հանգույցը հեռացվում է և նրա հասցեին վերագրվում է ձախ ենթածառի հասցեն։
• Համանման գործողություններ են կատարվում նաև այն դեպքում, երբ հանգույցն ունի միայն աջ ենթածառ։
• Երբ առկա են հանգույցի և՛ ձախ, և՛ աջ ենթածառերը։ Այս դեպքում, որպեսզի պահպանվի բինար որոնման ծառի հատկությունները, հեռացվող հանգույցը պետք է փոխարինել կա՛մ ձախ ենթածառի ամենամեծ արժեքով, կա՛մ աջ ենթածառի ամենափոքր արժեքով։

  void removeNode( const T& val, decltype(root)& tree )
  {
    // ծառը դատարկ է
    if( tree == nullptr )
      return;
    // հեռացնել ձախ ենթածառից
    if( val < tree->data )
      removeNode( val, tree->cleft );
    // հեռացնել աջ ենթածառից
    else if( val > tree->data )
      removeNode( val, tree->cright );
    else {
      bool L(tree->cleft != nullptr);
      bool R(tree->cright != nullptr);
      if( !L && !R ) {
        // տերև է
        delete tree;
        tree = nullptr;
      }
      else if( L && !R ) {
        // միայն ձախ ենթածառն է
        auto temp(tree);
        tree = tree->cleft;
        delete temp;
      }
      else if( !L && R ) {
        // միայն աջ ենթածառն է
        auto temp(tree);
        tree = tree->cright;
        delete temp;
      }
      else /* if( L && R ) */ {
        // առկա են ձախ և աջ ենթածառերը
        auto temp(tree->cright);
        // որոնել աջ ենթածառի ամենաձախ հանգույցը
        while( temp->cleft != nullptr )
          temp = temp->cleft;
        // նրա արժեքը արտագրել "հեռացվող" հանգույցում
        tree->data = temp->data;
        // բայց հեռացնել աջ ենթածառի ամենաձախ հանգույցը
        removeNode( temp->data, tree->cright );
      }
    }
  }

Ծառի բոլոր հանգույցներով անցնելու այն երեք ստարատեգիաները, որոնք արտահայտված են Preorder, Inorder և Postorder արտաքին մեթոդներով, օգտագործում են միակ traverse ներքին մեթոդը։ Այստեղ ord արգումենտի արժեքով որոշվում է թե երբ պետք է գործողությունը կիրառել գագաթի արժեքի նկատմամբ։

  void traverse( decltype(root) tree, Order ord, std::function<void(T)> operation )
  {
    // ծառը դատարկ է
    if( tree == nullptr )
      return;
    // գագաթ-ձախ-աջ
    if( T_Preorder == ord )
      operation(tree->data);
    // անցում ձախ ենթածառով
    traverse(tree->cleft, ord, operation);
    // ձախ-գագաթ-աջ
    if( T_Inorder == ord )
      operation(tree->data);
    // անցում աջ ենթածառով
    traverse(tree->cright, ord, operation);
    // ձախ-աջ-գագաթ
    if( T_Postorder == ord )
      operation(tree->data);
  }
};

* * * Ծառը ներկայացնող դասն արդեն պատրաստ է։ Այժմ կառուցենք ստորև բերված նկարում պատկերված բինար որոնման ծառը.

Տրված արժեքներով ծառ կառուցելու համար օգտագործենք արժեքավորող ցուցակը։

Tree<int> tr { 10, 6, 20, 4, 8, 16, 22, 7, 13, 17, 15 };

Ծառի պարունակությունը preorder, inorder և postorder անցումներով արտածելու համար սահմապենք printer ֆունկցիան և այն փոխանցենք Preorder, Inorder և Postorder արտքին մեթոդներին։

auto printer = [](int e) { printf("%d ", e); };

printf(" Preorder: ");
tr.Preorder( printer );
printf("\n");
  
printf("  Inorder: ");
tr.Inorder( printer );
printf("\n");
  
printf("Postorder: ");
tr.Postorder( printer );
printf("\n");

Կատարումից հետո կստանանք.

 Preorder: 10 6 4 8 7 20 16 13 15 17 22 
  Inorder: 4 6 7 8 10 13 15 16 17 20 22 
Postorder: 4 7 8 6 15 13 17 16 22 20 10 

Եթե հեռացնենք 13 արժեքը և ծառի պարունակությունն արտածենք ձախ-գագաթ-աջ կարգով, այնուհետև հեռանցնենք 10 արժեքը ու նորից արտածենք գագաթ-ձախ-աջ կարգով.

tr.Remove(13);
printf("  Inorder: ");
tr.Inorder( printer );
printf("\n");

printf(" Preorder: ");
tr.Preorder( printer );
printf("\n");

ապա կստանանք.

  Inorder: 4 6 7 8 10 15 16 17 20 22 
 Preorder: 15 6 4 8 7 20 16 17 22 

Այժմ, ենթադրենք պահանջվում է ծառի հանգույցները հավաքել std::vector<int> օբյեկտի մեջ, օրինակ, postorder կարգով։ Սահմանենք vec վեկտորը և մի լյամբդա արտահայտությունը, որը "բռնում" (capture) vec օբյեկտը որպես հղում և նրա մեջ է ավելացնում իր արգումենտում տրված արժեքը։

std::vector<int> vec;
tr.Postorder( [&vec](int e) { vec.push_back(e); });

Իսկ, օրինակ, ծառի արժեքների թվաբանական միջինը կարելի է հաշվել հետևյալ կերպ.

int summ(0), count(0);
tr.Inorder( [&summ,&count](int e) { summ += e; ++count; });
printf( "Sum = %f\n", 1.0 * summ / count );