Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[86]

Рис. 13.6 Цифровое дерево хранит строки 1011, 10, 011, 100 и 0. Каждой вершине соответствует ключ - строка, которую можно прочесть, идя из корня в эту вершину, поэтому эти ключи не надо хранить специально (на рисунке они показаны для наглядности). Тёмные вершины не соответствуют ключам, а являются промежуточными для других вершин.


14

Красно-чёрные деревья

В главе 13 мы показали, что основные операции с двоичным деревом поиска высоты h могут быть выполнены за 0(h) действий. Деревья эффективны, если их высота мала - но малая высота не гарантируется, и в худшем случае деревья не более эффективны, чем списки. Красно-чёрные деревья - один из типов «сбалансированных» деревьев поиска, в которых предусмотрены операции балансировки, гарантирующие, что высота дерева не превзойдёт O(lgn).

14.1. Свойства красно-чёрных деревьев

Красно-чёрное дерево (red-black tree) - это двоичное дерево поиска, вершины которого разделены на красные (red) и чёрные (black). Таким образом, каждая вершина хранит один дополнительный бит - её цвет.

При этом должны выполняться определённые требования, которые гарантируют, что глубины любых двух листьев отличаются не более чем в два раза, поэтому дерево можно назвать сбалансированным (balanced).

Каждая вершина красно-чёрного дерева имеет поля color (цвет), key (ключ), left (левый ребёнок), right (правый ребёнок) и р (родитель). Если у вершины отсутствует ребёнок или родитель, соответствующее поле содержит nil. Для удобства мы будем считать, что значения nil, хранящиеся в полях left и right, являются ссылками на дополнительные (фиктивные) листья дерева. В таком пополненном дереве каждая старая вершина (содержащая ключ) имеет двух детей.

Двоичное дерево поиска называется красно-чёрным деревом, если оно обладает следующими свойствами (будем называть их RB-свойствами, по-английски red-black properties):

1.Каждая вершина - либо красная, либо чёрная.

2.Каждый лист (nil) - чёрный.


Рис. 14.1 Красно-чёрное дерево. Чёрные вершины показаны как тёмные, красные - как серые. Каждая вершина либо красная, либо черная. Все nil-листья чёрные. Дети красной вершины - чёрные. Для каждой вершины все пути от неё вниз к листьям содержит одинаковое количество чёрных вершин. Около каждой вершины (кроме листьев) записана её чёрная высота. Чёрная высота листьев равна 0.

3.Если вершина красная, оба её ребёнка чёрные.

4.Все пути, идущие вниз от корня к листьям, содержат одинаковое количество чёрных вершин.

Пример красно-чёрного дерева показан на рисунке 14.1.

Рассмотрим произвольную вершину х красно-чёрного дерева и пути, ведущие вниз от неё к листьям. Все они содержат одно и то же число чёрных вершин (добавим к ним путь из корня в х и применим свойство 4). Число чёрных вершин в любом из них (саму вершину х мы не считаем) будем называть чёрной высотой (black-height) вершины х и обозначать ЬЬ(ж). Чёрной высотой дерева будем считать чёрную высоту его корня.

Следующая лемма показывает, что красно-чёрные деревья хороши как деревья поиска.

Лемма 14.1. Красно-чёрное дерево с п внутренними вершинами (т.е. не считая ть-листъев) имеет высоту не больше 21g(ra+l).

Доказательство. Сначала покажем, что поддерево с корнем в х содержит по меньшей мере 2hh(x) - 1 внутренних вершин. Доказательство проведём индукцией от листьев к корню. Для листьев чёрная высота равна 0, и поддерево в самом деле содержит не менее 2ЪНХ) - 1 = 2° - 1 = 0 внутренних вершин. Пусть теперь вершина х не является листом и имеет чёрную высоту к. Тогда оба её ребёнка имеют чёрную высоту не меньше к - 1 (красный ребёнок будет иметь высоту к, чёрный - к - 1). По предположению индукции левое и правое поддеревья вершины х содержат не менее 2fc 1 - 1 вершин, и потому поддерево с корнем в х содержит по меньшей мере 2fc 1 - 1 + 2fc 1 - 1+1 = 2fc - 1 внутренних вершин.

Чтобы завершить доказательство леммы, обозначим высоту дерева через h. Согласно свойству 3, по меньшей мере половину всех



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]