3
\$\begingroup\$

This is one more implementation of Binary Search Tree in C++. There are many such implementations, however they are typically long and complex, and also many of them rely on pointers to parent nodes for deletion (which isn't necessary). My goals were simplicity, clarity and conciseness, especially for the erase function. Performance wasn't my first priority, so you can see a number of places in this code, where the performance might be slightly improved.

#include <cstdlib>
#include <ctime>

#include <iostream>
#include <string>
#include <utility>

using std::cout;
using std::endl;

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////// Node //
////////////////////////////////////////////////////////////////////////////////

struct Node
{

  Node() = delete;
  Node(std::string const& K): _lPtr(nullptr), _rPtr(nullptr), _key(K) {}

  friend std::ostream& operator<<(std::ostream&, const Node* const);
  friend std::pair<Node**, bool> Find(std::string const&, Node** const);
  friend void Erase(Node** const);
  friend void Clear(const Node* const);

private:

  friend Node** FindMin(Node** const);
  friend Node** FindMax(Node** const);

  Node* _lPtr;
  Node* _rPtr;
  std::string _key;

};

std::ostream& operator<<(std::ostream& S, const Node* const N)
// ------ in the subtree with the root N:
// ------ recursively traverse this subtree with inorder keys output
{
  if (N != nullptr) S << '(' << N->_lPtr << N->_key << N->_rPtr << ')';
  return S;
}

std::pair<Node**, bool> Find(std::string const& K, Node** const P)
// ------ in the subtree with the root *P:
// ------ if the node with the key K exists, return pointer to pointer to it and the flag 'true',
// ------ otherwise return pointer to pointer, where the new node should be linked, and the flag 'false'
{
  const auto nodePtr = *P;
  if (nodePtr != nullptr)
  {
    if (K < nodePtr->_key)
    {
      // ------ search in the left subtree
      return Find(K, &nodePtr->_lPtr);
    }
    else if (K > nodePtr->_key)
    {
      // ------ search in the right subtree
      return Find(K, &nodePtr->_rPtr);
    }
    else
    {
      // ------ the node is found: return pointer to it
      return std::make_pair(P, true);
    }
  }
  else
  {
    // ------ the node isn't found
    return std::make_pair(P, false);
  }
}

void Erase(Node** const P)
// ------ in the subtree with the root *P:
// ------ recursively erase its root
{
  const auto nodePtr = *P;
  if (nodePtr->_lPtr != nullptr && nodePtr->_rPtr != nullptr)
  {
    // ------ the node has two children: find the closest node, copy its key and erase it
    // ------ closest left or right nodes are chosen randomly for symmetry
    const auto closestPtr = (std::rand() % 2 == 0) ? FindMax(&nodePtr->_lPtr) : FindMin(&nodePtr->_rPtr);
    nodePtr->_key = (*closestPtr)->_key;
    Erase(closestPtr);
  }
  else if (nodePtr->_lPtr != nullptr)
  {
    // ------ the node has only the left child
    *P = nodePtr->_lPtr;
    delete nodePtr;
  }
  else if (nodePtr->_rPtr != nullptr)
  {
    // ------ the node has only the right child
    *P = nodePtr->_rPtr;
    delete nodePtr;
  }
  else
  {
    // ------ the node doesn't have children
    *P = nullptr;
    delete nodePtr;
  }
}

void Clear(const Node* const N)
// ------ in the subtree with the root N:
// ------ recursively erase all this subtree
{
  if (N != nullptr)
  {
    Clear(N->_lPtr);
    Clear(N->_rPtr);
    delete N;
  }
}

Node** FindMin(Node** const P)
// ------ in the subtree with the root *P:
// ------ return pointer to pointer to the node with a minimal key
{
  const auto nodePtr = *P;
  return (nodePtr->_lPtr != nullptr) ? FindMin(&nodePtr->_lPtr) : P;
}

Node** FindMax(Node** const P)
// ------ in the subtree with the root *P:
// ------ return pointer to pointer to the node with a maximal key
{
  const auto nodePtr = *P;
  return (nodePtr->_rPtr != nullptr) ? FindMax(&nodePtr->_rPtr) : P;
}

////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////// BST //
////////////////////////////////////////////////////////////////////////////////

struct BST
{

  BST(): _rootPtr(nullptr) {std::srand(std::time(nullptr));}
  virtual ~BST() {this->clear();}

  friend std::ostream& operator<<(std::ostream&, BST const&);

  bool contains(std::string const&) const noexcept;
  void insert(std::string const&);
  void erase(std::string const&) noexcept;
  void clear() noexcept;

private:

  Node* _rootPtr;

};

std::ostream& operator<<(std::ostream& S, BST const& T)
{
  S << T._rootPtr;
  return S;
}

bool BST::contains(std::string const& K) const noexcept
{
  return Find(K, const_cast<Node**>(&_rootPtr)).second;
}

void BST::insert(std::string const& K)
{
  const auto res = Find(K, &_rootPtr);
  if (not res.second) *res.first = new Node(K);
}

void BST::erase(std::string const& K) noexcept
{
  const auto res = Find(K, &_rootPtr);
  if (res.second) Erase(res.first);
}

void BST::clear() noexcept
{
  Clear(_rootPtr);
  _rootPtr = nullptr;
}

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////// main //
////////////////////////////////////////////////////////////////////////////////

int main()
{
  BST t;
  t.insert("50");
  t.insert("60");
  t.insert("40");
  t.insert("45");
  t.insert("43");
  t.insert("30");
  t.insert("35");
  // ---------------------------- traverse original tree
  cout << t << endl;
  // ------------------------------------------------ erase
  t.erase("50");
  // ------------------------ traverse after erasure
  cout << t << endl;
}

Also I tried to use more references in function arguments to get rid of * and & operators, but I didn't succeed. May be, this is example of a problem, where references aren't flexible enough comparing to pointers - what do you think?

Please see a more complete implementation of the BST (templates, copy and move constructors and assignments) here.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Move struct Node inside struct BST

A Node is just an implementation detail of a BST. Also, consider the scenario where you need multiple data types, like linked lists, hash maps and so on, you can't name everything Node. Moving Node into BST solves the problem neatly:

struct BST
{
    struct Node {
        ...
    };
    ...
};

Make operations on the tree private members functions.

You have a lot of global functions that are just helper functions for the BST. Make them private member functions of BST or Node. This will avoid polluting the global namespace.

Use smart pointers to avoid manual memory management

Use std::unique_ptr for the child pointers in Node, and for the pointer to the root node in BST. This avoids you having to call new and delete manually. For example:

struct Node
{
    ...
private:
    std::unique_ptr<Node> _lPtr;
    std::unique_ptr<Node> _rPtr;
    ...
};

When inserting a node, use std::make_unique instead of new:

void BST::insert(std::string const& K)
{
  const auto res = Find(K, &_rootPtr);
  if (not res.second)
      *res.first = std::make_unique<Node>(K);
}

Note that this also requires you to update other functions that would return a Node ** to return a std::unique_ptr<Node> *. But now deleting a subtree is very simple. You don't need to call Clear() anymore; assuming _rootPtr is also a std::unique_ptr<Node>, you can just write:

void BST::clear() noexcept
{
  _rootPtr.reset();
}

This will automatically delete the root node, and since class members are automatically destructed, _leftPtr and _rightPtr will also clean themselves up, which in turn will recurse to their children until everything has been deleted. You don't need to explicitly call clear() in the destructor of BST either.

Prefer '\n' over std::endl

Use '\n' instead of std::endl; the latter is equivalent to the former but also forces the output to be flushed, which is usually not necessary and can impact performance.

References vs. pointers

You should be able to use references for function arguments, however references should always point to a valid object, you can't have a nullptr reference. This is a problem for the way you wrote some of the functions; for example naively trying to modify your operator<<() would look like:

std::ostream& operator<<(std::ostream& S, const Node& N)
{
  if (&N != nullptr) S << '(' << *(N._lPtr) << N._key << *(N._rPtr) << ')';
  return S;
}

However, since the C++ standard says that references must always point to valid objects, most compilers will eliminate the check for &N != nullptr. So instead you would have to rewrite it like so:

std::ostream& operator<<(std::ostream& S, const Node& N)
{
  S << '(';
  if (N._lPtr) S << *(N._lPtr);
  S << N._key;
  if (N._rPtr) S << *(N._rPtr);
  S << ')';
  return S;
}

Yes, that's more tedious, but that's the way you would have to do it if you want to use references. The same goes for other functions that currently take a pointer to a Node that might be nullptr.

Consider using Doxygen to document your code

I see you tried to document some of your functions with comments, which is great. Consider using the Doxygen standard to document your code; this allows the Doxygen tools to check that you documented everything, and can create nicely formatted PDF, HTML and other format documents from your code.

Drawback of lack of parent pointers

There is a drawback of not having parent pointers, which you will encounter if you would want to implement iterators for your binary search tree. With parent pointers, iterators only have to store the pointer to the node they are currently at; using the parent pointer and comparing whether they are at the left or right child of the parent they can correctly iterate to the next node. Without parent pointers you need to store a stack of parent pointers inside your iterator.

\$\endgroup\$
4
  • \$\begingroup\$ Thank you for your kind suggestions. I won't touch my question, however I'll try to implement them in my GitHub repository. \$\endgroup\$
    – HEKTO
    Sep 12, 2021 at 18:40
  • 1
    \$\begingroup\$ Note that using unique_ptr would give a recursive delete issue, causing excessive stack depth. OTOH, being a tree (rather than a single list) you might have that anyway as-written. \$\endgroup\$
    – JDługosz
    Sep 13, 2021 at 14:10
  • \$\begingroup\$ @JDługosz That's true, although it's not worse than OP's Clear() in that regard. I'm not sure how to address this issue efficiently in a tree without parent pointers, as again, iterating over it would require a stack as well, and unlike a linked list where you have only one child pointer, you can't use the trick where you move the child's child pointer into your own child pointer in a loop. \$\endgroup\$
    – G. Sliepen
    Sep 13, 2021 at 14:13
  • \$\begingroup\$ @G.Sliepen IIRC, the normal way is to maintain an "end" pointer and move the Right link to the end, sliding the end pointer down all the way to the left. Do that while deleting and advancing to the left in a non-recursive loop. Back in the old days, running out of stack space was a more serious issue. \$\endgroup\$
    – JDługosz
    Sep 13, 2021 at 14:28
1
\$\begingroup\$

You can use inline initializers for class data members, and simplify the constructors.

    ⋮
  Node* _lPtr = nullptr;
  Node* _rPtr = nullptr;
    ⋮
public:
  explicit Node(std::string const& K) : _key{K} {}

Oh, and being a one-argument constructor, it should probably be explicit.

The parameter, being a string by reference, is OK and normal. But it could be better: For strings in particular, prefer using string_view (as a value) instead for more flexibility and efficiency when calling with lexical string literals. But, being a constructor that will create a string value for its member, you can use the sink idiom instead:

  explicit Node(std::string K/*sink*/) : _key{std::move(K)} {}

This will save another copy operation when a string had to be created in order to call the constructor.

pointers or references

In this case, you are dealing with pointers most explicitly, so using pointers is probably clearest. That way you don't get confused as to whether one or two dereferences are happening.

testing pointers

Don't write explicit tests against nullptr. Unlike in some other languages, nullptr is false and other pointer values are true. Just write if(p) or if(!p) when testing a pointer.

(Historical note: this was an efficiency issue with smart pointers prior to C++11, and is established culture and idiom. It is less cognitive overhead and thus easier to read.)

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for curly braces {K} as well! The argument type will be not only the std::string. \$\endgroup\$
    – HEKTO
    Sep 14, 2021 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.