Двоичные деревья поиска

 7       nodeTemp = node.nodeParent.right;

 8       If (nodeTemp.color == RED) Then

 9       Begin

10         nodeTemp.color = BLACK;

11         nodeTemp.nodeParent.color = RED;

12         RBTLeftRotate(Tree,node.nodeParent);

13         nodeTemp = node.nodeParent.right;

14       End

15       If (nodeTemp.left.color == BLACK) and (nodeTemp.right.color == BLACK) Then

16       Begin

17         nodeTemp.color = RED;

18         nodeTemp = nodeTemp.nodeParent;

19       End

20       Else

21       Begin

22         If (nodeTemp.right.color == BLACK) Then

23         Begin

24           nodeTemp.left.color = BLACK;

25           nodeTemp.color = RED;

26           RBTRightRotate(Tree,nodeTemp)

27           nodeTemp = node.nodeParent.right;

28         End

29         nodeTemp.color = node.nodeParent.color;

30         node.color.nodeParent = BLACK;

31         nodeTemp.right.color = BLACK;

32         RBTLeftRotate(Tree,node.nodeParent);

33         node = Tree.root;

34       End

35     End

36     Else

37     Begin

38       nodeTemp = node.nodeParent.left;

39       If (nodeTemp.color == RED) Then

40       Begin

41         nodeTemp.color = BLACK;

42         nodeTemp.nodeParent.color = RED;

43         RBTRightRotate(Tree,node.nodeParent);

44         nodeTemp = node.nodeParent.left;

45       End

46       If (nodeTemp.right.color == BLACK) and (nodeTemp.left.color == BLACK) Then

47       Begin

48         nodeTemp.color = RED;

49         nodeTemp = nodeTemp.nodeParent;

50       End

51       Else

52       Begin

53         If (nodeTemp.left.color == BLACK) Then

54         Begin

55           nodeTemp.right.color = BLACK;

56           nodeTemp.color = RED;

57           RBTLeftRotate(Tree,nodeTemp)

58           nodeTemp = node.nodeParent.left;

59         End

60         nodeTemp.color = node.nodeParent.color;

61         node.color.nodeParent = BLACK;

62         nodeTemp.left.color = BLACK;

63         RBTRightRotate(Tree,node.nodeParent);

64         node = Tree.root;

65       End

66     End

67   End

68   node.color = BLACK;

69 End

Процедура RBTDeleteFixUp применяется к дереву, которое обладает свойствами КЧД, если учесть дополнительную единицу черноты в вершине node (она теперь дважды чёрная, это чисто логическое понятие, и оно нигде фактически не сохраняется и логического типа для хранения цвета вам всегда будет достаточно) и превращает его в настоящее КЧД.

Что такое дважды чёрная вершина? Это определение может запутать. Формально вершина называется дважды чёрной, дабы отразить тот факт, что при подсчёте чёрных вершин на пути от корня до листа эта вершина считается за две черных. Если чёрная вершина была удалена, её черноту так просто выкидывать нельзя. Она на счету. Поэтому временно черноту удалённой вершины передали вершине node. В задачу процедуры RBTDeleteFixUp входит распределение этой лишней черноты. Они или будет передана красной вершине (и та станет чёрной) или после перестановок других чёрных вершин (дабы изменить их количество на пути от корня к листьям) будет просто выкинута.

В цикле (строки 3-67) дерево изменяется, и значение переменной node тоже изменяется, но сформулированное свойство остаётся верным. Цикл завершается, если:

node указывает на красную вершину, тогда мы красим её в чёрный цвет (строка 68).

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

Могло оказаться, что внутри тела цикла удается выполнить несколько вращений и перекрасить несколько вершин, так что дважды чёрная вершина исчезает. В этом случае присваивание node = Tree.root (строки 33 и 64) позволяет выйти из цикла.

Внутри цикла node указывает на дважды чёрную вершину, а nodeTemp – на её брата (другую вершину с тем же родителем). Поскольку вершина node дважды чёрная, nodeTemp не может быть NIL, поскольку в этом случае вдоль одного пути от node.nodeParent было бы больше чёрных вершин, чем вдоль другого. Четыре возможных случая показаны на рисунке ниже. Зелёным и синим, помечены вершины, цвет которых не играет роли, то есть может быть как черным, так и красным, но сохраняется в процессе преобразований.

Двоичные деревья поиска 

Рисунок 8

Убедитесь, что преобразования не нарушают свойство 4 КЧД (помните, что вершина node считается за две чёрные, и что в поддеревьях a - f изначально не равное количество чёрных вершин).

Случай 1 (строки 9-14 и 40-45) имеет место, когда вершина nodeTemp красная (в этом случае node.nodeParent чёрная). Так как оба потомка вершины nodeTemp чёрные мы можем поменять цвета nodeTemp и node.nodeParent и произвести левое вращение вокруг node.nodeParent не нарушая свойств КЧД. Вершина node остается дважды чёрной, а её новый брат – чёрным, так что мы свели дело к одному из случаев 2-4.

Случай 2 (строки 16-19 и 47-50). Вершина nodeTemp – чёрная, и оба её потомка тоже чёрные. В этом случае мы можем снять лишнюю чёрноту с node (теперь она единожды чёрная), перекрасить nodeTemp, сделав ёё красной (оба её потомка чёрные, так что это допустимо) и добавить черноту родителю node. Заметим, что если мы попали в случай 2 из случая 1, то вершина node.nodeParent – красная. Сделав её чёрной (добавление чёрного к красной вершине делает её чёрной), мы завершим цикл.

Случай 3 (строки 23 – 28 и 53 - 59) Вершина nodeTemp чёрная, её левый потомок красный, а правый чёрный. Мы можем поменять цвета nodeTemp и её левого потомка и потом применить правое вращение так, что свойства КЧД будут сохранены. Новым братом node будет теперь чёрная вершина с красным правым потомком, и случай 3 сводится к случаю четыре.

Случай 4 (строки 29 – 33 и 60 - 64) Вершина nodeTemp чёрная, правый потомок красный. Меняя некоторые цвета (не все из них нам известны, но это нам не мешает) и, производя левое вращение вокруг node.nodeParent, мы можем удалить лишнюю черноту у node, не нарушая свойств КЧД. присваивание node = Tree.root выводит нас из цикла.

Сравнительные характеристики скорости работы различных структур данных

Чтобы всё сказанное до этого не казалось пустой болтовнёй, я в качестве заключения приведу сравнительные характеристики скорости работы различных структур данных (деревьев и массивов). Для измерения времени была использована функция WinAPI QueryPerfomanceCounter. Время пересчитано в микросекунды. В скобках приведена конечная глубина дерева. Тестирование проводилось на процессоре Intel Celeron Tualatin 1000MHz с 384Мб оперативной памяти. В качестве ключа использовалось число типа int (32-х битное целое со знаком), а в качестве данных число типа float (4-х байтное вещественное).

Количество элементов ДДП КЧД Постоянно сортированный массив Несортированный массив Массив с постсортировкой
1000

 4943 

 (1000)

 535 

 (17)

193 32 73
2000

 20571 

 (2000)

 1127 

 (19)

402 89 152
3000

 65819 

 (3000)

 1856 

 (20)

621 98 305
4000

 82321 

 (4000)

 2601 

 (21)

862 189 327
5000

 126941 

 (5000)

 3328 

 (22)

1153 192 461
6000

 183554 

 (6000)

 4184 

 (22)

1391 363 652
7000

 255561 

 (7000)

 4880 

 (23)

1641 452 789
8000

 501360 

 (8000)

 5479 

 (23)

1905 567 874
9000

 1113230 

 (9000)

 6253 

 (24)

2154 590 1059
10000

 1871090 

 (10000)

 7174 

 (24)

2419 662 1180

Таблица 1. Добавление элемента (возрастающие ключи)

Количество элементов ДДП КЧД

Постоянно  

сортированный массив

Несортированный массив Массив с постсортировкой
1000 4243 108 136 1354 134
2000 19295 250 289 5401 286
3000 71271 391 448 25373 441
4000 79819 560 615 23861 607
5000 124468 759 787 38862 776
6000 180029 956 954 55303 941
7000 246745 1199 1165 75570 1111
8000 487187 1412 1307 98729 1330
9000 1062128 1906 1494 134470 1474
10000 1807235 2068 1719 154774 1688

Таблица 2. Поиск элемента (возрастающие ключи).

Количество элементов ДДП КЧД Постоянно сортированный массив Несортированный массив Массив с постсортировкой
1000 308 419 2077 2047 2080
2000 639 876 13422 8046 8179
3000 1001 1372 25092 30902 18407
4000 1380 1831 32572 32473 32651
5000 1680 2286 50846 51001 50962
6000 2105 2891 73321 73114 73202
7000 2569 3514 99578 100059 99801
8000 3025 4384 129833 129897 130054
9000 3484 5033 164846 194361 164264
10000 4050 5690 203207 202979 202738

Таблица 3. Удаление элемента по ключу (возрастающие ключи).

Количество элементов ДДП КЧД Постоянно сортированный массив Несортированный массив Массив с постсортировкой
1000

547

(25)

548

(13)

1800 34 362
2000

1133

(25)

1171

(14)

5534 70 734
3000

1723

(28)

1905

(14)

12065 150 1174
4000

2891

(28)

2985

(15)

20867 223 1626
5000

3604

(28)

4024

(15)

32927 248 1962
6000

4336

(29)

4970

(15)

44720 373 2537
7000

5196

(29)

5794

(16)

60723 443 2977
8000

6051

(30)

6972

(16)

77482 511 3485
9000

6994

(30)

7519

(16)

104219 590 3821
10000

9544

(31)

10303

(16)

118760 584 4408

Таблица 4. Добавление элемента (случайные ключи)

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты:

Количество элементов ДДП КЧД Постоянно сортированный массив Несортированный массив Массив с постсортировкой
1000 181 136 159 1354 155
2000 406 307 347 5412 339
3000 653 494 551 12927 538
4000 925 702 765 23936 747
5000 1223 949 1024