Недавно, на одном из митингов моей команды, была поднята проблема отсутствия документации внутри кода. Было решено назначить ответственного за ведение документации. Нужно было найти подходящие инструменты документирования, определить стиль и регламент, представить решение команде. Я решил, что возьму эту задачу на себя, так как для меня это особенно важный вопрос. Мне, как новому сотруднику, было довольно тяжело разобраться в уже существующем коде без документации, и упустить возможность повлиять на ее появление я просто не мог. В итоге, в процессе определения стандарта для нашей команды и появилась эта статья. Я подумал о том, здесь присутствуют довольно интересные мысли, поэтому решил поделится ими здесь.

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

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

В данной части мы разберем вставку и балансировку. Эти вещи идут бок о бок, без балансировки дерево будет терять свои свойства, и толка от него будет мало.

Довольно долгое время я воевал с красно-черным деревом. Вся информация, которую я находил, была в духе "листья и корень дерева всегда черные, ПОТОМУ ЧТО", "топ 5 свойств красно-черного дерева" или "3 случая при балансировке и 12 случаев при удалении ноды". Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют "черной высотой"?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево, с которого мы и начнем.

Эта статья разделена на 3 логические части. Я рекомендую прочитать их в указанном порядке. Первая часть (данная) будет направлена на введение в кчд и знакомство с ним. Во второй части мы поговорим о балансировке и вставке в кчд. В третьей, завершающей, части мы разберем процесс удаления ноды. Наберитесь терпения и приятного чтения.