Задача
Реализовать структуру «Двоичное дерево поиска» в соответствии с этим шаблоном.
Решение
По моему субъективному мнению, тут следует привести более ли менее детальное описание только операций вставки и удаления вершины.
Операция вставки
Пусть у нас есть вершина с ключом [latex]key[/latex] и дерево [latex]T[/latex], в которое нам нужно вставить нашу вершину. Сразу у нас есть ссылка только на корень дерева, поэтому посмотрим на значение ключа в корне дерева. Если оно вдруг совпало с нашим [latex]key[/latex], то, в этой реализации, мы заменяем поля этой вершины на новые. Если оно не совпало, то так как нам нужно найти незанятое место, куда бы мы могли вставить нашу вершину, мы проверяем: если значение нашего [latex]key[/latex] больше значения в корне — правое поддерево [latex]T[/latex], иначе — левое. Можно заметить, что ситуация изменилась только значением ключа в корне, поэтому можно применить наши прошлые действия. Так мы будем делать, пока наш выбор не остановится на пустом поддереве, то есть — пока не найдется места для нашей вершины. Теперь, когда мы нашли приют нашей вершине, мы вставляем ее на это место.
Операция удаления
Для того, чтобы удалить вершину, нам, очевидно, нужно ее сначала найти, при этом, у нас есть только ключ этой вершины. И да, мы будем не одни, с нами пойдет указатель на предыдущую вершину в дереве. Искать мы будем способом, описанным в предыдущем пункте. Если значение нашего ключа и ключа в корне совпало — мы нашли обреченную вершину, если же мы попали в пустое поддерево — можно считать, что наша работа выполнена (нет вершины — нет проблемы). Однако рассмотрим первый случай.
Пусть правое (левое) поддерево пусто. Тогда удалить вершину просто — мы заменяем адрес удаляемой вершины у предыдущей вершины (там ведь стоит указатель) на адрес левого (правого) поддерева удаляемой вершины.
Если же правое поддерево не пусто, мы уже не можем просто удалить вершину. Чтобы сохранить основное свойство дерева мы должны найти замену. В правом поддереве мы найдем вершину с наименьшим ключом и поменяем с удаляемой вершиной (если есть еще какие-то поля — их тоже заменяем). Задача свелась к первому случаю.
Код
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Tree <Key extends Comparable<Key>, Value> { private class Node { Key key; Value value; Node left, right; public Node (Key key, Value value) { this.key = key; this.value = value; this.left = this.right = null; } } private Node root; public Key getRootKey(){ return root.key; } public Value getRootValue(){ return root.value; } private Node add (Node node,Key key, Value value){ //возвращает измененный узел (после добавления значения) if (node == null){ Node newnode = new Node(key,value); return newnode; } int compareResult = key.compareTo(node.key); if(compareResult == 0) { node.value = value; return node; } else if(compareResult < 0) node.left = add(node.left, key, value); else node.right = add(node.right, key, value); return node; } public Key MinKey(){ Node cur = root; // спускаемся к самому левому листу, по свойству дерева - наименьший ключ там for(; cur.left != null; cur = cur.left){} return cur.key; } public Key MaxKey(){ Node cur = root; // спускаемся к самому правому листу, по свойству дерева - наибольший ключ там for(; cur.right != null; cur = cur.right){} return cur.key; } //вспомогательная функция, которая нигде не используется. private Node NodeMinKey(Node node){ Node cur = node; for(; cur.left != null; cur = cur.left){} return cur; } public void add(Key key, Value value) { root = add(root, key, value); } //удаление вершины public void delete(Key key) { Node cur = root; Node prev = null; //спускаемся по дереву, пока не найдем вершину или не уткнемся в null for(; true; ){ if(cur == null) return; if(key.compareTo(cur.key) < 0){ prev = cur; cur = cur.left; } else if(key.compareTo(cur.key) > 0){ prev = cur; cur = cur.right; } else break; } /* * Итак, у нас есть элемент, который нужно удалить (cur) и его предок (prev) * Теперь нас ждет разбор частных случаев: * 1)Если правый сын удаляемого элемента не существует, мы можем просто выкинуть этот элемент из * цепи prev -> cur -> left, оставив prev -> left. * 2)Если же правый сын существует, так просто выкинуть вершину мы не можем. * Чтобы сохранить свойство дерева мы найдем узел с наименьшим ключом в правом поддереве cur, * присоединим к найденному узлу левого сына cur и заменим cur на этот узел. */ if(cur.right == null) if(prev == null){ root = root.left; } else if(cur == prev.right) prev.right = cur.left; else prev.left = cur.left; else if(cur.left == null) if(prev == null){ root = root.left; } else if(cur == prev.right) prev.right = cur.left; else prev.left = cur.left; else{ Node mostLeft = cur.right; prev = null; for(; mostLeft.left != null;){ prev = mostLeft; mostLeft = mostLeft.left; } if(prev != null) prev.left = mostLeft.right; else cur.right = mostLeft.right; cur.key = mostLeft.key; cur.value = mostLeft.value; } } public Value get(Key key) { Node cur = root; for(; true; ){ if(cur == null) break; if(key.compareTo(cur.key) < 0) cur = cur.left; else if(key.compareTo(cur.key) > 0) cur = cur.right; else break; } return cur != null? cur.value : (Value)null; } private void print(Node node, int level) { if (node != null) { print(node.right, level+1); for (int i=0; i < level; i++) { System.out.print("\t"); } System.out.println(node.key + " => " + node.value); print(node.left, level + 1); } } public void print() { print(root, 0); } public static void main (String[] args){ Tree<Double, Double> a = new Tree<Double, Double>(); int n = 10000; for(int i = 0; i < n; i++){ a.add( Math.round(Math.random() * 1000.0) + 1.0*i, Math.round(Math.random() * 1000000.0) + 1.0*i); } System.out.println(a.MaxKey() + " => " + a.get(a.MaxKey())); System.out.println(a.MinKey() + " => " + a.get(a.MinKey())); System.out.println(); System.out.println(); System.out.println(); System.out.println("First print"); a.print(); a.delete(a.getRootKey()); System.out.println(); System.out.println(); System.out.println(); System.out.println("Second print"); a.print(); } } |
Денис, Вы просто публикуете код. Нужно сформулировать задачу и сделать необходимые пояснения к программе.
Необходимо:
1) постановка задачи,
2) тестовый вывод,
3) пояснения (можно и кратко),
4) ссылка на online IDE.
На IDEOne у Вас «Ошибка выполнения»
Это результат c 10000 итераций. Адеоне просто не может это вывести, а нетбинкс может.