Algoritmo para encontrar la diferencia máxima en una matriz de números

Question

Tengo una matriz de unos pocos millones de números.

double* const data = new double (3600000); 

necesito para iterar a través de la matriz y encontrar el rango (el valor más grande de la matriz menos el valor más pequeño). Sin embargo, hay una trampa. Solo quiero encontrar el rango donde los valores más pequeños y más grandes están dentro de 1,000 muestras el uno del otro.

Así que necesito encontrar el máximo de: rango (datos + 0, datos + 1000), rango (datos + 1, datos + 1001), rango (datos + 2, datos + 1002), .... , rango (datos + 3599000, datos + 3600000).

Espero que tenga sentido. Básicamente podría hacerlo como arriba, pero estoy buscando un algoritmo más eficiente si existe. Creo que el algoritmo anterior es O (n), pero creo que es posible optimizarlo. Una idea con la que estoy jugando es hacer un seguimiento de los máximos y mínimos más recientes y de lo atrás que están, y luego retroceder solo cuando sea necesario.

Voy a codificar esto en C++, pero un buen algoritmo en pseudocódigo estaría bien. Además, si este número que estoy tratando de encontrar tiene un nombre, me gustaría saber de qué se trata.

Gracias.

Answer 1

El algoritmo que describes es realmente O (N), pero creo que la constante es demasiado alta. Otra solución que parece razonable es utilizar O (N * log (N)) algoritmo de la siguiente manera:

* create sorted container (std::multiset) of first 1000 numbers 
* in loop (j=1, j<(3600000-1000); ++j) 
    - calculate range 
    - remove from the set number which is now irrelevant (i.e. in index *j - 1* of the array) 
    - add to set new relevant number (i.e. in index *j+1000-1* of the array) 

creo que debería ser más rápido, debido a la constante es mucho menor.

Answer 2

Este tipo de pregunta pertenece a una rama de algoritmos llamada algoritmos de transmisión. Es el estudio de problemas que no solo requieren una solución O (n) sino que también necesitan trabajar en un solo paso sobre los datos. los datos se ingresan como una secuencia al algoritmo, el algoritmo no puede guardar todos los datos y, a continuación, se pierde para siempre. el algoritmo necesita obtener alguna respuesta sobre los datos, como, por ejemplo, el mínimo o la mediana.

Específicamente está buscando un máximo (o más comúnmente en la literatura - mínimo) en una ventana sobre una secuencia.

Here's a presentation que menciona este problema como un problema secundario de lo que están tratando de obtener. podría darte algunas ideas.

Creo que el esquema de la solución es algo así: mantenga la ventana sobre la secuencia donde en cada paso se inserta un elemento en la ventana y se retira uno del otro (una ventana deslizante). Los elementos que realmente conserva en la memoria no son todos los 1000 elementos en la ventana, sino representantes seleccionados que serán buenos candidatos para ser el mínimo (o máximo).

lea el artículo. es un poco complejo, pero después de 2-3 lecturas puedes entenderlo.

Answer 3

Esta es una buena aplicación de cola mínima - una cola (First-In, First-Out = FIFO) que puede realizar un seguimiento simultáneo del elemento mínimo que contiene, con actualizaciones amortizadas de tiempo constante. Por supuesto, una cola máxima es básicamente la misma cosa.

Una vez que tenga esta estructura de datos en su lugar, puede considerar CurrentMax (de los últimos 1000 elementos) menos CurrentMin, almacenar eso como BestSoFar, y luego presionar un nuevo valor y mostrar el valor anterior, y verificar nuevamente.De esta manera, siga actualizando BestSoFar hasta que el valor final sea la solución a su pregunta. Cada paso único lleva un tiempo constante amortizado, por lo que todo es lineal, y la implementación que conozco tiene una buena constante escalar (es rápida).

No conozco ninguna documentación sobre min-queue's: esta es una estructura de datos que surgió en colaboración con un compañero de trabajo. Puede implementarlo rastreando internamente un árbol binario de los elementos mínimos dentro de cada subsecuencia contigua de sus datos. Simplifica el problema de que solo extraerá datos de un extremo de la estructura.

Si está interesado en obtener más información, puedo intentar proporcionarla. Estaba pensando en escribir esta estructura de datos como un documento para arxiv. También tenga en cuenta que Tarjan y otros previamente llegaron a una estructura min-deque más poderosa que funcionaría aquí, pero la implementación es mucho más compleja. Puede google for "mindeque" para leer sobre el trabajo de Tarjan et al.

Answer 4

idea del algoritmo:

dar los primeros 1000 valores de los datos y ordenarlos
El último de la clase - la primera es la gama (datos + 0, los datos + 999).
Entonces quitar de la pila tipo el primer elemento con los datos de valor [0]
y añadir los datos de elementos de [1000]
Ahora, el último de la clase - la primera es la gama (datos + 1, los datos + 1000)
Repita hasta que esté hecho

// This should run in (DATA_LEN - RANGE_WIDTH)log(RANGE_WIDTH) 
#include <set> 
#include <algorithm> 
using namespace std; 

const int DATA_LEN = 3600000; 
double* const data = new double (DATA_LEN); 

.... 
.... 

const int RANGE_WIDTH = 1000; 
double range = new double(DATA_LEN - RANGE_WIDTH); 
multiset<double> data_set; 
data_set.insert(data[i], data[RANGE_WIDTH]); 

for (int i = 0 ; i < DATA_LEN - RANGE_WIDTH - 1 ; i++) 
{ 
    range[i] = *data_set.end() - *data_set.begin(); 
    multiset<double>::iterator iter = data_set.find(data[i]); 
    data_set.erase(iter); 
    data_set.insert(data[i+1]); 
} 
range[i] = *data_set.end() - *data_set.begin(); 

// range now holds the values you seek 

Probablemente debería comprobar esto para off por 1 errores, pero la idea está ahí.

Answer 5

std::multiset<double> range; 
double currentmax = 0.0; 
for (int i = 0; i < 3600000; ++i) 
{ 
    if (i >= 1000) 
     range.erase(range.find(data[i-1000])); 
    range.insert(data[i]); 
    if (i >= 999) 
     currentmax = max(currentmax, *range.rbegin()); 
} 

Nota código no probado.

corregir: error fijo por error.

Answer 6

1. lea en los primeros 1000 números.
2. crea una lista vinculada de 1000 elementos que rastrea el número 1000 actual.
3. crear una matriz de 1000 elementos de punteros a los nodos de lista vinculados, 1-1 mapeo.
4. ordena la matriz de puntero en función de los valores del nodo de la lista vinculada. Esto reorganizará la matriz pero mantendrá intacta la lista vinculada.
5. ahora puede calcular el rango para los primeros 1000 números mediante el examen del primer y último elemento de la matriz de puntero.
6. elimina el primer elemento insertado, que es la cabeza o la cola dependiendo de cómo hayas hecho tu lista vinculada. Usando el valor del nodo realice una búsqueda binaria en la matriz de punteros para encontrar el puntero del nodo que se va a eliminar, y desplace la matriz uno para eliminarlo.
7. agregue el elemento 1001o a la lista vinculada e inserte un puntero en la posición correcta en la matriz, realizando un paso de una ordenación por inserción. Esto mantendrá la matriz ordenada.
8. ahora usted tiene el min. y max. valor de los números entre 1 y 1001, y puede calcular el rango usando el primer y último elemento de la matriz de punteros.
9. ahora debería ser obvio lo que debe hacer para el resto de la matriz.

El algoritmo debe ser O (n) ya que la eliminación y la inserción está limitada por el registro (1e3) y todo lo demás lleva tiempo constante.

Answer 7

Decidí ver cuál era el algoritmo más eficiente que se me ocurrió para resolver este problema utilizando el código real y los tiempos reales. Primero creé una solución simple, una que sigue el mínimo/máximo para las n entradas previas usando un buffer circular, y un arnés de prueba para medir la velocidad. En la solución simple, cada valor de datos se compara con el conjunto de valores mínimos/máximos, por lo que se trata de pruebas de recuento window_size * (donde el tamaño de ventana en la pregunta original es 1000 y el recuento es 3600000).

Pensé en cómo hacerlo más rápido. En primer lugar, creé una solución que utilizaba una cola fifo para almacenar valores de tamaño de ventana y una lista vinculada para almacenar los valores en orden ascendente donde cada nodo en la lista vinculada también era un nodo en la cola. Para procesar un valor de datos, el elemento al final de la fifo se eliminó de la lista vinculada y la cola. El nuevo valor se agregó al inicio de la cola y se utilizó una búsqueda lineal para encontrar la posición en la lista vinculada. Los valores mínimo y máximo podrían leerse desde el inicio y el final de la lista vinculada. Esto fue rápido, pero no se escalaría bien al aumentar el tamaño de la ventana (es decir, de forma lineal).

Así que decidí agregar un árbol binario al sistema para tratar de acelerar la parte de búsqueda del algoritmo. Los tiempos finales para window_size = 1,000 y contar = 3600000 fueron:

Simple: 106875 
Quite Complex: 1218 
Complex: 1219 

que tanto se esperaba e inesperado. Se esperaba que el uso de una lista de enlaces ordenados ayudara, de forma inesperada, a que la sobrecarga de tener un árbol de auto-equilibrio no compensara la ventaja de una búsqueda más rápida. Probé los dos últimos con un tamaño de ventana aumentado y encontré que siempre eran casi idénticos hasta un tamaño de ventana de 100000.

Lo que demuestra que teorizar sobre algoritmos es una cosa, implementarlos es otra cosa.

De todos modos, para aquellos que estén interesados, aquí está el código que he escrito (hay un poco!):

Range.h:

#include <algorithm> 
#include <iostream> 
#include <ctime> 

using namespace std; 

// Callback types. 
typedef void (*OutputCallback) (int min, int max); 
typedef int (*GeneratorCallback)(); 

// Declarations of the test functions. 
clock_t Simple (int, int, GeneratorCallback, OutputCallback); 
clock_t QuiteComplex (int, int, GeneratorCallback, OutputCallback); 
clock_t Complex (int, int, GeneratorCallback, OutputCallback); 

main.cpp:

#include "Range.h" 

int 
    checksum; 

// This callback is used to get data. 
int CreateData() 
{ 
    return rand(); 
} 

// This callback is used to output the results. 
void OutputResults (int min, int max) 
{ 
    //cout << min << " - " << max << endl; 
    checksum += max - min; 
} 

// The program entry point. 
void main() 
{ 
    int 
    count = 3600000, 
    window = 1000; 

    srand (0); 
    checksum = 0; 
    std::cout << "Simple: Ticks = " << Simple (count, window, CreateData, OutputResults) << ", checksum = " << checksum << std::endl; 
    srand (0); 
    checksum = 0; 
    std::cout << "Quite Complex: Ticks = " << QuiteComplex (count, window, CreateData, OutputResults) << ", checksum = " << checksum << std::endl; 
    srand (0); 
    checksum = 0; 
    std::cout << "Complex: Ticks = " << Complex (count, window, CreateData, OutputResults) << ", checksum = " << checksum << std::endl; 
} 

Simple.cpp:

#include "Range.h" 

// Function to actually process the data. 
// A circular buffer of min/max values for the current window is filled 
// and once full, the oldest min/max pair is sent to the output callback 
// and replaced with the newest input value. Each value inputted is 
// compared against all min/max pairs. 
void ProcessData 
(
    int count, 
    int window, 
    GeneratorCallback input, 
    OutputCallback output, 
    int *min_buffer, 
    int *max_buffer 
) 
{ 
    int 
    i; 

    for (i = 0 ; i < window ; ++i) 
    { 
    int 
     value = input(); 

    min_buffer [i] = max_buffer [i] = value; 

    for (int j = 0 ; j < i ; ++j) 
    { 
     min_buffer [j] = min (min_buffer [j], value); 
     max_buffer [j] = max (max_buffer [j], value); 
    } 
    } 

    for (; i < count ; ++i) 
    { 
    int 
     index = i % window; 

    output (min_buffer [index], max_buffer [index]); 

    int 
     value = input(); 

    min_buffer [index] = max_buffer [index] = value; 

    for (int k = (i + 1) % window ; k != index ; k = (k + 1) % window) 
    { 
     min_buffer [k] = min (min_buffer [k], value); 
     max_buffer [k] = max (max_buffer [k], value); 
    } 
    } 

    output (min_buffer [count % window], max_buffer [count % window]); 
} 

// A simple method of calculating the results. 
// Memory management is done here outside of the timing portion. 
clock_t Simple 
(
    int count, 
    int window, 
    GeneratorCallback input, 
    OutputCallback output 
) 
{ 
    int 
    *min_buffer = new int [window], 
    *max_buffer = new int [window]; 

    clock_t 
    start = clock(); 

    ProcessData (count, window, input, output, min_buffer, max_buffer); 

    clock_t 
    end = clock(); 

    delete [] max_buffer; 
    delete [] min_buffer; 

    return end - start; 
} 

QuiteComplex.cpp:

#include "Range.h" 

template <class T> 
class Range 
{ 
private: 
    // Class Types 

    // Node Data 
    // Stores a value and its position in various lists. 
    struct Node 
    { 
    Node 
     *m_queue_next, 
     *m_list_greater, 
     *m_list_lower; 

    T 
     m_value; 
    }; 

public: 
    // Constructor 
    // Allocates memory for the node data and adds all the allocated 
    // nodes to the unused/free list of nodes. 
    Range 
    (
    int window_size 
) : 
    m_nodes (new Node [window_size]), 
    m_queue_tail (m_nodes), 
    m_queue_head (0), 
    m_list_min (0), 
    m_list_max (0), 
    m_free_list (m_nodes) 
    { 
    for (int i = 0 ; i < window_size - 1 ; ++i) 
    { 
     m_nodes [i].m_list_lower = &m_nodes [i + 1]; 
    } 

    m_nodes [window_size - 1].m_list_lower = 0; 
    } 

    // Destructor 
    // Tidy up allocated data. 
    ~Range() 
    { 
    delete [] m_nodes; 
    } 

    // Function to add a new value into the data structure. 
    void AddValue 
    (
    T value 
) 
    { 
    Node 
     *node = GetNode(); 

    // clear links 
    node->m_queue_next = 0; 

    // set value of node 
    node->m_value = value; 

    // find place to add node into linked list 
    Node 
     *search; 

    for (search = m_list_max ; search ; search = search->m_list_lower) 
    { 
     if (search->m_value < value) 
     { 
     if (search->m_list_greater) 
     { 
      node->m_list_greater = search->m_list_greater; 
      search->m_list_greater->m_list_lower = node; 
     } 
     else 
     { 
      m_list_max = node; 
     } 

     node->m_list_lower = search; 
     search->m_list_greater = node; 
     } 
    } 

    if (!search) 
    { 
     m_list_min->m_list_lower = node; 
     node->m_list_greater = m_list_min; 
     m_list_min = node; 
    } 
    } 

    // Accessor to determine if the first output value is ready for use. 
    bool RangeAvailable() 
    { 
    return !m_free_list; 
    } 

    // Accessor to get the minimum value of all values in the current window. 
    T Min() 
    { 
    return m_list_min->m_value; 
    } 

    // Accessor to get the maximum value of all values in the current window. 
    T Max() 
    { 
    return m_list_max->m_value; 
    } 

private: 
    // Function to get a node to store a value into. 
    // This function gets nodes from one of two places: 
    // 1. From the unused/free list 
    // 2. From the end of the fifo queue, this requires removing the node from the list and tree 
    Node *GetNode() 
    { 
    Node 
     *node; 

    if (m_free_list) 
    { 
     // get new node from unused/free list and place at head 
     node = m_free_list; 

     m_free_list = node->m_list_lower; 

     if (m_queue_head) 
     { 
     m_queue_head->m_queue_next = node; 
     } 

     m_queue_head = node; 
    } 
    else 
    { 
     // get node from tail of queue and place at head 
     node = m_queue_tail; 

     m_queue_tail = node->m_queue_next; 
     m_queue_head->m_queue_next = node; 
     m_queue_head = node; 

     // remove node from linked list 
     if (node->m_list_lower) 
     { 
     node->m_list_lower->m_list_greater = node->m_list_greater; 
     } 
     else 
     { 
     m_list_min = node->m_list_greater; 
     } 

     if (node->m_list_greater) 
     { 
     node->m_list_greater->m_list_lower = node->m_list_lower; 
     } 
     else 
     { 
     m_list_max = node->m_list_lower; 
     } 
    } 

    return node; 
    } 

    // Member Data. 
    Node 
    *m_nodes, 
    *m_queue_tail, 
    *m_queue_head, 
    *m_list_min, 
    *m_list_max, 
    *m_free_list; 
}; 

// A reasonable complex but more efficent method of calculating the results. 
// Memory management is done here outside of the timing portion. 
clock_t QuiteComplex 
(
    int size, 
    int window, 
    GeneratorCallback input, 
    OutputCallback output 
) 
{ 
    Range <int> 
    range (window); 

    clock_t 
    start = clock(); 

    for (int i = 0 ; i < size ; ++i) 
    { 
    range.AddValue (input()); 

    if (range.RangeAvailable()) 
    { 
     output (range.Min(), range.Max()); 
    } 
    } 

    clock_t 
    end = clock(); 

    return end - start; 
} 

Complex.cpp:

#include "Range.h" 

template <class T> 
class Range 
{ 
private: 
    // Class Types 

    // Red/Black tree node colours. 
    enum NodeColour 
    { 
    Red, 
    Black 
    }; 

    // Node Data 
    // Stores a value and its position in various lists and trees. 
    struct Node 
    { 
    // Function to get the sibling of a node. 
    // Because leaves are stored as null pointers, it must be possible 
    // to get the sibling of a null pointer. If the object is a null pointer 
    // then the parent pointer is used to determine the sibling. 
    Node *Sibling 
    (
     Node *parent 
    ) 
    { 
     Node 
     *sibling; 

     if (this) 
     { 
     sibling = m_tree_parent->m_tree_less == this ? m_tree_parent->m_tree_more : m_tree_parent->m_tree_less; 
     } 
     else 
     { 
     sibling = parent->m_tree_less ? parent->m_tree_less : parent->m_tree_more; 
     } 

     return sibling; 
    } 

    // Node Members 
    Node 
     *m_queue_next, 
     *m_tree_less, 
     *m_tree_more, 
     *m_tree_parent, 
     *m_list_greater, 
     *m_list_lower; 

    NodeColour 
     m_colour; 

    T 
     m_value; 
    }; 

public: 
    // Constructor 
    // Allocates memory for the node data and adds all the allocated 
    // nodes to the unused/free list of nodes. 
    Range 
    (
    int window_size 
) : 
    m_nodes (new Node [window_size]), 
    m_queue_tail (m_nodes), 
    m_queue_head (0), 
    m_tree_root (0), 
    m_list_min (0), 
    m_list_max (0), 
    m_free_list (m_nodes) 
    { 
    for (int i = 0 ; i < window_size - 1 ; ++i) 
    { 
     m_nodes [i].m_list_lower = &m_nodes [i + 1]; 
    } 

    m_nodes [window_size - 1].m_list_lower = 0; 
    } 

    // Destructor 
    // Tidy up allocated data. 
    ~Range() 
    { 
    delete [] m_nodes; 
    } 

    // Function to add a new value into the data structure. 
    void AddValue 
    (
    T value 
) 
    { 
    Node 
     *node = GetNode(); 

    // clear links 
    node->m_queue_next = node->m_tree_more = node->m_tree_less = node->m_tree_parent = 0; 

    // set value of node 
    node->m_value = value; 

    // insert node into tree 
    if (m_tree_root) 
    { 
     InsertNodeIntoTree (node); 
     BalanceTreeAfterInsertion (node); 
    } 
    else 
    { 
     m_tree_root = m_list_max = m_list_min = node; 
     node->m_tree_parent = node->m_list_greater = node->m_list_lower = 0; 
    } 

    m_tree_root->m_colour = Black; 
    } 

    // Accessor to determine if the first output value is ready for use. 
    bool RangeAvailable() 
    { 
    return !m_free_list; 
    } 

    // Accessor to get the minimum value of all values in the current window. 
    T Min() 
    { 
    return m_list_min->m_value; 
    } 

    // Accessor to get the maximum value of all values in the current window. 
    T Max() 
    { 
    return m_list_max->m_value; 
    } 

private: 
    // Function to get a node to store a value into. 
    // This function gets nodes from one of two places: 
    // 1. From the unused/free list 
    // 2. From the end of the fifo queue, this requires removing the node from the list and tree 
    Node *GetNode() 
    { 
    Node 
     *node; 

    if (m_free_list) 
    { 
     // get new node from unused/free list and place at head 
     node = m_free_list; 

     m_free_list = node->m_list_lower; 

     if (m_queue_head) 
     { 
     m_queue_head->m_queue_next = node; 
     } 

     m_queue_head = node; 
    } 
    else 
    { 
     // get node from tail of queue and place at head 
     node = m_queue_tail; 

     m_queue_tail = node->m_queue_next; 
     m_queue_head->m_queue_next = node; 
     m_queue_head = node; 

     // remove node from tree 
     node = RemoveNodeFromTree (node); 
     RebalanceTreeAfterDeletion (node); 

     // remove node from linked list 
     if (node->m_list_lower) 
     { 
     node->m_list_lower->m_list_greater = node->m_list_greater; 
     } 
     else 
     { 
     m_list_min = node->m_list_greater; 
     } 

     if (node->m_list_greater) 
     { 
     node->m_list_greater->m_list_lower = node->m_list_lower; 
     } 
     else 
     { 
     m_list_max = node->m_list_lower; 
     } 
    } 

    return node; 
    } 

    // Rebalances the tree after insertion 
    void BalanceTreeAfterInsertion 
    (
    Node *node 
) 
    { 
    node->m_colour = Red; 

    while (node != m_tree_root && node->m_tree_parent->m_colour == Red) 
    { 
     if (node->m_tree_parent == node->m_tree_parent->m_tree_parent->m_tree_more) 
     { 
     Node 
      *uncle = node->m_tree_parent->m_tree_parent->m_tree_less; 

     if (uncle && uncle->m_colour == Red) 
     { 
      node->m_tree_parent->m_colour = Black; 
      uncle->m_colour = Black; 
      node->m_tree_parent->m_tree_parent->m_colour = Red; 
      node = node->m_tree_parent->m_tree_parent; 
     } 
     else 
     { 
      if (node == node->m_tree_parent->m_tree_less) 
      { 
      node = node->m_tree_parent; 
      LeftRotate (node); 
      } 

      node->m_tree_parent->m_colour = Black; 
      node->m_tree_parent->m_tree_parent->m_colour = Red; 
      RightRotate (node->m_tree_parent->m_tree_parent); 
     } 
     } 
     else 
     { 
     Node 
      *uncle = node->m_tree_parent->m_tree_parent->m_tree_more; 

     if (uncle && uncle->m_colour == Red) 
     { 
      node->m_tree_parent->m_colour = Black; 
      uncle->m_colour = Black; 
      node->m_tree_parent->m_tree_parent->m_colour = Red; 
      node = node->m_tree_parent->m_tree_parent; 
     } 
     else 
     { 
      if (node == node->m_tree_parent->m_tree_more) 
      { 
      node = node->m_tree_parent; 
      RightRotate (node); 
      } 

      node->m_tree_parent->m_colour = Black; 
      node->m_tree_parent->m_tree_parent->m_colour = Red; 
      LeftRotate (node->m_tree_parent->m_tree_parent); 
     } 
     } 
    } 
    } 

    // Adds a node into the tree and sorted linked list 
    void InsertNodeIntoTree 
    (
    Node *node 
) 
    { 
    Node 
     *parent = 0, 
     *child = m_tree_root; 

    bool 
     greater; 

    while (child) 
    { 
     parent = child; 
     child = (greater = node->m_value > child->m_value) ? child->m_tree_more : child->m_tree_less; 
    } 

    node->m_tree_parent = parent; 

    if (greater) 
    { 
     parent->m_tree_more = node; 

     // insert node into linked list 
     if (parent->m_list_greater) 
     { 
     parent->m_list_greater->m_list_lower = node; 
     } 
     else 
     { 
     m_list_max = node; 
     } 

     node->m_list_greater = parent->m_list_greater; 
     node->m_list_lower = parent; 
     parent->m_list_greater = node; 
    } 
    else 
    { 
     parent->m_tree_less = node; 

     // insert node into linked list 
     if (parent->m_list_lower) 
     { 
     parent->m_list_lower->m_list_greater = node; 
     } 
     else 
     { 
     m_list_min = node; 
     } 

     node->m_list_lower = parent->m_list_lower; 
     node->m_list_greater = parent; 
     parent->m_list_lower = node; 
    } 
    } 

    // Red/Black tree manipulation routine, used for removing a node 
    Node *RemoveNodeFromTree 
    (
    Node *node 
) 
    { 
    if (node->m_tree_less && node->m_tree_more) 
    { 
     // the complex case, swap node with a child node 
     Node 
     *child; 

     if (node->m_tree_less) 
     { 
     // find largest value in lesser half (node with no greater pointer) 
     for (child = node->m_tree_less ; child->m_tree_more ; child = child->m_tree_more) 
     { 
     } 
     } 
     else 
     { 
     // find smallest value in greater half (node with no lesser pointer) 
     for (child = node->m_tree_more ; child->m_tree_less ; child = child->m_tree_less) 
     { 
     } 
     } 

     swap (child->m_colour, node->m_colour); 

     if (child->m_tree_parent != node) 
     { 
     swap (child->m_tree_less, node->m_tree_less); 
     swap (child->m_tree_more, node->m_tree_more); 
     swap (child->m_tree_parent, node->m_tree_parent); 

     if (!child->m_tree_parent) 
     { 
      m_tree_root = child; 
     } 
     else 
     { 
      if (child->m_tree_parent->m_tree_less == node) 
      { 
      child->m_tree_parent->m_tree_less = child; 
      } 
      else 
      { 
      child->m_tree_parent->m_tree_more = child; 
      } 
     } 

     if (node->m_tree_parent->m_tree_less == child) 
     { 
      node->m_tree_parent->m_tree_less = node; 
     } 
     else 
     { 
      node->m_tree_parent->m_tree_more = node; 
     } 
     } 
     else 
     { 
     child->m_tree_parent = node->m_tree_parent; 
     node->m_tree_parent = child; 

     Node 
      *child_less = child->m_tree_less, 
      *child_more = child->m_tree_more; 

     if (node->m_tree_less == child) 
     { 
      child->m_tree_less = node; 
      child->m_tree_more = node->m_tree_more; 
      node->m_tree_less = child_less; 
      node->m_tree_more = child_more; 
     } 
     else 
     { 
      child->m_tree_less = node->m_tree_less; 
      child->m_tree_more = node; 
      node->m_tree_less = child_less; 
      node->m_tree_more = child_more; 
     } 

     if (!child->m_tree_parent) 
     { 
      m_tree_root = child; 
     } 
     else 
     { 
      if (child->m_tree_parent->m_tree_less == node) 
      { 
      child->m_tree_parent->m_tree_less = child; 
      } 
      else 
      { 
      child->m_tree_parent->m_tree_more = child; 
      } 
     } 
     } 

     if (child->m_tree_less) 
     { 
     child->m_tree_less->m_tree_parent = child; 
     } 

     if (child->m_tree_more) 
     { 
     child->m_tree_more->m_tree_parent = child; 
     } 

     if (node->m_tree_less) 
     { 
     node->m_tree_less->m_tree_parent = node; 
     } 

     if (node->m_tree_more) 
     { 
     node->m_tree_more->m_tree_parent = node; 
     } 
    } 

    Node 
     *child = node->m_tree_less ? node->m_tree_less : node->m_tree_more; 

    if (node->m_tree_parent->m_tree_less == node) 
    { 
     node->m_tree_parent->m_tree_less = child; 
    } 
    else 
    { 
     node->m_tree_parent->m_tree_more = child; 
    } 

    if (child) 
    { 
     child->m_tree_parent = node->m_tree_parent; 
    } 

    return node; 
    } 

    // Red/Black tree manipulation routine, used for rebalancing a tree after a deletion 
    void RebalanceTreeAfterDeletion 
    (
    Node *node 
) 
    { 
    Node 
     *child = node->m_tree_less ? node->m_tree_less : node->m_tree_more; 

    if (node->m_colour == Black) 
    { 
     if (child && child->m_colour == Red) 
     { 
     child->m_colour = Black; 
     } 
     else 
     { 
     Node 
      *parent = node->m_tree_parent, 
      *n = child; 

     while (parent) 
     { 
      Node 
      *sibling = n->Sibling (parent); 

      if (sibling && sibling->m_colour == Red) 
      { 
      parent->m_colour = Red; 
      sibling->m_colour = Black; 

      if (n == parent->m_tree_more) 
      { 
       LeftRotate (parent); 
      } 
      else 
      { 
       RightRotate (parent); 
      } 
      } 

      sibling = n->Sibling (parent); 

      if (parent->m_colour == Black && 
      sibling->m_colour == Black && 
      (!sibling->m_tree_more || sibling->m_tree_more->m_colour == Black) && 
      (!sibling->m_tree_less || sibling->m_tree_less->m_colour == Black)) 
      { 
      sibling->m_colour = Red; 
      n = parent; 
      parent = n->m_tree_parent; 
      continue; 
      } 
      else 
      { 
      if (parent->m_colour == Red && 
       sibling->m_colour == Black && 
       (!sibling->m_tree_more || sibling->m_tree_more->m_colour == Black) && 
       (!sibling->m_tree_less || sibling->m_tree_less->m_colour == Black)) 
      { 
       sibling->m_colour = Red; 
       parent->m_colour = Black; 
       break; 
      } 
      else 
      { 
       if (n == parent->m_tree_more && 
       sibling->m_colour == Black && 
       (sibling->m_tree_more && sibling->m_tree_more->m_colour == Red) && 
       (!sibling->m_tree_less || sibling->m_tree_less->m_colour == Black)) 
       { 
       sibling->m_colour = Red; 
       sibling->m_tree_more->m_colour = Black; 
       RightRotate (sibling); 
       } 
       else 
       { 
       if (n == parent->m_tree_less && 
        sibling->m_colour == Black && 
        (!sibling->m_tree_more || sibling->m_tree_more->m_colour == Black) && 
        (sibling->m_tree_less && sibling->m_tree_less->m_colour == Red)) 
       { 
        sibling->m_colour = Red; 
        sibling->m_tree_less->m_colour = Black; 
        LeftRotate (sibling); 
       } 
       } 

       sibling = n->Sibling (parent); 
       sibling->m_colour = parent->m_colour; 
       parent->m_colour = Black; 

       if (n == parent->m_tree_more) 
       { 
       sibling->m_tree_less->m_colour = Black; 
       LeftRotate (parent); 
       } 
       else 
       { 
       sibling->m_tree_more->m_colour = Black; 
       RightRotate (parent); 
       } 
       break; 
      } 
      } 
     } 
     } 
    } 
    } 

    // Red/Black tree manipulation routine, used for balancing the tree 
    void LeftRotate 
    (
    Node *node 
) 
    { 
    Node 
     *less = node->m_tree_less; 

    node->m_tree_less = less->m_tree_more; 

    if (less->m_tree_more) 
    { 
     less->m_tree_more->m_tree_parent = node; 
    } 

    less->m_tree_parent = node->m_tree_parent; 

    if (!node->m_tree_parent) 
    { 
     m_tree_root = less; 
    } 
    else 
    { 
     if (node == node->m_tree_parent->m_tree_more) 
     { 
     node->m_tree_parent->m_tree_more = less; 
     } 
     else 
     { 
     node->m_tree_parent->m_tree_less = less; 
     } 
    } 

    less->m_tree_more = node; 
    node->m_tree_parent = less; 
    } 

    // Red/Black tree manipulation routine, used for balancing the tree 
    void RightRotate 
    (
    Node *node 
) 
    { 
    Node 
     *more = node->m_tree_more; 

    node->m_tree_more = more->m_tree_less; 

    if (more->m_tree_less) 
    { 
     more->m_tree_less->m_tree_parent = node; 
    } 

    more->m_tree_parent = node->m_tree_parent; 

    if (!node->m_tree_parent) 
    { 
     m_tree_root = more; 
    } 
    else 
    { 
     if (node == node->m_tree_parent->m_tree_less) 
     { 
     node->m_tree_parent->m_tree_less = more; 
     } 
     else 
     { 
     node->m_tree_parent->m_tree_more = more; 
     } 
    } 

    more->m_tree_less = node; 
    node->m_tree_parent = more; 
    } 

    // Member Data. 
    Node 
    *m_nodes, 
    *m_queue_tail, 
    *m_queue_head, 
    *m_tree_root, 
    *m_list_min, 
    *m_list_max, 
    *m_free_list; 
}; 

// A complex but more efficent method of calculating the results. 
// Memory management is done here outside of the timing portion. 
clock_t Complex 
(
    int count, 
    int window, 
    GeneratorCallback input, 
    OutputCallback output 
) 
{ 
    Range <int> 
    range (window); 

    clock_t 
    start = clock(); 

    for (int i = 0 ; i < count ; ++i) 
    { 
    range.AddValue (input()); 

    if (range.RangeAvailable()) 
    { 
     output (range.Min(), range.Max()); 
    } 
    } 

    clock_t 
    end = clock(); 

    return end - start; 
}