Блог

Описание: определите i-й наименьший элемент. Если i находится за пределами диапазона, возвращаем false , в противном случае true.

Я пытался реализовать разные версии, и это единственный способ, которым я использую свой для работы, но не в O (h).

  bool get_ith(int i, T amp;x) {
      int n = size();
      int sofar=0;

      if(i < 1 || i > n)
        return false;

      _get_ith(root, i, x, sofar);
      return true;
    }

  private:
    // recursive helper function that does most of the work
    static void _get_ith(bst_node *t, int i, T amp;x, int amp;sofar) {
      if(t==nullptr)
        return;
      _get_ith(t->left, i, x, sofar);

      if(sofar==i)
        return;
      sofar  ;
      if(sofar==i) {
        x = t->val;
        return;
      }
      _get_ith(t->right, i, x, sofar);
    }

  

Для каждого узла следите за количеством узлов в его поддереве. Обновляйте это число при выполнении операций, связанных с этим поддеревом.

Когда вам нужно найти i -й наименьший элемент в поддереве, вы должны посмотреть на количество узлов в левом поддереве корневого узла. Если это число больше или равно i (предполагая i , что оно с одним индексом), нужный узел находится в левом поддереве, и вы можете выполнить рекурсию / итерацию по нему. Если число точно i - 1 , текущий узел является желаемым узлом. В противном случае желаемый узел является i - (leftcount 1) -м узлом в правильном поддереве, и вы можете выполнить рекурсию / итерацию соответствующим образом.