Операции над деревьями: двоичное дерево поиска, AVL, B-дерево, дерево отрезков — авторское изложение

ru · official · sha256:fb1b0d2a3a62bff5a12f78de02c4d5aa3c31d16362bc47e70fa4c324eed89ecfRU

§1. Дерево поиска, высота, баланс и дерево отрезков Двоичное дерево поиска — двоичное дерево, у каждого узла которого хранится ключ, причём все ключи левого поддерева меньше ключа узла, а все ключи правого — больше. Соглашение о РАВНЫХ ключах называется отдельно: настоящее изложение считает ключи различными, а хранение дубликатов — отдельным вариантом со счётчиком в узле. Свойство дерева поиска есть ИНВАРИАНТ структуры, а не свойство одной операции: каждая операция обязана его сохранять, и каждое обоснование ниже сводится к этому. Высота узла — длина наибольшего пути от него до листа в рёбрах; высота пустого дерева считается минус единицей, а высота листа — нулём. Соглашение о минус единице выбрано ради того, чтобы разность высот поддеревьев листа равнялась нулю без поправок. Дерево сбалансировано по AVL, когда у каждого узла разности высот левого и правого поддеревьев не превосходят единицы по модулю. Такое дерево имеет высоту порядка логарифма числа узлов — утверждение источника, доказываемое через числа Фибоначчи. Поворот — локальное перестроение трёх узлов и их поддеревьев, сохраняющее свойство дерева поиска и меняющее высоты. Малый поворот переставляет узел с одним потомком; большой поворот есть композиция двух малых в разные стороны, и он нужен, когда «излом» поддерева направлен внутрь. B-дерево порядка t — дерево, у каждого узла которого от t − 1 до 2t − 1 ключей (у корня — от одного), ключи упорядочены, а число потомков на единицу больше числа ключей; все листья лежат на одной глубине. Одинаковая глубина листьев есть тот инвариант, ради сохранения которого B-дерево растёт вверх, а не вниз. Дерево отрезков над последовательностью длины n — двоичное дерево, каждому узлу которого отвечает отрезок позиций, а листьям — отдельные позиции; в узле хранится свёртка значений его отрезка ассоциативной операцией. Ассоциативность обязательна: без неё свёртка двух половин не даёт свёртки целого. Нейтральный элемент операции нужен для пустых частей запроса; если его нет, описание обязано разбирать пустую часть отдельно, и это надо говорить прямо.

Referencing norms: AnswersHere, f-0589b9efc4449c34d8216bf4, f-1bf0cc0c2c1dd0b6bcd55d3d, f-224b2a4b4190db3bea52d61e, f-23af995cdecaea5c39bc3af9, f-2c31dbe56225c429bbafb5d2, f-31a8686f7e605394d753ac9f, f-370fd4a94a3e7f3040439a93, f-3caf51a63760653530568afd, f-3ef2c7f2cc158eb91e3fdbd9, f-41c4ffadd2f15a6328bc8ed5, f-456476f8f6855722024eb89a, f-465163c11c8d5708bfb992a3, f-4a23cb857648457c5b77c256, f-4e2018fb549d1fc281ca5a9d, f-57aa14b7df9bb45aa6e575d5, f-59d1b8fa617e21754935e05f, f-5d7a1307c97c6cc4cd3bf50e, f-666e6731608e1a9027a390ba, f-67d63e92feb659f889a88a95, f-69f86138460b704821842bd8, f-79be181301d6fa9c402edab6, f-83eae019eca637a562f7a0d9, f-8b46536af861a6258da230ea, f-8fd859316f8749c0434f46fe, f-99768c3817fb658dc1366cce, f-9999c4e4c090ad3f73bd2d18, f-9b3aa9b515362e9feda38151, f-a4dab6cceb8c06a751fe89c6, f-a9c34b195550ffb9de75139d, f-aedf2599b281a3b912c73f55, f-b7dc646a8cdc0d84a99115e0, f-bf7c0df520264cadd12ffee8, f-c2e6336162a6253256a163de, f-cce5e66892b1a0945334273d, f-cdfd9daa5a9871f467f62aa5, f-d067ed7d16d64eed45af640e, f-dee9e4d16b9c0b9e54b90ea1, f-e52c557942b060aea732e336, f-eef2fc3647cdb0df788bb893, f-f070f1f7c7c0718b783afbf6, f-f1f5ad7c505e01dcfc28c766, f-f3a5fe571f830776a730bed0, f-fb2c63aee4ecc6c08ab01525, f-fb323ba25f023f3ab2e1c3be

ru · official · sha256:18042c759d0e2598b09e608ee75701fee236deeef9611f1802cfcc9fb6a2adaeRU

§10. Построение дерева отрезков Задача: по последовательности длины n построить дерево отрезков со свёртками ассоциативной операцией. Вариант — рекурсивный сверху вниз с делением отрезка пополам. Узлу отвечает отрезок позиций. Отрезок из одной позиции даёт лист со значением этой позиции. Иначе отрезок делится пополам, строятся два поддерева, и значение узла есть свёртка значений потомков. Основание — ассоциативность операции §1: свёртка целого равна свёртке свёрток частей. Без ассоциативности всё построение бессмысленно, и это не оговорка, а предусловие. Мера убывания — длина отрезка; база рекурсии — отрезок из одной позиции. Оценка: число узлов не превосходит 4n при хранении в массиве, время построения линейно. Оценка 4n есть удобная верхняя граница для массива, а не точное число узлов; точное равно 2n − 1 при степени двойки.

Referencing norms: f-016e6bd7e44ef2415517eaac, f-04da31340062b62f1591cfc6, f-05dacedb5b055c395430fe4d, f-0a845a8b7397d08de029942c, f-0d857174cbbb1bc632ea8a1b, f-0f91a512600a6fd6ddb9fc01, f-105ffd5389d0a1750db132bd, f-180585c15ff49f0f191b81bb, f-22b332dbaca1b01b0ec3a72f, f-2422d288f9c0a260bd25c946, f-260f03e8aae5ce11ccdbdc9a, f-28eba80c9f9f116436b74105, f-2a18e7c70b3d789c76341ccc, f-2c5eb57ccc590cc9b9db98df, f-33fe1c9217da978bccc54b76, f-343908c5a55503dd20164cc2, f-37138cf44cc41227711ac90e, f-38fb72248964320610c8d30c, f-3d59403ef96c0f94376c9e29, f-4218a8c22bc7ab3584680bfc, f-45d93d0fba17eb235712a28e, f-4732c898689ac7c8126ad490, f-4e985c406a60b12c523be4a6, f-4f8992d90890703734adc00b, f-564c0178ac3f521105bb5497, f-590643c2dffbf4e6f109fc5e, f-5b0983f625d1c180fb3a49b2, f-5fc09ccac2e2aae0f600a45d, f-648d3191243f34f2d4ab24d0, f-66fe5c3209292d0174165dcd, f-6b347b32c6cec8f86244874c, f-6faf97de8a39ddfc5ebfc7f1, f-7187a7a6952cf18f3849672f, f-71c01ff2b55603fb9283f478, f-75165e5e9ed0053bd7b057e4, f-7727756bde5019a5c1d4a4ea, f-79411bd205625007576e222e, f-7f88d0778d63c06ab873443b, f-80c0ea854e703664b6a31089, f-8150cf4931cd8cb06aeae15c, f-82150d7ce6df24b5d3a37683, f-821536b3093563fb2d903c60, f-82958c7fb53acc1b275dc7e3, f-87deaca934374a35c93e5d21, f-88c445965e141726d0567182, f-89739faa55c5255ca4c2be93, f-8ae097c818797f778e9f60d9, f-8f69586a0f7fb22ff412b252, f-9b9633019d734d92f94f7342, f-9d4a42fbcceb801244a316e4, f-9f13d430bac6b630c720c6ec, f-9f8fa8e2dfbfb442c7ea4492, f-a6033960313f3c3bb110d679, f-a9bcd33e12a9f78529b2b1b3, f-a9c85bb2dc18d3de27c84aff, f-abd33d32626137132d263eb6, f-abec75ceca1b6e777d25acd1, f-b5648060c1157d10ddd633f4, f-b67bf5dfc10a4985f4b6c348, f-b70ab29677d4371a8a9fb324, f-b894c82b681b4819c5193e39, f-b9fe2e54c0b322a8d0110b9c, f-be9376a40bf9ebec748e0ca8, f-c4e314b436f376384e9ea93b, f-caf6a6e44c318d4b09fb95dd, f-d1054b2ff106e1f7d39fa534, f-d69d9887dce6a52d890ca920, f-d897ea1b6f6a251d6f27c36d, f-dc67438f033609ba12dd060f, f-dcf29f45342270f641eae497, f-e0beef9a8bfd626e54c1502e, f-e0e1cc4fad8cff29a68604cb, f-e1f1697961ad79cdaed84b95, f-e490752d5f1082ab114cb12f, f-eb8aef5f50acb2064b31e204, f-edeb5caba521a9cac4070028, f-f1a0b69a36d42fc5c9a44b48, f-f4ea419935ff2077cbb40850, f-f75a069c493377f35de3d84e, f-f7f7ddafbee477eedf84be4b, f-f857694f71f99ebb804c0215, f-f9750e187bbc693be030dce6

ru · official · sha256:65c8161d559d90bbb9de5835946e9a0ca22c05aec09cffd505fe156279e0a245RU

§11. Точечное обновление дерева отрезков Задача: изменить значение в одной позиции и обновить свёртки. Вариант — рекурсивный спуск к листу и пересчёт свёрток на обратном пути. Спуск ведётся в ту половину, которой принадлежит позиция. Достигнув листа, описание заменяет его значение. На обратном пути каждое значение пересчитывается как свёртка значений потомков. Пересчёт именно на ОБРАТНОМ пути существен: значение узла зависит от потомков, и пересчёт до спуска дал бы устаревший результат. Инвариант: после возврата из поддерева значение его корня есть свёртка текущих значений отрезка. Оценка: длина пути от корня к листу есть логарифм n; на каждом уровне одно сравнение и одна свёртка.

Referencing norms: f-02c5f1254fd90f790ee5935b, f-078a4b6cbf104c07cee4be77, f-0c03a057aaf361ffcb860c79, f-10903c839c2965e2d4418892, f-12ff26f5f7a0eebb193adb72, f-13283d78cba208044c85a45c, f-183be8897d6e1ac9c1aefff5, f-2265bb55b92bbaf776ba94dd, f-2348f106b82f15105d46ec10, f-23c16bead0b66bc0a39446b4, f-26a310d4a24e98a2066f1bbd, f-33cf16b5dd044b285d750e82, f-364b1277f34c9b1fa751777b, f-3ad90861ac2a70d9fe8d3c14, f-41318da3fdfb9c6a783ddc4a, f-4493a1500d0b8f6d814e4b06, f-4d2fb7dda0f1a9595c430707, f-54cae3165fba25838dba919b, f-56287d1bfb9554b2ea059747, f-566909c29d143767a0c593c9, f-576d39cb1580634c5df56024, f-5bae8be952a464200881ccb3, f-5c782a85f39b43605815abfc, f-5d2a593a2b338e56dc6a9f6e, f-5d804562a3486e789cfc7d69, f-5fb7fec1fed7d4b54080c3de, f-600e43f32dab4d3df0d0e6b7, f-6437b2144ce905d66c34cdb8, f-68c0ab36cda44f133b89000c, f-698615ab5a2605a06cb8fe56, f-69931cb5e9957bc8658bf133, f-771e640ea4900db9e7feed83, f-804f2934cd8874cf5e9cfdf0, f-82a929263c48d281854db533, f-87a9ab2dc5c9e315faea4968, f-87ed3855073cd9dc16783c18, f-92ba10d7f8c63a04533ccacc, f-94f2c5412ac0a214458688de, f-97cb3b1fba9b65fc4b3e93ae, f-99b381d5354cc46dd60132b9, f-9edf31e222c600f0983c715b, f-aa96998b1a2999608979bdfa, f-aaf8e514f050991953ccc51d, f-ab504dbf5b4938f8adecdadd, f-ae374ad1eae34049e9afe774, f-af3d1cef856aef6e100ceb89, f-aff72c82a26b5238fbbd30a7, f-bb919c04d2b2f0004e4c8df1, f-bd93bd98539b0127ee35a07d, f-be0edf3f995693ddc594e651, f-c12a5e477f5eadf1801d4148, f-c187a44a690164607729d3f8, f-c698682f41da28a0e1664bd1, f-cce2ddee0903a1142fcea0ef, f-ceab16b8e65656f58b5c3467, f-d5c56f6e4772ddc8df6cfc5f, f-d86e98d7908e077f44ed3421, f-dc1eaf62711414ad5f061555, f-dc712e0d81074c54c32d85f8, f-dfadf9a1f2a1e821c50f004c, f-e4412d8adc50a299bddc7ea5, f-e608cf0a63256c4fa714bf2a, f-e68edfc6aeb2e975cca1d54f, f-e9595243effc7d9f0ef714b7, f-ed93d8302307015ad47972ba, f-eed576af44ca3abea53f0f6f, f-f0c4248931c41ad071f8e7ed, f-f0ca2e8c9d5f0da2f6fbbef0, f-f427ccdd8e445fe998ca27fe, f-fdd387d131add74aa268a44f, f-fe293f882c9bcaf6159a23d3

ru · official · sha256:7006658aea34b5cfbe6953b1cf95bac6768f7461cb3c2d2000edb2a1a6451e25RU

§12. Запрос на диапазоне в дереве отрезков Задача: по дереву отрезков и диапазону позиций получить свёртку значений этого диапазона. Вариант — рекурсивный с тремя случаями: непересечение, полное покрытие, частичное пересечение. Для узла: если его отрезок не пересекается с запросом, возвращается нейтральный элемент; если целиком лежит внутри запроса, возвращается хранимое значение; иначе запрос разбивается на два поддерева, и результаты сворачиваются. Случай непересечения требует нейтрального элемента; при его отсутствии описание обязано возвращать признак пустоты и разбирать его отдельно. Это названо прямо, потому что операция без нейтрального элемента — например, взятие минимума на неограниченном типе — встречается постоянно. Основание — ассоциативность §1 вместе с тем, что узлы полного покрытия образуют разбиение запрашиваемого диапазона. Число посещённых узлов не превосходит четырёх на уровень — утверждение источника, из которого и следует логарифмическая оценка. Доказательство остаётся в источнике. Оценка: время порядка логарифма n, дополнительная память — глубина рекурсии того же порядка.

Referencing norms: f-0081024472188942214459ea, f-0205c748d1391f0928251bc9, f-04850fbc142743bbf19d2da5, f-05f7634574301c9a1a6ddaea, f-07b751d62811c586fbeb13a0, f-0a0566ba818f1e8aab42ae93, f-0bfb8c52491f79704a439529, f-10b2d95bb937f4ed09645a19, f-117200718d800ffbaaa3a3ad, f-14229717693516a07dcafd44, f-1949e58e36afe20d870d3f95, f-1b182ce7912bb3c38f67bc2a, f-1be04885f2ae79ddfe2ddfb7, f-1e768866e153260383d7c8cc, f-23792245710a9e63e42a4945, f-25146dd3a782e9ef0428d9b5, f-2876f606a07e6c6a489b210b, f-3ae16bfd47744ef943c3814a, f-3af2d2ee3b32ea5bdebe8b29, f-4e5723cbf688b466dacce11e, f-4e6a2cebd88800ebe4850f54, f-4ff99ba40e99624d958864dc, f-529225dbf7c12382d22168e7, f-57a37da9fe3c5786c281e703, f-581261e380c7fc3fb0139774, f-58de49c978a02e5d0eba6e14, f-5b33418bb89edbb7cb7da5c5, f-5c45c7d75b21952c86b84f3d, f-5fb3cffccdbc3973fc33c724, f-66aac613bd6978c59002d655, f-686cf3e99c54c7ce2fd7210f, f-69e2b525ed851771e02fc6ca, f-708c3cbb65dbad75a521d572, f-75460322e9b3d870afb5908b, f-7583fd7f86a397d1e7dfc572, f-75b68b80b93b85ff8dcf01af, f-7a0fd7df258f87d88a4fd9cb, f-7d6f982bd2be3abbe901fd84, f-7e64c3d6a906bbd8a4cf9ddb, f-81a46db71611a08ae323085a, f-81b207ed192ce7e20e5982f9, f-8204a50eebf9b59f3daef54f, f-849159569869b6ddaa4500d9, f-8555e37cafa2ed8e51306b40, f-87624196032265614e92d38c, f-8b2dfdf599c5fabff54cebc7, f-9594227d793eebd70a2f7a35, f-9854b3ef2b00367c02e48de7, f-9a39382612fd42ed81dfae33, f-9ce7bb863feef429def75215, f-9e21bb991d613a70a7505c21, f-a006b22c87bc67b727b1a7c0, f-a0e55501c28353b270b912a8, f-a658bf13a608c2e605669cd4, f-a8ddd161593209c25377a5e8, f-a96dab7cc14c5684cccba2b1, f-ac88ca0993cdb0e62b6f0024, f-acdbe37db582de2a878fc628, f-ae4101e80955cb229f6695cf, f-ae888b02f0a58bad08be20fa, f-af280d48a7e4aa42bdc9464e, f-b4b7fa271cb32835490ed441, f-c4b11adeb113119df017910c, f-c991244060ce064bfea74308, f-d1196cd045477b9174b5d410, f-d1d13925e8d941a7adf7fee0, f-d49420688a2c06c739979e10, f-d522e56a5031c8ae29505ed7, f-de360ef793b39fbd2ddff865, f-e3ad14c918e4676149fa04a7, f-e606b2a330d14307f09cca0a, f-e8c4b33270018ac3b03589c1, f-ea6bac222bd411600e1a2cdf, f-eb37e60501a6b08597babd0d, f-eb38a86ac8352dd93c152e2d, f-f1fdcec64836db32365b07bd, f-f2aca78878ad1c27fe1472ca, f-f43f51f3749ae6ee803d1c74, f-f6b60ceeffebbac2cf2c9e54, f-fac9187f017f244b9681b0f7, f-fb199c71ae0ba8e79340f228, f-fb6a2d0927c83cfcca3ae2e2, f-fce69568b3665583586f36e4, f-fdb2c42570bb4b5fb7c0945c

ru · official · sha256:f248cd6c7a2d564d37eb7c340ed44fba1288e6746be09afdce4b3826713bf163RU

§2. Поиск в двоичном дереве поиска Задача: по дереву поиска и ключу найти узел с этим ключом либо установить его отсутствие. Вариант — спуск от корня со сравнением ключа в каждом узле. Текущий узел начинается с корня. Пока узел существует: при равенстве ключей узел найден; при меньшем искомом спуск идёт влево, при большем — вправо. Достижение пустого поддерева означает отсутствие ключа. Основание каждого шага — свойство дерева поиска §1: всё, что меньше ключа узла, лежит слева, и потому противоположную сторону просматривать незачем. Инвариант: искомый ключ, если он есть в дереве, лежит в поддереве текущего узла. Мера убывания — высота поддерева текущего узла. Оценка: число сравнений равно длине пути от корня, то есть не превосходит высоты дерева. Для сбалансированного дерева это логарифм; для вырожденного — линейно по числу узлов, и это главное, что заставляет вводить балансировку.

Referencing norms: f-01925ed5cb674f479faf225b, f-03e18c32aa3a9952c4658b61, f-0b239336c573877c545ef6c8, f-0e4dfd542ea222c13dcc372b, f-1a38fc9c6cefa30d979c2ca8, f-2212001bb48c81c7edd29c76, f-2355a6c9bec2f95753583953, f-26a3ceda3b2a8cb1298caf60, f-2ea9b99c5b2232c5e05844bf, f-33206f9f283007de40fd6b7c, f-38635f235ddbae4362b47075, f-3c80d6dd3a9016ea9740640a, f-412f9dc81d8b39910f7dd340, f-455e3152a52083d9567f28ff, f-46c9c15fb368b5205db5ffb7, f-4b412c9c1a49c7776b154202, f-4dd29bb124076edbb468326f, f-4e26f8d17350f77065e9c1ad, f-4e7a8e8a1ec8a0982ed0c481, f-4f473dc2c786a780b7af010c, f-53737f4eec39e3dd93635b68, f-54d4c93b3577da832d02c672, f-557e1c27d3c8618e6e4306e1, f-5867610d93be9cd81df52c9b, f-589276ea68a0f238e7e8eeb5, f-59cd14ab5d7c1c891c965322, f-5e00cc6a768f8929c178b221, f-623edce082867ac5d13c38de, f-68eb7039aa5c18baf6d3ef9f, f-6de6f3ecbadb5b2f739ada0c, f-737974148ca33fd95a804cb3, f-74049c556ec54b6676d90feb, f-74b8c0d13222e9704b5c11b2, f-7a6c2ea610d3d6c5e3d1ea0a, f-7c1b5dbf848ff0b587d1f90e, f-7dc1346ffbbc6944c541b079, f-7e2086e437a3b9c03a0f4a4e, f-7e3a23df7de48dba702df8dc, f-8af4783f9784af04d8df7202, f-8f85772236a04bf399432ea2, f-90c68376aa15e69e63fb9669, f-92329bb2a567dff26cfc269d, f-936b91d422efb27ba4fb9b3b, f-940913ad50bfff11289b5bfc, f-a02ee2152833ced9620a1304, f-a11785b466d17bbc85493155, f-a7a13fc1f52115b3457baa26, f-aac447ef436fc71c88e4ca6d, f-b15ae844fb1d1f34dbd84d5d, f-b335812388bd45e5658edd27, f-b508bb9767b0c481a6ee5162, f-b53acce454119840f6796a53, f-b575a25e4bcfd5de4a2be6ec, f-b964668cfce27ee298f4ec95, f-b98139c97250db7d40b7a959, f-be49745ce143e4c76cd88855, f-c2b1ab18c35b49e64e303126, f-c347c17e334c73ded496b595, f-c459f054e500819d20f97760, f-c49f7538e6ee3b809033f153, f-c508b918c5dc869d43b332a9, f-c9257f5db6a7f3bd556b16bf, f-cd9afd9e560a44d2eea712af, f-d8a1ec72980c41fcdcfb96fc, f-d93a8bbfae96c184ca64ceef, f-db046d0ed86aa796c2263969, f-db93b9d8f1089757b677b8f5, f-dcafb1968d10fb68306243d2, f-df2e7907468c26f87960f7c6, f-df9f4f8f4bb9462d5d62cb9b, f-e5752f031226688f50509d0c, f-e74225dedabed7e929714eb5, f-ef0397863827d2e3706776d1, f-ef9f58634af5e433fb404f24, f-f4ad1e2de1d1a59c1ea75ca6, f-f7140c477e332d6f8254a8e3, f-f93a903574d85ab30b93dc1d, f-fa5da829d3081cb2f260eff4, f-fb52e6bab2ea5b4811b734e4, f-fc1ba44d251a8ccb70dc63e0, f-fd3e721d8e7067e4474ecb8e

ru · official · sha256:855d11296ebd940249ab1e8b1661333550a577844c9a9d801660c4ba0496893fRU

§3. Вставка в двоичное дерево поиска Задача: добавить ключ, сохранив свойство дерева поиска. Вариант — спуск до пустого поддерева и подвешивание нового листа. Спуск ведётся как при поиске. Найденное пустое поддерево и есть место нового узла: он подвешивается туда листом. Если по пути встретился равный ключ, вставка не выполняется — по принятому соглашению §1 ключи различны. Основание: место, в которое приводит спуск, единственно, и подвешивание листа именно туда сохраняет свойство дерева поиска — все предки нового узла сравнивались с его ключом, и каждое сравнение задало нужную сторону. Крайние случаи: пустое дерево — новый узел становится корнем; равный ключ — вставка не выполняется, и это ответ описания, а не сбой. Балансировки вариант не выполняет: вставка в порядке возрастания ключей даёт вырожденное дерево высоты n. Это ограничение названо прямо и снимается §6.

Referencing norms: f-00b87586301edd6a9a2a6026, f-0557550b9802baa8c53353ef, f-062339cfdbc1c8c9416f319b, f-0b28abea945078d097b8731a, f-0bbeea8983153755a03a9916, f-0cf074cd70f60f27a8e8e55d, f-1078736395fdee3b69e06201, f-1079b9815dc04cf810b09794, f-112e84f615b2288d05ad7170, f-184be26e12b56efe2d781310, f-1f047feb5e8489e039bb01c0, f-20e51ea0cf1c71603b61c7e0, f-21b472248ec99d5660d44ab9, f-2385a7f5f93482a1ce3a82ca, f-27633cc270effe1dbd2427cb, f-28e2d47824d0ea1dcf6a37ba, f-2acacbccba5be42d6d53bbae, f-2ef7de8234139c11d73680d7, f-2f59b822b1d747fb95bab0f7, f-309977d8e5d744b2733bc95b, f-37b23b346d04286669347af2, f-391fe664a04e039342f82af5, f-3b987d387b334ad14e1814b2, f-3faca460414e427e529bc116, f-4313de1dfbf40c5637a6979d, f-436b4052a4f86df5470b0028, f-44b9c93caa64b36f1597af95, f-48c29ab341959bbf5e4b2116, f-4c7d8bb45ce7f6a70ba366d6, f-4cfe7cc6a7c0d9c5add11e72, f-4d3e6cf2583cbfd629552751, f-5169794350b8bccc56d9d80b, f-52552f961fe5aca3dd48cdd6, f-538685bbb050e974f258d15e, f-596a89e990c09572afc907e1, f-5a25cc548a9b3a36521e3def, f-604b0908fc2731780719a027, f-63f8b4b7aac97c2ecbb99fe3, f-6746e3e3ef5306d47934844a, f-707d753330dc4104e376dac3, f-74b785ac5b2a1e722012ae38, f-7a84ce496088fcd1bf1f6ee7, f-7d98544ab71d703095777543, f-7f5678538492e2e8c17f9366, f-816263b6d9e17d222efbd6d8, f-81eb5654c84eae74bde445a0, f-86722b5a72c28415f8b0b1f1, f-86eb45751d3929e138e7eba2, f-8a10d9269594f35139bcecc0, f-8ad0719904c7f467a162dd61, f-8bd5b5911e973674baff8f73, f-8c532b735730f0d085d358b7, f-931ddd26e5392425cf516b2d, f-9a5bce72b2edec399a1d8f41, f-9bdbce5e666b35d8572a5c1d, f-9d701fc1d7563abdfbbe502f, f-a1cd8522c31005dd85dd91bd, f-abef372f00cdcc5300c7dc8e, f-affcd13f38ff07c1c4cc74c2, f-b3277343653338880fdfb9ba, f-b7487123e94a4014f2e73f9f, f-b7583a5e159f4eee0ae20890, f-b9a5a4190d96530a6b273042, f-c03796713072596eea72b904, f-c5e4738da159f1f1e2a79061, f-ca0ff2844769c7bcf458f514, f-cb8f66478e595969e93279e3, f-d11d01231a69c08d501d9a6b, f-d2d98b19c087c31bba0183b0, f-d8a4b69e92db18177fa0106a, f-de1d20df68b85e55844a465c, f-de3d5995c2befd9651b283af, f-de3ef6a5e5627c5f0eb9c57d, f-dea19976368537f27a663806, f-e2394bc387c2e27b2665278e, f-e427bfea09e3b9d21860c246, f-e72b9d6a392e362a1e81df7a, f-e8f06fefb7379efa5f03ff30, f-eb0925af26fdf75fda7443b0, f-ebf77df3bd0b87d046a5d021, f-eeb19be3c032ab6fa1cf3b1d, f-f099c4b0476d0cd17dc89e3a, f-f0c582e0ec93d927b151fc4d, f-f166da2057be105cc7c08b9e, f-f1c6b10e0b0269ff3dfd8b90, f-f72871ee7b6fa7f6951ef392, f-f9c7699d8e3687fee38ef050, f-f9f509e05bd7b3a19ab92776, f-fcde7334c9463e7c38a9c5fb

ru · official · sha256:508cdd5ac4b7a5fc25b1bc0a9cbd0428dbef7d2e5490c5cd5bdf608dfd8f38f3RU

§4. Удаление из двоичного дерева поиска Задача: удалить узел с данным ключом, сохранив свойство дерева поиска. Вариант — с тремя случаями и заменой на НАИМЕНЬШИЙ узел правого поддерева. Узел ищется спуском. Дальше три случая. Узел без потомков просто отсоединяется. Узел с одним потомком заменяется этим потомком. Узел с двумя потомками заменяется наименьшим узлом своего правого поддерева, после чего этот наименьший узел удаляется из правого поддерева — а у него потомков не более одного, и случай сводится к предыдущим. Именно сведение третьего случая ко второму и есть существо операции. Замена на наибольший узел ЛЕВОГО поддерева верна равным образом; изложение фиксирует правое и говорит об этом, потому что несогласованный выбор в разных местах одного изложения приводит к ошибкам. Основание: наименьший ключ правого поддерева больше всех ключей левого поддерева и меньше всех остальных ключей правого; поставленный на место удаляемого, он сохраняет свойство дерева поиска. Крайние случаи: ключа в дереве нет — описание сообщает об этом и дерева не меняет; удаляется корень — правило то же, меняется только ссылка родителя.

Referencing norms: f-008319d2acfaab9342cb574c, f-0203d63d6cbdb6b5307025f2, f-035ebc306ba30f717cdc088a, f-0418576f92128713a137e6bd, f-051fa0f251ec4e33860dcf87, f-06f75f662521187a41a269e3, f-0803008ae627912d7019bab8, f-1011188a9930df1fc943c6d0, f-1066dd0b9ca4f75bf6634f90, f-1125e8aa3c270ebfaae6f19c, f-116431c921d063011608e290, f-1170d96d35c26d450c7cecd6, f-13214e1416c5e8a80716dd8f, f-15d3a616140546b721732af0, f-17cf009f20319452a71fcaae, f-1a97e08325d9d5b1194c0c38, f-1afc5e5e84509e4871037bb1, f-1b211b3d348e5b0d52b36d61, f-1b98137ef09213a4c92b1b83, f-1d8772a6ec6bd60ea4c9023e, f-20d0e9fd924e87b85a58fe0c, f-210e9d986fb8c41b55c9bfad, f-23842ad4ea506d3b690de2a1, f-23fe967225ae7371416d5a21, f-25f76760c0b5d37442884e8d, f-260f88e4d33babb752abf775, f-27603d348b2f4c011ff3dd50, f-29d8fa627913dbcb95789b19, f-29f3040364082b42a3afba6c, f-33457a13b72cb5429984407c, f-372675c0843ecf03c202c48b, f-3a06e97c6f2c138ecc8ba53e, f-3a3344031ecb7498c8b42d96, f-3ac64849db4a8e5de824e9f6, f-3c7beca86143d844eb1f8ceb, f-3cc04459b81dec3955d388b0, f-444c6164f9ce285374df382c, f-447f10b9fa78ebe6eb7ffc82, f-47c55ac7f0c6fade27c0308b, f-48299c94948c602458bd0fda, f-501b6993663caef1111cb0c4, f-54097b834066cd36376fef0f, f-56624de22f731796045e1ff0, f-56903c0631a9ef6566769718, f-5692e5467f811e10c00bee40, f-5b75d2b2fa219f1f71325f5f, f-5ee35669c71f892c2c1cf109, f-6497972e8eee5ecf954b9b14, f-6a37bfc6f5d2ea0c2102c196, f-6b3eab19e7fc44cff09dbe19, f-6dd66ac1b111116f80e04455, f-71a2874effb23f9af902442a, f-71a2bb6c6975bfdcdcb90e64, f-732a5c147057e633db95df8d, f-7929a306a54690bd10d61c18, f-7ab4be2769c979742c4c9acf, f-7b4766a8ca7a95b4ae1744d1, f-7e6682b6e8b3b9b4276c6287, f-84db4a52982802c140ba5c0c, f-8534e2daf6402ab89bcdbed4, f-8d4f4312be8e32d85fdb8cbd, f-90c1706079393b4526510138, f-94923d1aaf71b9773a6cc0bb, f-9518bdf092f846ceee49ae0c, f-963780a031ed3140d71bad71, f-968705e2f7ba6021b1b6d70b, f-97427bcce88b61a8640d68bd, f-98886716415d726174ceeade, f-9a6af286ba38288e1549f2d8, f-9be4dda4de5f6b09cb0dfd7e, f-9c87e2e8895702d6fe08fb61, f-9e5bc3ce102d88644e83960e, f-a40f8fc28de3f6524aa57727, f-acf907b7fc8633c71dd90524, f-af2a3662f6db3e039306686c, f-b7e2533c30876b011b98660d, f-b82a233edcee563f309c4ce6, f-bdf6784d30b42d451c87ae4b, f-c15aac4d9928e470f79dc7fb, f-c7d2eb69bd9fca60d148345d, f-c8a5825bb00f08cd4a04e71f, f-ccb5a31518e66fa9061cb286, f-cceb6c7b1d54ea1b3c44a066, f-d29f44bfae35be6b6a3cd691, f-d615ae99fcaf5136818ae555, f-d72f7b9c7442b80650e600f2, f-d759e263f259f163ae498985, f-d7ef879b4d41bf3dd9c756e5, f-d8788529faf7173b16950950, f-dcda526419ce4d94cd3c248a, f-dd7b8b34bb7f53ac0ced2694, f-df970b856c0609999172a5dd, f-e3aeb3a473f798ff39d156a8, f-e4131d66ad9e61c77d89e5eb, f-e983a525e8be7c17979fdfc3, f-ef79d8242f8c4a65f5c3df57, f-f114132a1e957bf1feae3913, f-f4de2ab66dea84212b849b9d, f-f5378a6fd84a190b664547d0, f-f545b389c48c95ee7ca9ea85, f-f7434586f7ef2980c4ec8470, f-f7919be31a86ab6a51a1e341, f-f9b21baa65881d92412b7c3a, f-fcf9bc820d0afc8451a60f9a

ru · official · sha256:83b2c9410c033af6dcfdf9c85d7148a79438aa669b5ba26bf4cbb19fc36cca20RU

§5. Поворот AVL-дерева Задача: локально перестроить узел и его потомка, сохранив свойство дерева поиска и уменьшив высоту перекошенного поддерева. Вариант — малый поворот, из которого композицией строится большой. Малый правый поворот вокруг узла x с левым потомком y: y становится корнем поддерева, x становится правым потомком y, а прежнее правое поддерево y становится левым поддеревом x. Малый левый поворот зеркален. Основание сохранения свойства дерева поиска: порядок обхода в симметричном порядке не меняется. Это утверждение и есть содержание поворота: перестроение переставляет узлы, но не переставляет ключи в симметричном порядке. Большой поворот есть композиция двух малых в разные стороны и применяется, когда излом направлен внутрь: левый потомок перекошен вправо либо правый — влево. Один малый поворот в таком случае перекос не снимает, и это единственная причина существования большого поворота. Высоты обновляются снизу вверх: сначала у узла, ставшего потомком, затем у нового корня поддерева. Обратный порядок даёт неверные высоты, и эта ошибка не видна на малых примерах. Оценка: постоянное число ссылок и два обновления высоты. Поворот сам по себе стоит постоянного времени и не зависит от размера поддеревьев.

Referencing norms: f-01eb62068063161cbae2a774, f-0233e692425a9fe21fbbddfc, f-04beac3c51e8e408f14b9883, f-1a0092a1bf7d513125e68d15, f-1b99f879d1c11fa6d37026b7, f-21a8f22c93e4ec8ff5f8b9cb, f-23a2acb8cb5cf4a48fc0adf6, f-23ff113069298c4ffadd5b69, f-25058bee27891a8c881351b5, f-257d6a6b649a91ac2db1dd9b, f-2ab2d48e4d4eae7eb841a6fc, f-2c275b230b114732d5ca4966, f-2d12ed4408c087dcad4e05d9, f-2de4e6bd6dcc9a9cfcb9747a, f-2f8571ee63a07d3ba52d2d98, f-35aff4cf9934e8279e2dca80, f-35e06731d1cc586ea2edbab4, f-3691e616e702d0ce89ff0e2f, f-36d640820b58c04b7272caf9, f-3bb7a4d26b122313ebe7b6c3, f-3df893f5a576e14e58136523, f-413ade9b47f7cd475e938efd, f-4293d18866022212e6e18e56, f-48b1aaf4775003fc075b2f99, f-4f1d623f9bb9323a250108f4, f-50880da96fab548a689f9d91, f-51da10ec79ab089aa0b647c5, f-53fd9a8dd1c2a4bec2ae326c, f-5f3206d69aeef7ae503c8c3f, f-5f5748aa510802be28ee59ef, f-6858d95c1e58185ceafc1d34, f-6aa2c6545086a758eb3b2c87, f-6d56b78b737b832a83d3971e, f-7492e9d08ce53a675c18f270, f-78a5d8432e832e21d9d649bc, f-7b9800515b1cab2d35ae53da, f-7d94cd1d0883a0daeb45b3b4, f-7e323c58707258b6491f5f82, f-7f91d727fcb2d35c5ac76659, f-89c87f72063b6e66c52b3f1f, f-8cb3ad960fe703401c94d26a, f-8f017215c12f2fe4f2ad45fe, f-8fb6b70bfae3b621355c285c, f-9134645864be4c03edbf8df0, f-918747baa8c56c25b2ad35d3, f-9429497276993405c65e0baa, f-95be4672f5aa9ba9d370c6e5, f-99185fa69c60d58658d4dceb, f-99a60b6703cb85d5c9fd77fb, f-9eca00c00b833044ddc48863, f-9febd15ff2f9430ba61db2aa, f-a2262b7af6461f766f0bb235, f-a6da3832f00520ac4df57531, f-a78b42773024f3ac4cde3690, f-a80ca1649786018a85bffe31, f-ae5baafe52255dc934e35908, f-b3ec2c5d4846fbd421fabec4, f-b3f02bac352edc3098aa9110, f-b4e2e5ededff48d1ecbc8d3d, f-b6ab0a0d488eeee156cd9132, f-b6f921cb53538f05ccb2316e, f-b7c93903717e9a413608a48d, f-b91a101140c5ee185b3bab46, f-bac707817b397f9ca1255439, f-bd74b9bf30a7d4ad458ee449, f-bf9dbf9a77cbe8d4fcd34bed, f-cd6f05b60d3eb21eef67d38e, f-ced35df692e500025fb9878c, f-d159b61a0d49037018d912ae, f-d3174c3a3f5e9d31d76a6ca2, f-d81f3adfc7bcf5c98f295602, f-dad204591a62e099d0737087, f-e144cf80ec543106e024be01, f-e52baf9e4b789378b8c9628d, f-e573bbd8e1146f2dc7087576, f-e78c28c1cbf92fd0e6e9a9df, f-e78ce4178cf0a6b1c059fc7f, f-e96caaf6bc95794e2a6b1d0c, f-eaa4660bdd68840a7a47deb9, f-ec658d290d6f65f7f4ef378b, f-f3dcd73ab4792040aa3ab703, f-f3f3bda7567a80012266d458, f-f3ff423e709fe344fe9f93aa, f-f4dcd8b1b46c05e85c8c0eea, f-f816254e6f2b1dc38fa4cd84, f-fba0f2e0b64b05ee346be347

ru · official · sha256:dde5aec8acb0ecd936a65d0b57d517a01db5ec23a06f6534de95f06ca96dd4b5RU

§6. Поддержание баланса AVL-дерева Задача: после вставки либо удаления восстановить AVL-свойство §1 на пути от изменённого места к корню. Вариант — подъём по пути с пересчётом высот и поворотом при разности высот, равной двум по модулю. Идя от места изменения к корню, для каждого узла пересчитывается высота и вычисляется разность высот поддеревьев. Если разность равна двум по модулю, выполняется поворот: малый, если излом наружу, большой, если внутрь. Направление определяется знаком разности у узла и у его перекошенного потомка. После вставки достаточно ОДНОГО поворота: он восстанавливает прежнюю высоту поддерева, и выше по пути ничего не меняется. После удаления одного поворота может не хватить, и подъём обязан продолжаться до корня. Это различие вставки и удаления — самое частое умолчание изложений, и оно названо здесь прямо. Инвариант подъёма: все узлы ниже текущего сбалансированы и их высоты верны. Оценка: длина пути к корню есть высота дерева, то есть логарифм числа узлов; каждый шаг стоит постоянного времени. Итого логарифм на операцию.

Referencing norms: f-01b162fe05e85b77b5e9569f, f-021748e9cce18793e5ac6a6b, f-07e96ce9a360331aa574c566, f-0fd09a23af7246bac4b4706e, f-10cd56a73ab099ad18f4e5df, f-13ac5ac581fef695633dfc44, f-1cd692a7de3a24be0dea3675, f-1df24f69e057a619cbd98791, f-1e3dbb0f168d9d4e79f88cf0, f-20258bed7c117e0b7c33cf98, f-2123620a61764369f2e59abe, f-24f74ecdf469f5fa8157db6e, f-26e342d867257b2eda6df95a, f-2cf13c6e69765076683dc1ec, f-2d8e5fca2cb519e33b2fc6d1, f-2f67f3e76af769a54018213d, f-328e506066f9787901ea6389, f-3508b7001dd3fc3a1cd36ce6, f-38989cca9bed9080c3efc111, f-3a03a2b8dbfd62ecc917df54, f-3ac2291147c1d46be7930764, f-3bb5c79213521a13bd9bf66e, f-3bd26705e7f93d44672d1c3b, f-426da08fb571acc57885ce90, f-42ca495881d87f43bf312155, f-464b5d030c6f35b1cde7b4ac, f-46a9a03ddf1c03f8ef12c507, f-4b196e5fa31a3bb8103aeb0d, f-4b29b7d2b95151ebeb226f60, f-4e23c149a050d9f49c722c33, f-50a16098ec3303ba9e8cf621, f-51689dc30f1b18a597e04888, f-55dd1cff104b886a2dc91f16, f-56821f776468a7b27ad94e53, f-5729598c770d199506641246, f-5820e661e13ba795e09c029b, f-5a6cd29afb08401466abdb7e, f-5b03526660fae54dd80bd4ce, f-5b65ebf85718bba2cc06fbef, f-60ae3f4ea32f3937b6665959, f-63c4fac22319f9c26786aa2d, f-6455a4295d4604463b00435e, f-67bb84c655e7ca3a9ef803b0, f-6e53148c8797c98a985cb523, f-7056b108468762850cb24ac0, f-7250ecd8937c05859cd3dcb3, f-75709529d73d76065c0cd849, f-78ed80e1f6d3030807372ad0, f-7eb455bc1629133034cf267d, f-809cc4fb0c31a90d7c14730a, f-80c2ef5e14c75c29a2efd8d3, f-8bfaaa80e08a2c726f5df7e4, f-9298a1028941c5b14eda137f, f-96b4a3637d0e9e1622e7ef9e, f-9726a496538f5e8bbf42e858, f-a2ef56219f51e0a89c8be9dc, f-a39d3861498bd924bcabbacf, f-a467f5dad5058a005b749a96, f-a54f25d68e23647badd636db, f-a62b90d406c40b7908d93379, f-a730432e5fe51fb80927c4e8, f-a99cd2fb8a36397885b2955f, f-ac3b04f8e5b1eabacba4d7cf, f-b37f97a7bd058d1eb2e5ef5c, f-b478a263db9b03987f6a9bbb, f-b5c95eeb895a019d1419e1f0, f-b67ee5d9c62bc77abd930643, f-bf86f17b340cfffa0c93fcba, f-cac84188941bda3ef39140df, f-ccf7b2bc72331b7751c9c343, f-cd9e815f93080b430104a51d, f-ce1780a19bd3e8f74fd2426f, f-ceffd706da2691da23210f44, f-d004b54077d69f04b4b06d9e, f-d0bf9a36dca59f6611419e67, f-d284473ad9268872ea1808c0, f-dedcbe9263773171a832c6b3, f-e06a9411432303a235cb3315, f-e13c9123662eff7567aabf24, f-e3697d36367495cb2c71d666, f-e52adce2d1de9f8a87cc7e52, f-e5892d8accf55c1076eda0b4, f-e6c149b664480638aa31af0f, f-e758fc27d702a2a00439ad9d, f-eea41ee92720e9a5c9c4dd0f, f-f350123e863cd83ba666f839, f-f3d476c96948df26f52b9fce, f-f94d731d35711fcc6ddc2e57, f-f9b1b0d3d89393b9e5e6f17a, f-fe47aac1a5a2ad08f58e7abc, f-ffaa3706e0e4c4fd87a2d8d5

ru · official · sha256:0ec4dc0cb0b0c869254860ec6ad78bf89fe15bd6b0c89326ee59c07f8cea20e4RU

§7. Поиск в B-дереве Задача: по B-дереву и ключу найти узел и позицию ключа либо установить его отсутствие. Вариант — спуск с двоичным поиском по ключам внутри узла. В узле ключи упорядочены; двоичным поиском находится первая позиция с ключом, не меньшим искомого. При равенстве ключ найден. Иначе спуск идёт в потомка по найденной позиции; отсутствие потомка, то есть лист, означает отсутствие ключа. Основание — упорядоченность ключей в узле и то, что потомок по позиции i содержит ключи между ключами i − 1 и i. Это и есть обобщение свойства дерева поиска на узел с многими ключами. Оценка: высота B-дерева порядка логарифма числа ключей по основанию t, а внутри узла — логарифм от t. Смысл структуры в том, что высота мала, и потому мало ОБРАЩЕНИЙ К ВНЕШНЕЙ ПАМЯТИ; модель стоимости здесь считает не сравнения, а именно чтения узлов, и это надо называть.

Referencing norms: f-01fe462f836d3ed54bff717b, f-045f1fac36a1f77d385499e5, f-08629afa3a83521dd910aaa4, f-087c691b0e2499806597e2b6, f-09e7af72c836e39081fcb2fb, f-0c56146f5e21f951f573a2e0, f-12dcf63c76df6464ec6a52ae, f-1418e79d9cbb2c13d35efb1d, f-158ccff3ad6bc5c36d1ffa2b, f-1aac913562b6cb905b94a5af, f-22fdd04cd2ed0f011351ed86, f-239d9c9f368855b30f3355ae, f-23e97a2cb586491f24c8b296, f-25df29cde5810faf2acbbac0, f-2601a9b9fd85176482a3ae72, f-2696f1b9196eeb58ba81555a, f-2987b85b26a9b881a2f63785, f-2a214325528f9ca1ecb832eb, f-2a4426b6dfa682c5d49bf807, f-30662a04662ff518e18acc56, f-3156fec5cd45043c6a15cf89, f-37569b988638e601c10bf712, f-3c76f22a3b76f7cc1bcb5691, f-40662cdbb87a289d35e05fc4, f-42b9e015ae3fd4c07fe38c3f, f-43bfa218149880de10880094, f-44a5feae8c5b00ece8602bc9, f-4534383d4b2aa495dea5cff1, f-48783e01bc8b9d91d2e9a85f, f-4d7f58adc42460ebbe938c19, f-4e1f2d31bbff565f833f76de, f-4e5f3ac63c17794b9b780b6b, f-552a22681536928dde60b0c9, f-55c93f86cb9eadf5272258e4, f-58885431018bdadd782bab7b, f-5cfa208193b24faae8c0820f, f-5db0ea4f169360913859577d, f-605d725f2081d69a729d6b3a, f-60b089ecd79e96e04bd425a7, f-616f07e5a6b893d8b4fba340, f-63242676863d25ca908f90ab, f-6727d1b92b51507ad1ecee88, f-690536c1e4f99452dfcf43dc, f-6a5db520abe52a5f35e76be4, f-6f6ed0aa534ad97b8a13f8af, f-6fe1d2bf67dd849425b660e4, f-70fefd6d0143355591388539, f-722dd97d5685116a6b8a506f, f-775604a5473ed4aec0665ab4, f-7ed2cf534a2e484f024d638b, f-7f990cc30444d9e2cc3236a1, f-80925bb0343f6a2cfdc577b2, f-81b5d7418792d43717ac38d8, f-859dd2f1b08639cead3eb318, f-8a2e66dbe9986e05c063b6dc, f-8c8687c323278c7f378187b0, f-92c940d4b467a188a04eee1b, f-9a1debfc5cf5d5698ffef68c, f-9ca33a80163e67c741f73d9e, f-9efd37dfe89807372a5d57ea, f-a2498c77733fea048c5d49cf, f-a99e0574f4432d648c122502, f-b5a7caa44b1513598339bc30, f-b68eec88a42f266047f65daf, f-b99b46fb14fd30863164c26c, f-c478521e333cf17ef2b4b6e6, f-c80cfd266a896f27cdda6cd5, f-ce4136aeb50f7c9f2937f236, f-cf816d761bad4fb07d6abda9, f-d0c73d34a20b0d50c054486e, f-d18396078bd243461420cd68, f-d1ee9b0ea1613b78cf82fbf4, f-d7deaf0ba9622f9b69b6824a, f-d82f113b85979c5f04156e25, f-dd7e43080e443bf7d803d039, f-ddd10899923ad8a9ffdb7570, f-df2dfe6b81e093c93bd6f5d6, f-df3df2ba7bd6bc9ffe2f910e, f-ee495f370995d9e4955a5d1d, f-f14714b0d3fa23bc7799f9a2, f-f42ac31b3f0e69c072e87148, f-fe4daa61bed0bc9d59516630

ru · official · sha256:fb962cd9f574851488603aad5ef57bab7cb7330dafb78c0286c91be66f22aaf0RU

§8. Вставка в B-дерево Задача: добавить ключ, сохранив свойства B-дерева §1. Вариант — с предупредительным разбиением полных узлов при спуске. Если корень полон, он разбивается, и дерево растёт вверх на один уровень — новый корень получает один ключ. Далее спуск: перед переходом в потомка, если тот полон, он разбивается, средний его ключ поднимается в родителя, и спуск продолжается в нужную половину. Достигнув листа, ключ вставляется в него на своё место. Предупредительное разбиение выбрано изложением ради ОДНОГО прохода: при нём родитель заведомо не полон, и поднятие ключа всегда возможно. Вариант с разбиением на обратном пути тоже верен и требует возврата; смешивать их нельзя. Рост дерева ВВЕРХ и есть то, что сохраняет одинаковую глубину листьев §1. Дерево, растущее вниз, это свойство теряет. Инвариант спуска: текущий узел не полон, поэтому вставка ключа из разбиения потомка в него возможна. Оценка: одно чтение и не более одной записи на уровень, то есть порядка логарифма по основанию t обращений к узлам.

Referencing norms: f-00c149d2c8111aa62cff4950, f-00cd95ff88d9039871932ab6, f-02df32aaf66d360a1d80ea3b, f-06f8041e6c877a55fdc5f258, f-0e9574d2378465de950badb3, f-0f933fc06d193bfe62eb360b, f-1806c653d658ccc4b15303ec, f-1cd808222e9d78958898daff, f-234cb5f3c7e59d7f39f0cf75, f-2451f25bb4ab2bb6306c8887, f-254116444c20ca9fbf334552, f-2799eda769136f7d53f587ab, f-2a9e86b2face3d6f96540b61, f-2acca8ddfc6c461a0ad2f9df, f-2d0be37998a8b671f3b256db, f-2d264510226bd5be44075c98, f-2ea5c312a9e0e53c34d55270, f-37fdd30b679527435f20a9cc, f-3bd31589e0583998bed5610d, f-3c226ce95582d0866037da8c, f-3d18b2b38e07a882282a27ce, f-3e2feb4757a0bcaec04acb71, f-3f36d571981452fc9f947e82, f-3fce50618263734f365c8c50, f-4641a1939dab322a043e05ed, f-47026a2368cba2437cb04699, f-479f63a19cb827cc8b3900f1, f-48633c81208a1644c8489885, f-4d2cd162d910e43aecf94402, f-4dd1d2bafa15ddcb1fa1eb42, f-4fe4c38a8003184367edec60, f-5322c918920be6a2f98deaa0, f-563486a1b1ee93e0e53bf8b4, f-5a94ba94731f43b44b1ac8c9, f-5b33f4d605782cc4907842e9, f-5c9083d706a99c047f154448, f-5cd16b10e988a80950866194, f-608506b88892ac3335fdd4d7, f-60bba1345d3cb8b78af41553, f-622014edf270e9b20da0b007, f-622da819d38775342b966f1a, f-68501ea8e120ec04cb64b6f3, f-6f27def5bfc4a1d34ea4bbd2, f-6f36f892fc491f31f8484b5e, f-72d0484dbd8e14deb26c9d7d, f-75a655f2a9c42d2bbfa92cb9, f-77fe9cdf613d80b347a6f2cb, f-7b4e8aa964c24618b64738e7, f-7fce9125a1889f22a2fc228d, f-81a5791ace98e9f621abc8ea, f-84459d08087d88e1b09c4b4b, f-8dd64f205b24390057586012, f-9044cbe0b9a79532daa88b79, f-9208c09c61b11232cc714623, f-93bcec5a0d28c99c8f7ceb69, f-94a862d7daef768473838b44, f-96e8361f0ac7cad1245215f8, f-9701b4b505ad60bdb6febb99, f-98f4fb814db1db5df6624d51, f-99a4f08ae5440880b5879d41, f-99bc194fbd072c1d4cb769f9, f-9bc28d593941c580f5ad4b28, f-9bf059fc1eb9c70c1d1d614e, f-9c88417bc2e217abd4abb760, f-9e7a577be871efb33d2481cb, f-a0536e34b98eb4fc25c72417, f-a4a2efae360b5c63dc652623, f-a4efd9e2895c0dc706058804, f-a52d9e4e6e36391f93bfbed4, f-aa68abab203d59b69e8459d2, f-ab4f19855c528ecf9b087d65, f-ac1758eb97c06e1c04938174, f-add0320df9b6c68c62ca20ac, f-af102726e5b4113281777b77, f-b2d00cb2ab22895897cbee7b, f-c2e21531fd0056dfb6e3c436, f-c372a987474201f30a2229b6, f-c3cc26461a46b9f53be2ad76, f-c41e5dafe1d084b2090db679, f-cc0e7035a6a441ffd1cc423d, f-cda2423fc6384cb6ef5e542c, f-ce5d3951df8879586f0d9078, f-cf9fd3869be87b0ca48c5516, f-d0a9bb7247e9c4703752d06c, f-d2ffbb49d5295c7e0d0b2728, f-d469181d8d733f04e258c40f, f-d5bdc77d6c24c9577335a875, f-dd7688f49b6b077ae351d338, f-de85a48a6dd382b71d03cec1, f-e2149fe6cdde52f79d640aea, f-e235ce5f42a5a0c650be6914, f-e29556ec042fed539c0ea65a, f-e41950e2a9351d347f3b9908, f-e6efd4b8ae9afec4421936e0, f-eb0ec3f09e450a8fe638d01b, f-ee453d96e9e299ce198eb573, f-ee751c2ad038ca4b6fc74c6f, f-f214a6436dd3fe9915291c4c, f-f55344636c5c939c67428002, f-f6236ab8ff69f510be53a08b, f-f9a9d2113bb50c3b7b38bbc0

ru · official · sha256:b777fb6f8294587044d44ecd0a1cdd5dcdd06184b7e63fa51d6edf9eaf0efb23RU

§9. Удаление из B-дерева Задача: удалить ключ, сохранив свойства B-дерева §1. Вариант — с предупредительным пополнением узлов при спуске до минимально допустимого размера. Перед переходом в потомка, содержащего ровно t − 1 ключ, он пополняется: либо заимствованием ключа у соседа через родителя, либо слиянием с соседом и ключом-разделителем из родителя. Только после этого спуск продолжается. Удаление из листа выполняется прямо. Удаление из внутреннего узла сводится к удалению предшественника либо преемника: ключ заменяется наибольшим ключом левого поддерева либо наименьшим правого, и удаляется уже он. Слияние может опустошить корень; тогда единственный его потомок становится корнем, и дерево УМЕНЬШАЕТСЯ на уровень. Это второй случай, в котором меняется высота, и он обязан быть назван. Предупредительное пополнение играет ту же роль, что предупредительное разбиение при вставке: оно даёт один проход сверху вниз. Инвариант спуска: текущий узел содержит больше минимума ключей, поэтому удаление из него не нарушит нижней границы. Оценка: та же, что у вставки, — порядка логарифма по основанию t обращений к узлам, с постоянным числом операций на уровень.

Referencing norms: f-040fd487ef9b8fdd7a417e7b, f-063a0b8cae90b6c913302921, f-0940652c26a029f39cd521de, f-0c93d5dfb3ace9508c3dc2f4, f-1240b0fadda965ab7f3e8dd7, f-13be3a8e1a4a596a888286fe, f-1a8769ba0f5faf7e87484169, f-1b4178898060b8d2383331f6, f-1c6f003dbba293e31ec3c6ce, f-1fe91ee3bffef539b21f59b5, f-21901c1040fd5f9d4d4aa0f4, f-28b42eb7cb90bae15648def0, f-294e675ca7f0d2880435e1b0, f-2f2c50aab5a7c49959392f7b, f-3035805d54522d0979ea4716, f-3054c4cfee51badbf2872f79, f-342829ee1efd713f4a0ef1c3, f-34f0ace034188fe9b5fc894f, f-39125e7395f51a664a286260, f-4093f5c967cab50a7b3672b6, f-4238411ae0e43850db4b8200, f-443e4e903bdb9f032e60ea1e, f-4852d4acb66a373778163c65, f-48655874d28ec809c1ece950, f-4866c576e772dec653c176da, f-4c7ee95f680e0ac99b027bd4, f-4cfdf20f5936bbe8bb0aac2a, f-53141e971c260bdfc5cbe3e8, f-54c756ca47621a9eb021d2da, f-5763a1174245ef30d5a5ebfe, f-5aa4f23e87543097199ec3c0, f-611fdebca82760c7ded8ecbe, f-6195ebb459a38e1666e3c3bb, f-632b7f3b4744c19124e1aa9d, f-639ff709f9a8f4b165f4f4bd, f-63b102e9458bd10ccbd9a723, f-643ca368d9446be85b314fe6, f-660e198ca884ecf86c26bbb3, f-693a918d082ce8fdc7a17516, f-6b07ad7c0615fb5a37c6bbdb, f-6c76797a3f911310785fa28e, f-7183bf0b9c6da669574e1d0a, f-71a710eaf7f18c0a63324d6f, f-77394f4c9e0c5015b90a107e, f-7927dbcbc45004aa745bcca2, f-7a56b1c2f5eb00b85837f195, f-7bb52cd8d7d1fa1ac0c45812, f-7be74708a01b2acfe271bf03, f-7d37185286fe0905d2718554, f-7e86c15e0375f327d8cba582, f-80395291a99e3996c66b02b7, f-82411df12c2fa3ba3d888555, f-8c7dc167843718c2db827f16, f-8d2bed75c584e384ad1340e7, f-911bfaec7bf12494d101de39, f-915c8be5c056ebe3cd2eb845, f-91e294d818041fada1bea0c6, f-99af2f7633e3d005e63924d4, f-9d5955c4bd6ed0626d697f27, f-a7dae291d547de437f41884f, f-ac1ea3f1e523aef4ad2f2b4b, f-aec8c49a4141585f604293d9, f-b31f008c6a685c4aa33cde36, f-b3793d9003b77bb172a7b3b6, f-b556ed53c75cd7848dac9a68, f-b93c828fff5eca22354dd2e0, f-bee9d09a422d942f4c873981, f-bf08b89afbe868881a40f87a, f-bfadf195aa34da958bc53367, f-bfc1e5ff3df12a64ac326fb0, f-c6a0d3a3c27e059ecaed7202, f-c9050d74ff6907228bbdab9c, f-cb5077ba699b712c388d0b75, f-cc7ec4f8cdd44a3f6dee5aa7, f-cd9cb128e1721d50345a2065, f-d3bab94ed13fa63912ce235c, f-d476d9e33c1643261ee4f41b, f-d563873af3f1db3514e141e4, f-d58bc5c89e3449befc5930e1, f-d8750bb81833fdd631e5d4d8, f-d9c86daf65523505d4d38015, f-db68c0219c067757f7ed7ccc, f-dba682af4574335870545075, f-de34c0060327f654a2099dfd, f-eab1b43471066a725ff76a16, f-ed986ad00596a65cc3709b6a, f-f1c05220042400c5265398e8, f-f23f074f70c82984c6bc763c, f-f29a95e1508afd44d0a3c713, f-f3c5483a5486f6b7a99feb0c, f-f42d21ecf64a30bd2ba002c1, f-f5f6e8cb789a4d5ab4f069fb, f-f7a657db5a3e1bed4dc4f089, f-fb5d6ca65f2f20c31d89da2a, f-fcd7b3f6b6e4f7af012e8f27, f-fd31279b221ad79731cf2ab7, f-fda1bf964d84c8d8582ab2ca, f-fe1eb7df935ca8fd8ccc03ac, f-ff62c57bad8c1359af65b43f

ru · official · sha256:0a0e5646b0dc25452d52ecfc34d769c4f90d35f2789320d3c6714c179057837cRU

ОПЕРАЦИИ НАД ДЕРЕВЬЯМИ: ДВОИЧНОЕ ДЕРЕВО ПОИСКА, AVL, B-ДЕРЕВО И ДЕРЕВО ОТРЕЗКОВ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство одиннадцати операций над четырьмя видами деревьев: поиска, вставки и удаления в двоичном дереве поиска; поворота и поддержания баланса AVL-дерева; поиска, вставки и удаления в B-дереве; построения дерева отрезков, точечного обновления и запроса на диапазоне. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве операции и не выполняет её: ни одно дерево здесь не изменяется.