2
\$\begingroup\$

I trying to see if I implemented these operations correctly and if they could be optimized in any way. The implementations are just the typical implementations found online but I adjusted them to work with pointers. I did not find pseudocode for transplant, it was only described and I am unsure if it does what it is supposed to do. The tree works correctly for my small test cases, but I have not tried it with bigger data sets and operations. I purposely made the tree non-owning but if it were owning, left and right children could be unique_ptr's and parent be a Node*. I may implement that later.

class Node {
public:
  Node(int key) : key(key) {}
  Node* parent = nullptr;
  Node* left = nullptr;
  Node* right = nullptr;
  int key;
};

class BinarySearchTree {
public:
  BinarySearchTree() = default;
  /// create tree from existing nodes
  BinarySearchTree(Node* nodes[], unsigned n);
  /// insert key into tree
  void insert(Node* node);
  /// remove node with key
  void remove(Node* node);
  /// find smallest node in subtree
  Node* minimum(Node* node) const;
  /// find largest node in subtree
  Node* maximum(Node* node) const;
  /// find successor of node
  Node* successor(Node* node) const;
  /// find predecessor of node
  Node* predecessor(Node* node) const;
  /// replace subtree at a with subtree at b
  void transplant(Node* a, Node* b);
  /// find node with key
  Node* find(int key) const;
  /// find kth smallest element
  Node* kth(unsigned k) const;
  /// write data to stream
  friend std::ostream& operator<<(std::ostream& out, const BinarySearchTree& tree);

private:
  /// helper method to initialize tree
  void build_bst(BinarySearchTree& tree, Node* nodes[], unsigned n);
  /// helper method for find
  Node* find(int key, Node* subtree) const;
  /// pointer to the root
  Node* root = nullptr;
};

void BinarySearchTree::build_bst(BinarySearchTree& tree, Node* nodes[], unsigned n) {
  if (n == 0) return;
  tree.insert(nodes[n/2]);
  build_bst(tree, nodes, n/2);
  build_bst(tree, nodes + n/2 + 1, n - 1 - n/2);
}

BinarySearchTree::BinarySearchTree(Node* nodes[], unsigned n) {
  build_bst(*this, nodes, n);
}

void BinarySearchTree::insert(Node* node) {
  Node* parent = nullptr;
  Node* child = root;

  while (child) {
    parent = child;
    if (node->key < child->key)
      child = child->left;
    else
      child = child->right;
  }

  node->parent = parent;
  if (!parent) {
    root = node;
  } else if (node->key < parent->key) {
    parent->left = node;
  } else {
    parent->right = node;
  }
}

void BinarySearchTree::remove(Node* node) {
  if (!node->left && !node->right) {
    // special case where only node is root
    if (node->parent) {
    // remove leaf node      
      if (node->parent->key < node->key) {
        node->parent->right = nullptr;
      } else {
        node->parent->left = nullptr;
      }
    } else {
      root = nullptr;
    }
    node->parent = nullptr;
  } else if (!node->left && node->right) {
    // no left child
    transplant(node, node->right);
  } else if (node->left && !node->right) {
    // no right child
    transplant(node, node->left);
  } else {
    // check if min = successor(node)
    Node* min = successor(node);
    if (min->parent != node) {
      transplant(min, min->right);
      min->right = node->right;
      min->right->parent = min;
    }
    transplant(node, min);
    min->left = node->left;
    min->left->parent = min;
  }
}

Node* BinarySearchTree::minimum(Node* node) const {
  Node* parent = nullptr;
  Node* child = node;

  while (child) {
    parent = child;
    child = child->left;
  }

  return parent;
}

Node* BinarySearchTree::maximum(Node* node) const {
  Node* parent = nullptr;
  Node* child = node;

  while (child) {
    parent = child;
    child = child->right;
  }

  return parent;
}

Node* BinarySearchTree::successor(Node* node) const {
  if (node->right) {
    // find minimum of right subtree
    return minimum(node->right);
  } else {
    // find parent of furthest node through right branches
    Node* iter = node;
    while (iter->parent) {
      if (iter->parent->key < iter->key) {
        iter = iter->parent;
      } else {
        break;
      }
    }

    // will return nullptr if no successor
    return iter->parent;
  }
}

Node* BinarySearchTree::predecessor(Node* node) const {
  if (node->left) {
    return maximum(node->left);
  } else {
    // find parent of furthest node through left branches
    Node* iter = node;
    while (iter->parent) {
      if (iter->key < iter->parent->key) {
        iter = iter->parent;
      } else {
        break;
      }
    }

    // will return nullptr if no predecessor exists
    return iter->parent;
  }
}

void BinarySearchTree::transplant(Node* a, Node* b) {
  if (b->parent->key < b->key) {
    b->parent->right = nullptr;
  } else {
    b->parent->left = nullptr;
  }

  b->parent = a->parent;

  // special case when a is root
  if (a->parent) {
    if (a->parent->key < a->key) {
      a->parent->right = b;
    } else {
      a->parent->left = b;
    }
  } else {
    root = b;
  }
}

Node* BinarySearchTree::find(int key) const {
  return find(key, root);
}

Node* BinarySearchTree::find(int key, Node* subtree) const {
  if (!subtree) return nullptr;
  if (subtree->key < key)
    return find(key, subtree->right);
  else if (subtree->key > key)
    return find(key, subtree->left);
  else
    return subtree;
}

Node* BinarySearchTree::kth(unsigned k) const {
  Node* kth = minimum(root);
  for (unsigned i = 0; i < k-1; ++i) {
    if (kth)
      kth = successor(kth);
    else
      return kth;
  }

  // returns nullptr if kth element does not exist
  return kth;
}

/// in-order traversal/print
std::ostream& operator<<(std::ostream& out, const Node& node) {
  if (node.left)
    out << *node.left;
  out << node.key << ' ';
  if (node.right)
    out << *node.right;
  return out;
}

/// print the entire tree
std::ostream& operator<<(std::ostream& out, const BinarySearchTree& tree) {
  if (!tree.root) return out;
  return out << *tree.root;
}
\$\endgroup\$
2
\$\begingroup\$

Good stuff

  • Consistent indentation
  • /// documenting comments (I applaud to that)
  • What it does first, how it does it last
    (although I personally prefer inline bodies, this is nice example of the separation being done right)

Design

What could be the reason to have the nodes exposed and not owned?
The tree should, in my opinion, accept and expose only values and be a template:

template<class T>
class BinarySearchTree {
    struct Node {
        std::unique_ptr<Node> left = nullptr;
        std::unique_ptr<Node> right = nullptr;
        T key;
        Node(T key) : key(std::move(key)) {}
    };
public:
    BinarySearchTree(std::initializer_list<T> init);

You should notice that:

  1. It uses std::unique_ptr because there is simply no excuse now! If you, for whatever reason, need something like Node* then it should rather be iterator or node handle (C++17).
  2. It has constructor accepting std::initializer_list to enable construction like BinarySearchTree<int>{1,2,3}
  3. No parent inside node. I will elaborate this a bit more:

I can understand why you did this, because I have done it during my first exam and it was not received well by the teacher. You can use stacks tracking the path from root to current node (maybe make it part of the iterator if needed) to implement every exposed operation. I know it is easier to have the parent in the node, but it should not be there.

Balancing the tree

You have provided constructor (BinarySearchTree(Node* nodes[], unsigned n) using build_bst(BinarySearchTree& tree, Node* nodes[], unsigned n)) that will produce well-balanced tree if the input array is sorted (should probably check and sort if needed), but did not make the tree read-only, which means, that you should provide some means of rebalancing the tree. Try reading about Red-Black Tree (and maybe AVL Tree as alternative).


Personal story: The purpose of the exam was to show understanding of pointers to handle joining two trees or heaps. The teacher could not imagine that somebody would even think about optimal solution... ehm, I did, and received some unwanted attention for the rest of my studies for doing so while helping myself using that parent pointer instead of three stacks - there was simply not enough time to pull this out... and I was not supposed to even think about such solution, you know :D I hope you now understand that I am not stressing the removal of parent too much :)

\$\endgroup\$
6
  • \$\begingroup\$ Thanks for the response. This was for my data structures class and we were expected to have the parent pointer. I have modified this code further and I could try implementing without the parent pointer \$\endgroup\$ – Brady Dean Sep 28 '18 at 19:43
  • \$\begingroup\$ If the only purpose of the review was to check the code before you submit it to the teacher, then, well, it looks good for the level I am assuming you are at. You can test insert and remove a bit more, to be sure, but I did not spot any obvious flaw in the implementation. \$\endgroup\$ – user52292 Sep 28 '18 at 20:12
  • \$\begingroup\$ In your personal story, the parent pointer implementation was the optimal solution or wasn’t? I can see how it saves memory. I’m also implementing an avl right now \$\endgroup\$ – Brady Dean Sep 28 '18 at 21:04
  • \$\begingroup\$ @BradyDean: The parent pointer did not change the speed, stack would produce same Big-O (some logarithm in it probably). I have used the pointer to even be able to write it ON PAPER IN TIME. The teacher expected something less-optimal (maybe quadratic complexity) but much easier to write (just tear the nodes from one tree/heap one at a time and put them in the bigger one). I was the only one to even try something smarter/faster. But adding that pointer to the node to make it easier to implement just made the teacher, ehm, mad at me. \$\endgroup\$ – user52292 Sep 28 '18 at 21:11
  • \$\begingroup\$ Our professor haven’t even mentioned implementations without the parent pointer and hasn’t talked about using a stack when iterating through. I like the idea tho \$\endgroup\$ – Brady Dean Sep 28 '18 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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