Doubts on classes when implementing binary search trees

user_5922196 0
Viewed 81

I am studying generic binary search trees (BST) and AVL trees (AVL) on some notes that contain implementation pseudocodes. I am a bit puzzled about some details of their implementation.

The BST is based on the struct Node below

struct Node{
  int key;
  Node* parent;
  Node* left;
  Node* right;

  //constructors
}

//methods

The AVL version is basically the same with a few fields more for balancing the tree (I'll call it AVLNode for clarity, but there's no such distinction on the notes):

struct AVLNode{
  int key;
  int height;
  int size;
  AVLNode* parent;
  AVLNode* leftchild;
  AVLNode* rightchild;

  //constructors
}

//methods

A lot of operations are the same between the two trees and I can easily use templates in order to reuse them on both trees. However, consider the operation insert, which inserts a new node. The code for a BST is something like

//Insert node with key k in tree with root R
void insert(const int& k, Node* root){
  Node* N=find(k, root);         //finds where to insert the node
  if (N->key>k)
    N->leftchild=new Node(k,N);  //inserts as a left child
  else
    N->rightchild=new Node(k,N); //inserts as a right child
}

Now, the point is that the insert operation of an AVL tree is basically the same. The pseudocode presented in the notes is as follows:

void avlInsert(int k, AVLNode* R){
  insert(k,R);          //same operations as for Nodes, shown above
  AVLNode* N=find(x,R); //find node inserted (generic operation for BST)
  rebalance(N);         //perform balancing operations specific to AVL trees 
}

I'm a bit puzzled at this point, I know that the above is just a pseudocode but I was wondering whether there is a way to reuse the operation insert already provided for Node. Using template specialization would just mean writing a different specialization insert<AVLNode> for AVLNode, so that's not what I'm referring to.

I think a way would be to define AVLNode as a child class of Node and then use something like

struct AVLNode : Node {
  //implementation
}

void avlInsert(int k, AVLNode* R){
  Node *root=R;
  insert(k,root);
  AVLNode* N=find(x,R);
  rebalance(N);
}

but I'm not quite sure this would work and I don't know how to manage the pointers to parent and the childs (i.e. they must be pointers to Node inside Node and to AVLNode inside AVLNode).

Is there a way to avoid rewriting the same code?

binary-search-tree avl-tree templates class c++
1 Answers

You could use CRTP here. This would allow you to create the left right and parent nodes in the baseclass. For example consider something like this:

template<typename T>
struct BaseNode{
  int key;
  T* parent;
  T* left;
  T* right;
};

struct AVLNode : public BaseNode<AVLNode>{
  int height;
  int size;
  AVLNode(const int&k, AVLNode*root){};
  AVLNode(){};
};
struct Node : public BaseNode<Node>{
    Node(const int&k, Node*root){};
    Node(){};
};

template<typename T>
T* find(const int& k, T* root){return root;};

template<typename T>
void insert(const int& k, T* root){
  T* N=find(k, root);         //finds where to insert the node
  if (N->key>k)
    N->left=new T(k,N);  //inserts as a left child
  else
    N->right=new T(k,N); //inserts as a right child
}

void test(){
    AVLNode avl_root;
    Node node_root;
    insert(42, &avl_root);
    insert(42, &node_root);
}

The downside is that the compiler will generate more code than necessary. Because it creates a new insert function for every type. This might not be a problem for you, but something worth considering. See godbolt for the generated code.

As an aside. Please please please please don't use raw pointers and new and delete. You'll be going to get so many memory leaks, especially if a pointer gets "lost" because its parent gets deleted. Consider using smart pointers like unique_ptr or shared_ptr

user_48946600
Related