// Написать (компилировать не нужно) вставку и поиск для дерева остатков
// (radix tree)
//
// Ключом является целое беззнаковое 32-битное число. Высота дерева должна
// определяться константой, т.е. в зависимости от значения этой константы мы
// получаем корректно работающее дерево различной высоты.
//
// Дерево остатков - это дерево высотой N (степень двойки), хранящее в листьях
// значения V по целочисленным беззнаковым ключам K. Пусть bits(X) - это число
// всех бит в X или sizeof(X) * 8 в терминах C. Каждый узел дерева хранит
// 2 ^ (bits(K) / N) (`^` - возведение в степень) указателей на узел следующего
// уровня или значение (если узел является листом). На i-м уровне указатель на
// узел (i + 1)'го уровня определяется в массиве i'го узла как (при адресации, в
// которой менее значимые биты ключа определяют индексы в верхних уровнях дерева).
 
#define N 4
 
typedef struct {
  // ......
} RtNode;
 
RtNode rt_root;
 
void rt_insert(unsigned int key, void *val) {
  // ...
}
 
/* Returns NULL if there is no element with such key. */
void *rt_lookup(unsigned int key) {
   // ...
}
 

Ly8g0J3QsNC/0LjRgdCw0YLRjCAo0LrQvtC80L/QuNC70LjRgNC+0LLQsNGC0Ywg0L3QtSDQvdGD0LbQvdC+KSDQstGB0YLQsNCy0LrRgyDQuCDQv9C+0LjRgdC6INC00LvRjyDQtNC10YDQtdCy0LAg0L7RgdGC0LDRgtC60L7QsgovLyAocmFkaXggdHJlZSkKLy8KLy8g0JrQu9GO0YfQvtC8INGP0LLQu9GP0LXRgtGB0Y8g0YbQtdC70L7QtSDQsdC10LfQt9C90LDQutC+0LLQvtC1IDMyLdCx0LjRgtC90L7QtSDRh9C40YHQu9C+LiDQktGL0YHQvtGC0LAg0LTQtdGA0LXQstCwINC00L7Qu9C20L3QsAovLyDQvtC/0YDQtdC00LXQu9GP0YLRjNGB0Y8g0LrQvtC90YHRgtCw0L3RgtC+0LksINGCLtC1LiDQsiDQt9Cw0LLQuNGB0LjQvNC+0YHRgtC4INC+0YIg0LfQvdCw0YfQtdC90LjRjyDRjdGC0L7QuSDQutC+0L3RgdGC0LDQvdGC0Ysg0LzRiwovLyDQv9C+0LvRg9GH0LDQtdC8INC60L7RgNGA0LXQutGC0L3QviDRgNCw0LHQvtGC0LDRjtGJ0LXQtSDQtNC10YDQtdCy0L4g0YDQsNC30LvQuNGH0L3QvtC5INCy0YvRgdC+0YLRiy4KLy8KLy8g0JTQtdGA0LXQstC+INC+0YHRgtCw0YLQutC+0LIgLSDRjdGC0L4g0LTQtdGA0LXQstC+INCy0YvRgdC+0YLQvtC5IE4gKNGB0YLQtdC/0LXQvdGMINC00LLQvtC50LrQuCksINGF0YDQsNC90Y/RidC10LUg0LIg0LvQuNGB0YLRjNGP0YUKLy8g0LfQvdCw0YfQtdC90LjRjyBWINC/0L4g0YbQtdC70L7Rh9C40YHQu9C10L3QvdGL0Lwg0LHQtdC30LfQvdCw0LrQvtCy0YvQvCDQutC70Y7Rh9Cw0LwgSy4g0J/Rg9GB0YLRjCBiaXRzKFgpIC0g0Y3RgtC+INGH0LjRgdC70L4KLy8g0LLRgdC10YUg0LHQuNGCINCyIFgg0LjQu9C4IHNpemVvZihYKSAqIDgg0LIg0YLQtdGA0LzQuNC90LDRhSBDLiDQmtCw0LbQtNGL0Lkg0YPQt9C10Lsg0LTQtdGA0LXQstCwINGF0YDQsNC90LjRggovLyAyIF4gKGJpdHMoSykgLyBOKSAoYF5gIC0g0LLQvtC30LLQtdC00LXQvdC40LUg0LIg0YHRgtC10L/QtdC90YwpINGD0LrQsNC30LDRgtC10LvQtdC5INC90LAg0YPQt9C10Lsg0YHQu9C10LTRg9GO0YnQtdCz0L4KLy8g0YPRgNC+0LLQvdGPINC40LvQuCDQt9C90LDRh9C10L3QuNC1ICjQtdGB0LvQuCDRg9C30LXQuyDRj9Cy0LvRj9C10YLRgdGPINC70LjRgdGC0L7QvCkuINCd0LAgaS3QvCDRg9GA0L7QstC90LUg0YPQutCw0LfQsNGC0LXQu9GMINC90LAKLy8g0YPQt9C10LsgKGkgKyAxKSfQs9C+INGD0YDQvtCy0L3RjyDQvtC/0YDQtdC00LXQu9GP0LXRgtGB0Y8g0LIg0LzQsNGB0YHQuNCy0LUgaSfQs9C+INGD0LfQu9CwINC60LDQuiAo0L/RgNC4INCw0LTRgNC10YHQsNGG0LjQuCwg0LIKLy8g0LrQvtGC0L7RgNC+0Lkg0LzQtdC90LXQtSDQt9C90LDRh9C40LzRi9C1INCx0LjRgtGLINC60LvRjtGH0LAg0L7Qv9GA0LXQtNC10LvRj9GO0YIg0LjQvdC00LXQutGB0Ysg0LIg0LLQtdGA0YXQvdC40YUg0YPRgNC+0LLQvdGP0YUg0LTQtdGA0LXQstCwKS4KCiNkZWZpbmUgTiA0Cgp0eXBlZGVmIHN0cnVjdCB7CiAgLy8gLi4uLi4uCn0gUnROb2RlOwoKUnROb2RlIHJ0X3Jvb3Q7Cgp2b2lkIHJ0X2luc2VydCh1bnNpZ25lZCBpbnQga2V5LCB2b2lkICp2YWwpIHsKICAvLyAuLi4KfQoKLyogUmV0dXJucyBOVUxMIGlmIHRoZXJlIGlzIG5vIGVsZW1lbnQgd2l0aCBzdWNoIGtleS4gKi8Kdm9pZCAqcnRfbG9va3VwKHVuc2lnbmVkIGludCBrZXkpIHsKICAgLy8gLi4uCn0K