K-мерное дерево

K-мерное дерево
Тип	Многомерное дерево Двоичное дерево поиска
Изобретено в	1975 году
Изобретено	Йон Бентли
Временная сложность в О-символике
	В среднем	В худшем случае
Расход памяти	O(n)	O(n)
Поиск	O(log n)	O(n)
Вставка	O(log n)	O(n)
Удаление	O(log n)	O(n)

В информатике k-d дерево (англ. k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и поиск ближайшего соседа). k-d деревья — особый вид двоичных деревьев поиска.

Математическое описание

K-мерное дерево — это несбалансированное дерево поиска для хранения точек из <math>\mathbb{R}^k</math>. Оно предлагает похожую на R-дерево возможность поиска в заданном диапазоне ключей. В ущерб простоте запросов, требования к памяти <math>O(kn)</math> вместо <math>O((log(n))^{k-1})</math>.

Существуют однородные и неоднородные k-d деревья. У однородных k-d деревьев каждый узел хранит запись. При неоднородном варианте внутренние узлы содержат только ключи, листья содержат ссылки на записи.

В неоднородном k-d дереве <math>H_i(t) = (x_1, x_2, \ldots , x_{i-1}, t , x_{i+1}, \ldots , x_k)</math> при <math>1 \leq i \leq k </math> параллельно оси <math>(k-1)</math>-мерной гиперплоскости в точке <math>t</math>. Для корня нужно разделить точки через гиперплоскость <math>H_1(t)</math> на два по возможности одинаково больших множества точек и записать <math>t</math> в корень, слева от этого сохраняются все точки у которых <math>x_1<t</math>, справа те у которых <math>x_1>t</math>. Для левого поддерева нужно разделить точки опять на новую «разделенную плоскость» <math>H_2(t)</math>, а <math>t</math> сохраняется во внутреннем узле. Слева от этого сохраняются все точки у которых <math>x_2<t</math>. Это продолжается рекурсивно над всеми пространствами. Потом всё начинается снова с первого пространства до того, пока каждую точку можно будет ясно идентифицировать через гиперплоскость.

K-d дерево можно построить за <math>O(n(k+log(n)))</math>. Поиск диапазона может быть выполнен за <math>O(n^{1-\frac{1}{k}}+a)</math>, при этом <math>a</math> обозначает размер ответа. Требование к памяти для самого дерева ограничено <math>O(kn)</math>.

Операции с k-d деревьями

Структура

Структура дерева, описанная на языке C++:

const int N=10; // количество пространств ключей

struct Item {   // структура элемента
  int key[N];   // массив ключей определяющих элемент
  char *info;   // информация элемента
};

struct Node {   // структура узла дерева
  Item i;       // элемент
  Node *left;   // левое  поддерево
  Node *right;  // правое поддерево
}

Структура дерева может меняться в зависимости от деталей реализации алгоритма. Например, в узле может содержаться не один элемент, а массив, что повышает эффективность поиска.

Анализ поиска элемента

Очевидно, что минимальное количество просмотренных элементов равно <math>1</math>, а максимальное количество просмотренных элементов — <math>O(h)</math>, где <math>h</math> — это высота дерева. Остаётся посчитать среднее количество просмотренных элементов <math>A_n</math>.

<math>[x_0,x_1,x_2,...,x_n]</math> — заданный элемент.

Рассмотрим случай <math>h=3</math>. Найденными элементами могут быть:

<math>

find(t_1): [(x_0=t_1)]; A=1. </math>

<math>

find(t_2): [(x_0<t_1)\land(x_0=t_2)]; A=2. </math>

<math>

find(t_3): [(x_0>t_1)\land(x_0=t_3)]; A=2. </math>

<math>

find(t_4): [(x_0<t_1)\land(x_0<t_2)\land(x_0=t_4)]; A=3. </math>

<math>

find(t_5): [(x_0<X_1)\land(x_0>t_2)\land(x_0=t_5)]; A=3. </math>

<math>

find(t_6): [(x_0<t_1)\land(x_0<t_3)\land(x_0=t_6)]; A=3. </math>

<math>

find(t_7): [(x_0<t_1)\land(x_0>t_3)\land(x_0=t_7)]; A=3. </math>

и так для каждого пространства ключей. При этом средняя длина поиска в одном пространстве составляет:

<math>A=\frac{1+2+2+3+3+3+3}{7}=\frac{17}{7}\approx 2,4</math>.

Средняя величина считается по формуле: <math>A_n=\sum_{k=1}^n kp_{n,k}</math>

Остаётся найти вероятность <math>p_{n,k}</math>. Она равна <math>p_{n,k}=\frac{p_{A,k}}{p_{n}}</math>, где <math>p_{A,k}</math> — число случаев, когда <math>A=k</math> и <math>p_{n}</math> — общее число случаев. Не сложно догадаться, что <math>p_{n,k}=\frac{2^{k-1}}{2^n-1}</math>.

Подставляем это в формулу для средней величины:

<math>

A_n=\sum_{k=1}^n kp_{n,k}=\sum_{k=1}^n {k\frac{2^{k-1}}{2^n-1}}=\frac{1}{2^n-1}\sum_{k=1}^n {k2^{k-1}}= </math>

<math>

\frac{1}{2^n-1}\sum_{k+1=1}^n {({k+1})2^k}=\frac{1}{2^n-1}(\sum_{k+1=1}^n {k2^k} + \sum_{k+1=1}^n {2^k})

</math>

<math>

\frac{1}{2^n-1}(\sum_{k=1}^n {k2^k} + \sum_{k=1}^n {2^k} - 2^n - n2^n)

</math>

<math>

=\frac{1}{2^n-1}(n2^{n+2} - (n+1)2^{n+1} +2 - 2^n + 2^3 -1 - n2^n) = \frac{2^n (n-1) +1}{2^n-1} </math>,

то есть <math>A_h=\frac{2^h (h-1) +1}{2^h-1}</math>, где <math>h</math> — высота дерева.

Если перейти от высоты дерева к количеству элементов, то:

<math>A_n=~O(\frac{2^h (h-1) +1}{2^h-1}) = ~O(h\frac{2^h}{2^h-1} - 1) = ~O(log(\frac{n}{N} +1)\frac{2^{log(\frac{n}{N} +1)}}{2^{log(\frac{n}{N} +1)}-1} - 1)=~O(log(\frac{n}{N} +1)\frac{n+N}{n}-1) =</math>

<math> =~O(log(\frac{n}{N} +1)^{\frac{n+N}{n}}-1)</math>, где <math>N</math> — количество элементов в узле.

Из этого можно сделать вывод, что чем больше элементов будет содержаться в узле, тем быстрее будет проходить поиск по дереву, так как высота дерева будет оставаться минимальной, однако не следует хранить огромное количество элементов в узле, так как при таком способе всё дерево может выродиться в обычный массив или список.

Добавление элементов

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

Алгоритм продвижения по дереву:

for (int i = 0; tree; i++) // i - это номер пространства
    if (tree->x[i] < tree->t)  // t - медиана
        tree = tree->left;     // переходим в левое поддерево
    else
        tree = tree->right;    // переходим в правое поддерево

Добавление выполняется за <math>O(h)</math>, где <math>h</math> — высота дерева.

Удаление элементов

При удалении элементов дерева может возникнуть несколько ситуаций:

• Удаление листа дерева — довольно простое удаление, когда удаляется один узел и указатель узла-предка просто обнуляется.

• Удаление узла дерева (не листа) — очень сложная процедура, при которой приходится перестраивать всё поддерево для данного узла.

Иногда процесс удаления узла решается модификациями k-d дерева. К примеру, если у нас в узле содержится массив элементов, то при удалении всего массива узел дерева остаётся, но новые элементы туда больше не записываются.

Поиск диапазона элементов

Поиск основан на обычном спуске по дереву, когда каждый узел проверяется на диапазон. Если медианы узла меньше или больше заданного диапазона в данном пространстве, то обход идет дальше по одной из ветвей дерева. Если же медиана узла входит полностью в заданный диапазон, то нужно посетить оба поддерева.

Алгоритм

Z – узел дерева
[(x_0_min, x_1_min, x_2_min,..., x_n_min),(x_0_max, x_1_max, x_2_max,..., x_n_max)] - заданный диапазон

Функция Array(Node *&Z){
If ([x_0_min, x_1_min, x_2_min,..., x_n_min]<Z){
		Z=Z->left; // левое поддерево
}
else
If ([x_0_max, x_1_max, x_2_max,..., x_n_max]>Z){
			Z=Z->right; // правое поддерево
}
		Else{ // просмотреть оба поддерева
			Array(Z->right); // запустить функцию для правого поддерева
			Z=Z->left; // просмотреть левое поддерево
		}
}

Анализ

Очевидно, что минимальное количество просмотренных элементов это <math>O(h)</math>, где <math>h</math> — высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это <math>O(2^h-1)</math>, то есть просмотр всех элементов дерева. Остаётся посчитать среднее количество просмотренных элементов <math>A_n</math>.

<math>[(x_{0_{min}}, x_{1_{min}}, x_{2_{min}},..., x_{n_{min}}),(x_{0_{max}}, x_{1_{max}}, x_{2_{max}},..., x_{n_{max}})]</math> — заданный диапазон.

Оригинальная статья про k-d деревья даёт такую характеристику: <math>A_n=~O(h \cdot log(h))</math> для фиксированного диапазона.

Если перейти от высоты дерева к количеству элементов, то это будет: <math>A_n=~O(log(log(n-1))^{log(n-1)})</math>

Поиск ближайшего соседа

Поиск ближайшего элемента разделяется на две подзадачи: определение возможного ближайшего элемента и поиск ближайших элементов в заданном диапазоне.

Дано дерево <math>tree</math>. Мы спускаемся по дереву к его листьям по условию <math>tree\to x[i](<,>=)tree\to t</math> и определяем вероятный ближайший элемент по условию <math>l_{min}=\sqrt{(({x_0-x[i]_0})^2 + ({x_1-x[i]_1})^2 + ... + ({x_n-x[i]_n})^2)}</math>. После этого от корня дерева запускается алгоритм поиска ближайшего элемента в заданном диапазоне, который определяется радиусом <math>R=l_{min}=\sqrt{(({x_0-x[i]_0})^2 + ({x_1-x[i]_1})^2 + ... + ({x_n-x[i]_n})^2)}</math>.

Радиус поиска корректируется при нахождении более близкого элемента.

Алгоритм

Z – корень дерева|
List – список ближайших элементов|
[x_0,x_1,x_2...,x_n] - элемент для которого ищется ближайшие
Len – минимальная длина

Функция Maybe_Near(Node *&Z){ // поиск ближайшего возможного элемента
	While(Z){
		// проверка элементов в узле
for(i=0;i<N;i++){
len_cur=sqrt((x_0-x[i]_0)^2 + (x_1-x[i]_1)^2 + ... + (x_n-x[i]_n)^2); // длина текущего элемента
if(Len>длины текущего элемента){
	Len=len_cur; // установление новой длины
	Delete(List); // очистка списка
	Add(List); // добавить новый элемент в список
}
		Else
if(длины равны)
					Add(List); // добавить новый элемент в список
			If((x_0=x[i]_0) && (x_1=x[i]_1) && ... && (x_n=x[i]_n)) 
				Return 1;
		}
		If([x_0,x_1,x_2...,x_n]<Z)
			Z=Z->left; // левое поддерево
If([x_0,x_1,x_2...,x_n]>Z)
			Z=Z->right; // правое поддерево			
}
}


Функция Near(Node *&Z){ // поиск ближайшего элемента в заданном диапазоне
	While(Z){
		// проверка элементов в узле
for(i=0;i<N;i++){
len_cur=sqrt((x_0-x[i]_0)^2 + (x_1-x[i]_1)^2 + ... + (x_n-x[i]_n)^2); // длина текущего элемента
if(Len>длины текущего элемента){
	Len=len_cur; // установление новой длины
	Delete(List); // очистка списка
	Add(List); // добавить новый элемент в список
}
		Else
if(длины равны)
					Add(List); // добавить новый элемент в список
		}
If([x_0,x_1,x_2...,x_n]+len>Z){ // если диапазон больше медианы 
			Near(Z->right); // просмотреть оба дерева
			Z=Z->left;			
}
		If([x_0,x_1,x_2...,x_n]<Z)
			Z=Z->left; // левое поддерево
If([x_0,x_1,x_2...,x_n]>Z)
			Z=Z->right; // правое поддерево			
}
}

Анализ

Очевидно, что минимальное количество просмотренных элементов это <math>O(h)</math>, где h — это высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это <math>O(2^h-1)</math>, то есть просмотр всех узлов. Остаётся посчитать среднее количество просмотренных элементов.

<math>[(x_0, x_1, x_2,..., x_n)]</math> — заданный элемент, относительно которого нужно найти ближайший. Эта задача разделяется на две подзадачи: нахождение ближайшего элемента в узле и нахождение ближайшего элемента в заданном диапазоне. Для решения первой подзадачи потребуется один спуск по дереву, то есть <math>O(h)</math>.

Для второй подзадачи, как мы уже вычислили, поиск элементов в заданном диапазоне выполняется за <math>O(h \cdot log(h))</math>. Чтобы узнать среднее, достаточно просто сложить эти две величины:

<math>=~O(h)+ ~O(h \cdot log(h)) = ~O(h) \cdot ({~O(log(h))+1}))</math>.

См. также

• R-дерево
• VP-дерево
• Задача поиска ближайшего соседа

Ссылки

• [libkdtree.alioth.debian.org libkdtree++], an open-source STL-like implementation of k-d trees in C++.
• [www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en A tutorial on KD Trees]
• [people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN FLANN] and its fork [code.google.com/p/nanoflann/ nanoflann], efficient C++ implementations of k-d tree algorithms.
• [code.google.com/p/kdtree/ kdtree] A simple C library for working with KD-Trees
• [donar.umiacs.umd.edu/quadtree/points/kdtree.html K-D Tree Demo, Java applet]
• [www.cs.umd.edu/~mount/ANN/ libANN] Approximate Nearest Neighbour Library includes a k-d tree implementation
• [www.vision.caltech.edu/malaa/software/research/image-search/ Caltech Large Scale Image Search Toolbox]: a Matlab toolbox implementing randomized k-d tree for fast approximate nearest neighbour search, in addition to LSH, Hierarchical K-Means, and Inverted File search algorithms.
• [dcgi.felk.cvut.cz/home/havran/phdthesis.html Heuristic Ray Shooting Algorithms], pp. 11 and after
• [intopii.com/into/ Into] contains open source implementations of exact and approximate (k)NN search methods using k-d trees in C++.

Отрывок, характеризующий K-мерное дерево

Наташа задумалась.
– Ах Соня, если бы ты знала его так, как я! Он сказал… Он спрашивал меня о том, как я обещала Болконскому. Он обрадовался, что от меня зависит отказать ему.
Соня грустно вздохнула.
– Но ведь ты не отказала Болконскому, – сказала она.
– А может быть я и отказала! Может быть с Болконским всё кончено. Почему ты думаешь про меня так дурно?
– Я ничего не думаю, я только не понимаю этого…
– Подожди, Соня, ты всё поймешь. Увидишь, какой он человек. Ты не думай дурное ни про меня, ни про него.
– Я ни про кого не думаю дурное: я всех люблю и всех жалею. Но что же мне делать?
Соня не сдавалась на нежный тон, с которым к ней обращалась Наташа. Чем размягченнее и искательнее было выражение лица Наташи, тем серьезнее и строже было лицо Сони.
– Наташа, – сказала она, – ты просила меня не говорить с тобой, я и не говорила, теперь ты сама начала. Наташа, я не верю ему. Зачем эта тайна?
– Опять, опять! – перебила Наташа.
– Наташа, я боюсь за тебя.
– Чего бояться?
– Я боюсь, что ты погубишь себя, – решительно сказала Соня, сама испугавшись того что она сказала.
Лицо Наташи опять выразило злобу.
– И погублю, погублю, как можно скорее погублю себя. Не ваше дело. Не вам, а мне дурно будет. Оставь, оставь меня. Я ненавижу тебя.
– Наташа! – испуганно взывала Соня.
– Ненавижу, ненавижу! И ты мой враг навсегда!
Наташа выбежала из комнаты.
Наташа не говорила больше с Соней и избегала ее. С тем же выражением взволнованного удивления и преступности она ходила по комнатам, принимаясь то за то, то за другое занятие и тотчас же бросая их.
Как это ни тяжело было для Сони, но она, не спуская глаз, следила за своей подругой.
Накануне того дня, в который должен был вернуться граф, Соня заметила, что Наташа сидела всё утро у окна гостиной, как будто ожидая чего то и что она сделала какой то знак проехавшему военному, которого Соня приняла за Анатоля.
Соня стала еще внимательнее наблюдать свою подругу и заметила, что Наташа была всё время обеда и вечер в странном и неестественном состоянии (отвечала невпопад на делаемые ей вопросы, начинала и не доканчивала фразы, всему смеялась).
После чая Соня увидала робеющую горничную девушку, выжидавшую ее у двери Наташи. Она пропустила ее и, подслушав у двери, узнала, что опять было передано письмо. И вдруг Соне стало ясно, что у Наташи был какой нибудь страшный план на нынешний вечер. Соня постучалась к ней. Наташа не пустила ее.
«Она убежит с ним! думала Соня. Она на всё способна. Нынче в лице ее было что то особенно жалкое и решительное. Она заплакала, прощаясь с дяденькой, вспоминала Соня. Да это верно, она бежит с ним, – но что мне делать?» думала Соня, припоминая теперь те признаки, которые ясно доказывали, почему у Наташи было какое то страшное намерение. «Графа нет. Что мне делать, написать к Курагину, требуя от него объяснения? Но кто велит ему ответить? Писать Пьеру, как просил князь Андрей в случае несчастия?… Но может быть, в самом деле она уже отказала Болконскому (она вчера отослала письмо княжне Марье). Дяденьки нет!» Сказать Марье Дмитриевне, которая так верила в Наташу, Соне казалось ужасно. «Но так или иначе, думала Соня, стоя в темном коридоре: теперь или никогда пришло время доказать, что я помню благодеяния их семейства и люблю Nicolas. Нет, я хоть три ночи не буду спать, а не выйду из этого коридора и силой не пущу ее, и не дам позору обрушиться на их семейство», думала она.


Анатоль последнее время переселился к Долохову. План похищения Ростовой уже несколько дней был обдуман и приготовлен Долоховым, и в тот день, когда Соня, подслушав у двери Наташу, решилась оберегать ее, план этот должен был быть приведен в исполнение. Наташа в десять часов вечера обещала выйти к Курагину на заднее крыльцо. Курагин должен был посадить ее в приготовленную тройку и везти за 60 верст от Москвы в село Каменку, где был приготовлен расстриженный поп, который должен был обвенчать их. В Каменке и была готова подстава, которая должна была вывезти их на Варшавскую дорогу и там на почтовых они должны были скакать за границу.
У Анатоля были и паспорт, и подорожная, и десять тысяч денег, взятые у сестры, и десять тысяч, занятые через посредство Долохова.
Два свидетеля – Хвостиков, бывший приказный, которого употреблял для игры Долохов и Макарин, отставной гусар, добродушный и слабый человек, питавший беспредельную любовь к Курагину – сидели в первой комнате за чаем.
В большом кабинете Долохова, убранном от стен до потолка персидскими коврами, медвежьими шкурами и оружием, сидел Долохов в дорожном бешмете и сапогах перед раскрытым бюро, на котором лежали счеты и пачки денег. Анатоль в расстегнутом мундире ходил из той комнаты, где сидели свидетели, через кабинет в заднюю комнату, где его лакей француз с другими укладывал последние вещи. Долохов считал деньги и записывал.
– Ну, – сказал он, – Хвостикову надо дать две тысячи.
– Ну и дай, – сказал Анатоль.
– Макарка (они так звали Макарина), этот бескорыстно за тебя в огонь и в воду. Ну вот и кончены счеты, – сказал Долохов, показывая ему записку. – Так?
– Да, разумеется, так, – сказал Анатоль, видимо не слушавший Долохова и с улыбкой, не сходившей у него с лица, смотревший вперед себя.
Долохов захлопнул бюро и обратился к Анатолю с насмешливой улыбкой.
– А знаешь что – брось всё это: еще время есть! – сказал он.
– Дурак! – сказал Анатоль. – Перестань говорить глупости. Ежели бы ты знал… Это чорт знает, что такое!
– Право брось, – сказал Долохов. – Я тебе дело говорю. Разве это шутка, что ты затеял?
– Ну, опять, опять дразнить? Пошел к чорту! А?… – сморщившись сказал Анатоль. – Право не до твоих дурацких шуток. – И он ушел из комнаты.
Долохов презрительно и снисходительно улыбался, когда Анатоль вышел.
– Ты постой, – сказал он вслед Анатолю, – я не шучу, я дело говорю, поди, поди сюда.
Анатоль опять вошел в комнату и, стараясь сосредоточить внимание, смотрел на Долохова, очевидно невольно покоряясь ему.
– Ты меня слушай, я тебе последний раз говорю. Что мне с тобой шутить? Разве я тебе перечил? Кто тебе всё устроил, кто попа нашел, кто паспорт взял, кто денег достал? Всё я.
– Ну и спасибо тебе. Ты думаешь я тебе не благодарен? – Анатоль вздохнул и обнял Долохова.
– Я тебе помогал, но всё же я тебе должен правду сказать: дело опасное и, если разобрать, глупое. Ну, ты ее увезешь, хорошо. Разве это так оставят? Узнается дело, что ты женат. Ведь тебя под уголовный суд подведут…
– Ах! глупости, глупости! – опять сморщившись заговорил Анатоль. – Ведь я тебе толковал. А? – И Анатоль с тем особенным пристрастием (которое бывает у людей тупых) к умозаключению, до которого они дойдут своим умом, повторил то рассуждение, которое он раз сто повторял Долохову. – Ведь я тебе толковал, я решил: ежели этот брак будет недействителен, – cказал он, загибая палец, – значит я не отвечаю; ну а ежели действителен, всё равно: за границей никто этого не будет знать, ну ведь так? И не говори, не говори, не говори!
– Право, брось! Ты только себя свяжешь…
– Убирайся к чорту, – сказал Анатоль и, взявшись за волосы, вышел в другую комнату и тотчас же вернулся и с ногами сел на кресло близко перед Долоховым. – Это чорт знает что такое! А? Ты посмотри, как бьется! – Он взял руку Долохова и приложил к своему сердцу. – Ah! quel pied, mon cher, quel regard! Une deesse!! [О! Какая ножка, мой друг, какой взгляд! Богиня!!] A?
Долохов, холодно улыбаясь и блестя своими красивыми, наглыми глазами, смотрел на него, видимо желая еще повеселиться над ним.
– Ну деньги выйдут, тогда что?
– Тогда что? А? – повторил Анатоль с искренним недоумением перед мыслью о будущем. – Тогда что? Там я не знаю что… Ну что глупости говорить! – Он посмотрел на часы. – Пора!
Анатоль пошел в заднюю комнату.
– Ну скоро ли вы? Копаетесь тут! – крикнул он на слуг.
Долохов убрал деньги и крикнув человека, чтобы велеть подать поесть и выпить на дорогу, вошел в ту комнату, где сидели Хвостиков и Макарин.
Анатоль в кабинете лежал, облокотившись на руку, на диване, задумчиво улыбался и что то нежно про себя шептал своим красивым ртом.
– Иди, съешь что нибудь. Ну выпей! – кричал ему из другой комнаты Долохов.
– Не хочу! – ответил Анатоль, всё продолжая улыбаться.
– Иди, Балага приехал.
Анатоль встал и вошел в столовую. Балага был известный троечный ямщик, уже лет шесть знавший Долохова и Анатоля, и служивший им своими тройками. Не раз он, когда полк Анатоля стоял в Твери, с вечера увозил его из Твери, к рассвету доставлял в Москву и увозил на другой день ночью. Не раз он увозил Долохова от погони, не раз он по городу катал их с цыганами и дамочками, как называл Балага. Не раз он с их работой давил по Москве народ и извозчиков, и всегда его выручали его господа, как он называл их. Не одну лошадь он загнал под ними. Не раз он был бит ими, не раз напаивали они его шампанским и мадерой, которую он любил, и не одну штуку он знал за каждым из них, которая обыкновенному человеку давно бы заслужила Сибирь. В кутежах своих они часто зазывали Балагу, заставляли его пить и плясать у цыган, и не одна тысяча их денег перешла через его руки. Служа им, он двадцать раз в году рисковал и своей жизнью и своей шкурой, и на их работе переморил больше лошадей, чем они ему переплатили денег. Но он любил их, любил эту безумную езду, по восемнадцати верст в час, любил перекувырнуть извозчика и раздавить пешехода по Москве, и во весь скок пролететь по московским улицам. Он любил слышать за собой этот дикий крик пьяных голосов: «пошел! пошел!» тогда как уж и так нельзя было ехать шибче; любил вытянуть больно по шее мужика, который и так ни жив, ни мертв сторонился от него. «Настоящие господа!» думал он.
Анатоль и Долохов тоже любили Балагу за его мастерство езды и за то, что он любил то же, что и они. С другими Балага рядился, брал по двадцати пяти рублей за двухчасовое катанье и с другими только изредка ездил сам, а больше посылал своих молодцов. Но с своими господами, как он называл их, он всегда ехал сам и никогда ничего не требовал за свою работу. Только узнав через камердинеров время, когда были деньги, он раз в несколько месяцев приходил поутру, трезвый и, низко кланяясь, просил выручить его. Его всегда сажали господа.