Задача
Разработать класс, реализующий функциональность дерева двоичного поиска.
Ссылка на условие http://java.mazurok.com/word-of-week/bst
Тесты
| input | output |
| put S 11.11 | Ok |
| put E 22.22 | Ok |
| put A 33.33 | Ok |
| put R 44.44 | Ok |
| put H 55.55 | Ok |
| put C 66.66 | Ok |
| put X 77.77 | Ok |
| put M 88.88 | Ok |
| size | 8 |
| min | (A->33.33)/2 |
| max | (X->77.77)/1 |
| L0: (S->11.11)/8 .L1: (E->22.22)/6 ..L2: (A->33.33)/2 …L3: (C->66.66)/1 ..L2: (R->44.44)/3 …L3: (H->55.55)/2 ….L4: (M->88.88)/1 .L1: (X->77.77)/1 |
|
| delete E | Ok |
| size | 7 |
| min | (A->33.33)/2 |
| max | (X->77.77)/1 |
| L0: (S->11.11)/7 .L1: (H->55.55)/5 ..L2: (A->33.33)/2 …L3: (C->66.66)/1 ..L2: (R->44.44)/2 …L3: (M->88.88)/1 .L1: (X->77.77)/1 |
|
| exit | N/A |
Критерий тестирования
В ходе тестирования мы добавляем 8 ключей с уникальными значениями. Затем мы определяем размер, минимальный и максимальный узлы, а также распечатываем все дерево, чтобы убедится, что оно имеет ожидаемою конфигурацию. Затем мы удаляем 1 ключ с серединным значением и повторяем вышеперечисленные операции, чтобы увидеть ожидаемые изменения в дереве.
Формат вывода:
Команды min и max выводят одиночный узел в следующем формате: (ключ->значение)/кол-во узлов
Команда print выводит дерево по уровням, каждая строчка имеет следующий формат: уровень: (ключ->значение)/кол-во узлов
Структура программы
Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:
- Класс CountingBST, реализующий функциональность дерева двоичного поиска с подсчетом количества узлов в дереве
- Класс CountingBSTTestApp, реализующий тестовое приложение
Класс CountingBST
|
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 |
package odessa.uni.imem.maxim; class CountingBST<Key extends Comparable<Key>, Value> { // -------------------------------------------------------------------------- public class Node { Key key; Value value; Node left, right; int count; public Node( Key key, Value value, int count) { this.key = key; this.value = value; this.left = this.right = null; this.count = count; } } private Node root; // -------------------------------------------------------------------------- public void put( Key key, Value val ) { root = put( root, key, val ); } // -------------------------------------------------------------------------- private Node put( Node x, Key key, Value val ) { if (x == null) return new Node( key, val, 1 ); int cmp = key.compareTo( x.key ); if (cmp < 0) x.left = put( x.left, key, val ); else if (cmp > 0) x.right = put( x.right, key, val ); else if (cmp == 0) x.value = val; x.count = 1 + size( x.left ) + size( x.right ); return x; } // -------------------------------------------------------------------------- public Value get( Key key ) { Node x = root; while (x != null) { int cmp = key.compareTo( x.key ); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else if (cmp == 0) return x.value; } return null; } // -------------------------------------------------------------------------- public int size() { return size( root ); } // -------------------------------------------------------------------------- private int size( Node x ) { if (x == null) return 0; return x.count; } // -------------------------------------------------------------------------- public Node min() { return min(root); } // -------------------------------------------------------------------------- private Node min( Node x ) { if ( x != null ) { if (x.left == null) { return x; } return min( x.left ); } return null; } // -------------------------------------------------------------------------- public Node max() { return max(root); } // -------------------------------------------------------------------------- private Node max( Node x ) { if ( x != null ) { if (x.right == null) { return x; } return max( x.right ); } return null; } // -------------------------------------------------------------------------- private Node deleteMin( Node x ) { if ( x != null ) { if (x.left == null) return x.right; x.left = deleteMin( x.left ); x.count = 1 + size(x.left) + size(x.right); return x; } return null; } // -------------------------------------------------------------------------- public void delete( Key key ) { root = delete( root, key ); } // -------------------------------------------------------------------------- private Node delete( Node x, Key key ) { if (x == null) return null; int cmp = key.compareTo( x.key ); if (cmp < 0) x.left = delete( x.left, key ); else if (cmp > 0) x.right = delete( x.right, key ); else { if (x.right == null) return x.left; if (x.left == null) return x.right; Node t = x; x = min( t.right ); x.right = deleteMin( t.right ); x.left = t.left; } x.count = size( x.left ) + size( x.right ) + 1; return x; } // -------------------------------------------------------------------------- private void print( Node node, int level ) { if (node != null) { for( int i = 0; i<level; i++ ) { System.out.print( "." ); } System.out.printf( "L%d: (", level ); System.out.print( node.key ); System.out.print( "->" ); System.out.print( node.value ); System.out.print( ")" ); System.out.printf( "/%d", node.count ); System.out.println(); print( node.left, level + 1 ); print( node.right, level + 1 ); } } // -------------------------------------------------------------------------- public void print() { print( root, 0 ); } // also maxKey, minKey, } |
Все методы разделены на пары — один метод пары приватный, а другой — публичный. Это необходимо для того, чтобы передавать первым аргументом корень дерева, начиная с которого выполняются все операции. Каждый приватный метод содержит первым аргументом узел, начиная с которого будет выполнятся операция. Публичный метод вызывает приватный и передает ему в качестве первого аргумента корень дерева. Это относится к основным операциям на дереве:
- put — помещает ключ и значение в дерево
- get — извлекает значение по клчу
- size — возвращает количество узлов дерева
- min — находит узел с минимальным ключом
- max — находит узел с максимальным ключом
- delete — удаление по Хиббарду ( Coursera presentation )
- print — печать дерева
Помимо основных полей, необходимых для BST, узел содержит поле count, в котором содержится количество все узлов поддерева, корнем которого является данный узел, включая сам узел.
Класс CountingBSTTestApp
|
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 |
package odessa.uni.imem.maxim; import java.util.*; public class CountingBSTTestApp { // parse text line into tokens, e.g. "put salary 120.22" to "put" "salary" "120.22" public static Vector<String> parseTextToTokens( String text ) { Vector<String> tokens = new Vector<String>(); StringTokenizer st = new StringTokenizer(text); while (st.hasMoreTokens()) { tokens.add(st.nextToken()); } return tokens; } // helper function: converts string to double if possible or returns null public static Double strToDouble( String s ) { Double x = null; try { x = Double.parseDouble( s ); } catch( NumberFormatException e ) { } return x; } // print content of one node into human readable form public static void printTreeNode( CountingBST<String,Double>.Node node ) { if ( node != null ) { System.out.print( "(" ); System.out.print( node.key ); System.out.print( "->" ); System.out.print( node.value ); System.out.print( ")/" ); System.out.print( node.count ); System.out.println(); } else { System.out.println("null"); } } // main method with command line interpreter public static void main(String[] args) { CountingBST<String,Double> tree = new CountingBST<String,Double>(); Scanner in = new Scanner(System.in); for(;;) { String inputLine = in.nextLine(); if ( inputLine.isEmpty() ) { continue; } String cmd = null; String arg1 = null; String arg2 = null; { Vector<String> inputTokens = parseTextToTokens( inputLine ); if ( inputTokens.size() > 0 ) cmd = inputTokens.get(0); if ( inputTokens.size() > 1 ) arg1 = inputTokens.get(1); if ( inputTokens.size() > 2 ) arg2 = inputTokens.get(2); } if ( cmd.equals("exit") ) { break; } else if ( cmd.equals("print") ) { tree.print(); } else if (cmd.equals("size")) { System.out.println(tree.size()); } else if ( cmd.equals("put") ) { String key = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ; Double value = ( arg2 != null ) ? strToDouble( arg2 ) : null ; if ( key == null || value == null ) { System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%s>\n",cmd,arg1,arg2); continue; } tree.put( key, value ); System.out.println("Ok"); } else if ( cmd.equals("get") ) { String key = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ; if ( key == null ) { System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n",cmd,arg1); continue; } Double value = tree.get( key ); System.out.println(value); } else if ( cmd.equals("delete") ) { String key = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ; if ( key == null ) { System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n",cmd,arg1); continue; } tree.delete( key ); System.out.println("Ok"); } else if ( cmd.equals("min") ) { printTreeNode( tree.min() ); } else if ( cmd.equals("max") ) { printTreeNode( tree.max() ); } } in.close(); } } |
Данный класс реализует тестовое приложение для класса CountingBST. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста. Он реализует командный интерпритатор, где каждая команда вызывает соответствующий публичный метод тестируемого класса. По-этому тест представляет собой текстовый файл с командами для стандартного потока ввода с консоли.
Ссылка на Ideone: https://ideone.com/b0xrPX
Очень качественно реализованная структура двоичного дерева поиска, хорошая структуризация программы, засчитано, 20 баллов.
Уважаемый Александр Сергеевич, простите что пишу в комментариях, ноя сегодня посмотрел на таблицу оценок на сайте, и там у меня выставлено 91, хотя вы уже мне поставили 85. Я просто не понял ситуацию, какая у меня действительно выходит оценка?