Simple non balancing indexed binary search tree

Question

The following code represents a simple indexed binary search tree of integers. The insert method inserts an int. The indexed lookup looks up the ith smallest element (0 indexed). I'm trying to write C++ that is idiomatic, clean, modern, and efficient in that order. Can people give me pointers?

#include <iostream>
#include <pthread.h>
#include <type_traits>
#include <vector>
#include <algorithm>
#include <random>
using std::vector;
class IndexedBST{
 public:
 IndexedBST() : root(nullptr) {}
 void insert(int val){
 auto node = new Node(val, 1);
 if(root==nullptr){
 root = node;
 }
 else{
 auto pointer = root;
 Node * prev;
 while(pointer!=nullptr){
 ++pointer->size;
 prev = pointer;
 if(val < pointer->key){
 pointer = pointer->left;
 }
 else {
 pointer = pointer->right;
 }
 }
 if(prev->key>val)
 prev->left = node;
 else
 prev->right = node;
 }
 }
 int operator[](int i) const{
 if(root==nullptr||i<0||i>=root->size)
 throw std::out_of_range("Invalid index");
 auto pointer = root;
 while(1){
 auto left{pointer->left==nullptr?0:pointer->left->size}; 
 auto right{pointer->right==nullptr?0:pointer->right->size}; 
 if(i<left)
 pointer = pointer->left;
 else if (i==left)
 return pointer->key;
 else{
 i -= left+1;
 pointer = pointer->right;
 }
 }
 }
 
 private: 
 class Node
 {
 public:
 int key;
 int size;
 Node * left;
 Node * right;
 Node(int key, int size, Node * left = nullptr, Node * right = nullptr): key(key), size(size), left(left), right(right) {}
 };
 private:
 Node * root;
};
int main(int argc, char * argv[]) {
 vector<int> input(atoi(argv[1]), 0);
 vector<int> confirm(atoi(argv[1]), 0);
 for(int i=0; i<input.size(); i++){
 input[i] = confirm[i] = i;
 }
 auto rng = std::default_random_engine {};
 std::shuffle(std::begin(input), std::end(input), rng);
 IndexedBST bst;
 for(auto e:input)
 bst.insert(e);
 for(int i=0; i<input.size(); i++){
 if(bst[i]!=confirm[i]){
 printf("%d at %d does not match %d\n", bst[i], i, confirm[i]);
 break;
 }
 }
 printf("Checked %lu elements successfully\n", confirm.size());
}
```

Answer 1

Use unique_ptr for root, left, and right

Because each node of a binary tree owns memory for left and right children nodes, and a binary tree owns memory for the root node. This completely eliminates the need of delete, also reduces the headache of copy constructor/copy assignment operator problem (which arise because you used raw pointers as member variables)

Use better formatting and indentation

For better readability

Variable naming

I think node is better name than pointer

Prefer cout over printf

printf is bug-prone. If you're concerned on performance, use ios_base::sync_with_stdio(false)

Never leave local variable uninitialized

Always initialize raw pointers as nullptr, trivial typed objects as {0}, etc

Instead of comparing pointer with nullptr, use bool expression directly

C++ is already too verbose, you don't need to add another verbosity. You can use pointer->left ? pointer->left->size : 0 instead of pointer->left==nullptr?0:pointer->left->size

This is my rudimentary binary search tree for practicing purpose, you can refer this (https://github.com/frozenca/CLRS3/blob/main/12/12.3_insertion_and_deletion.cpp)

Answer 2

• More horizontal spacing please. Give your operators some breathing space. It is very hard to read things like root==nullptr||i<0||i>=root->size. BTW, I spent more time than necessary trying to parse prev->key>val. It looks almost like key itself is a pointer. prev->key > val is much more readable.

• Don't pass size to the Node()constructor. Your program relies on an important invariant, namely that node->size is always equal to node->left->size + node->right->size + 1. So (1) the size of a new node is easily inferred from left and `right, and (2) passing it explicitly may break the invariant.

• What is the purpose of right in operator[]?

• size should be size_t, not int.