How can I delete the k-th smallest element in balanced bst

Question

I have to delete the k-th smallest element in a balanced bst. The code works in most cases, but when i try to delete the root it breaks connections between nodes and it prints a partially remaining bbst. When i try to delete an interior node or a leaf node it works.

This is the code:

#include <iostream>
using namespace std;


struct arbore_binar {
    int key;
    struct arbore_binar* left;
    struct arbore_binar* right;
    int size = 0;
};

arbore_binar* nod_arbore(int key) {
    arbore_binar* node = (arbore_binar*)malloc(sizeof(arbore_binar));
    node->key = key;
    node->left = NULL;
    node->right = NULL;

    return node;
}

struct arbore_binar* Build_Tree(int a[], int i, int j, int size) {

    if (i > j)
    {
        
        return NULL;
        size = 0;
    }
    int m = (i + j) / 2;

    arbore_binar* rad = nod_arbore(a[m]);

    rad->left = Build_Tree(a, i, m - 1, size+1);
    rad->right = Build_Tree(a, m + 1, j, size+1);


        if ((rad->right) && (rad->left))
            rad->size = rad->right->size + 1 + rad->left->size;

        else
            rad->size = size;
    
    if ((!rad->left) && (!rad->right))
        rad->size = 1;


    //printf("%d %d \n",rad->key,  rad->size);
   

    return rad;

}


void postorder(arbore_binar* p, int indent = 0)
{
    if (p != NULL) {
        
        
        if (indent) {
            
            std::cout <<std::string(indent, ' ') ;
        }

        cout << p->key << endl;
        if (p->left) postorder(p->left, indent + 4);
        if (p->right) postorder(p->right, indent + 4);
    }
}

struct arbore_binar* OS_SELECT(arbore_binar* rad, int poz) {

    if (poz == 0)
        return NULL;

    int r = 1;
    if (!rad)
        return NULL;

    if(rad->left)
    r= rad->left->size + 1;
       

    if (poz == r)
        return rad;

    else if (poz < r && rad->left)
        return OS_SELECT(rad->left, poz);

    else
    {
        if(rad->right)
        return OS_SELECT(rad->right, poz - r);
    }
        
    
        

}

struct arbore_binar* succesor(arbore_binar* rad) {
    struct arbore_binar* current = rad;

    while (current && current->left != NULL)
        current = current->left;

    return current;
}


struct arbore_binar* OS_DELETE(arbore_binar* rad, int poz) {

    if (poz == 0)
        return NULL;

    int r = 1;
    if (!rad)
        return NULL;

    if (rad->left) {
        r = rad->left->size + 1;
    }
        
    if (poz < r && rad->left) {
        rad->left = OS_DELETE(rad->left, poz);
        return rad;
    }
        

    else if(poz>r && rad->right)
    {
        rad->right= OS_DELETE(rad->right, poz - r);
        return rad;
    }

   
        if (!rad->left)
        {
            arbore_binar* actual = rad->right;
            free(rad);
            return actual;
        }


        else if (!rad->right) {
            arbore_binar* actual = rad->left;
            free(rad);
            return actual;
        }
        else {
            arbore_binar* parinte = rad;
            arbore_binar* actual = succesor(rad->right);

            if (parinte != rad)
                parinte->left = actual->right;
            else
                parinte->right = actual->right;

            rad->key=actual->key;

            free(actual);
            return rad;


        }
        
    

}

void demo() {
    int array[] = { 1,2,3,4,5,6,7,8,9,10,11 };

    arbore_binar* rad = Build_Tree(array, 0, 10, 0);
    postorder(rad);
    printf("\n");
    printf("%d \n", rad->size);

    arbore_binar* cautat = nod_arbore(0);
    cautat = OS_SELECT(rad, 5);
    if (cautat)
        printf("Elementul de gasit este: %d \n", cautat->key);
    else printf("Prea mic arbore\n");
    printf("\n");
    cautat = OS_DELETE(rad, 6);
    if (cautat)
        printf("Elementul de sters este: %d \n", cautat->key);
    else printf("Prea mic arbore\n");
    printf("\n");
    postorder(rad);

}

int main()
{
    demo();
}

The code prints this:

6
    3
        1
            2
        4
            5
    9
        7
            8
        10
            11
11
Elementul de gasit este: 5

Elementul de sters este: 7

7
    3
        1
            2
        4
            5
    8

But it can be clearly seen that it breaks the connection to 9 and so it does not print correctly. What can I do to improve it?

Answer 1

I will not write a code. I know you can manage it yourself. Just try to explain the way nodes are deleted from the BST. There are three basic cases:

1. If node is a leaf (does not have children) just delete the node

2. If node has one child, than the node is deleted, and its child comes to its place

3. If node has two children, than go to the left child of the node you are deleting. After that go right as far as you can. Delete node you are in (it can have at most one child) using case 1 or 2, and the label of deleted node write in the node you needed to delete.

There is a alternative for 3: you can go to the left child of the node, and than go left as far as you can.

Anyhow, I dont know what do you mean when talking about balanced BST. The tree you are building in the program is not a balanced BST. Balanced BSTs are AVL tree and red-black tree, and algorithms for insertion and deletion for them are, although basically the same, should contain balancing of the tree.

If I understand what you are doing, you use divide and conquer to build up the tree from sorted array. I have to point out that, if you have sorted array, no BST is needed. You can use binary search which will search array even faster that you can do in the BST. In fact, you will have the algorithm with the same complexity: O(lg n), but you will not need to build BST. The idea of BST is to speed up search in average if you have random array. For random array the average complexity of the search would be O(lg n), and worst-case still O(n). But if you use balanced BST (namely AVL or red-black tree), you will have worst-case search of complexity O(lg n).

Answer 2

You can do an inorder traversal and count (down) the number of nodes you visited.

#include <iostream>
#include <array>
#include <functional>
#include <type_traits>

using namespace std;

template<typename Data>
struct Node {
  Data data;
  Node *left = nullptr, *right = nullptr;

  Node(const Data& data) : data(data) {}
};

//template <typename Node>
//using Func = std::function<void(const Node *)>;

template<typename Node, typename preFunc = std::nullptr_t, typename inFunc = std::nullptr_t, typename postFunc = std::nullptr_t>
void Order(Node *root, preFunc pre = nullptr, inFunc in = nullptr, postFunc post = nullptr) {
  if constexpr (!std::is_same<preFunc, std::nullptr_t>::value)
    pre(root);
  if (root->left != nullptr) Order(root->left, pre, in, post);  //traverse left if exists
  if constexpr (!std::is_same<inFunc, std::nullptr_t>::value)
    in(root);
  if (root->right != nullptr) Order(root->right, pre, in, post);//traverse right if exists
  if constexpr (!std::is_same<postFunc, std::nullptr_t>::value)
    post(root);
}

int main() {
  std::array<Node<int>, 3> nodes { { { 2 }, { 1 }, { 3 } } };
  nodes[0].left = &nodes[1];
  nodes[0].right = &nodes[2];

  int cnt = 3;
  Node<int> *kth = nullptr;

  Order(&nodes[0],
      nullptr, //  [](const Node<int> * node) { std::cout << "Pre:" << node->data << '\n'; },
       [&cnt, &kth](Node<int> * node) mutable { if (!--cnt) kth = node; }
      //, nullptr// [](const Node<int> * node) { std::cout << "Post:" << node->data << '\n'; }
  );

  if (kth) {
    std::cout << kth->data << '\n';

    // delete kth
  }

  return 0;
}

This is unfortunately O(N) always, you could plaster the Order function with early out flags or misuse throw to stop early.

See this why tail recursion is ... difficult for this.