Оценивание: стандартная задача, 20 баллов.
Вот заготовка для реализации класса BST на языке Java (основана на типе BST из курса Седжвика Algorithms, Part I):
|
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 |
class BST <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; 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); //... } public void add(Key key, Value value) { root = add(root, key, value); } public void delete(Key key) { //... } public Value get(Key key) { //... } 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); } //also maxKey, minKey, } |
Специализированная версия для подсчета количества ключей (при добавлении ключа значение увеличивается на 1).
|
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 |
class CountingBST <Key extends Comparable<Key>> { private class Node { Key key; int value; Node left, right; public Node (Key key) { this.key = key; this.value = 1; this.left = this.right = null; } } private Node root; private Node add (Node node,Key key){ //возвращает измененный узел (после добавления значения) if (node == null) { Node newnode = new Node(key); return newnode; } int compareResult = key.compareTo(node.key); //... } public void add(Key key) { root = add(root, key); } public void delete(Key key) { //... } public int get(Key key) { //... } 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); } //also maxKey, minKey, } |
Реализация всех основных операций над двоичным деревом поиска (в виде псевдокода), приведена здесь.
Дополнительная задача: сравнить производительность полученного двоичного дерева в качестве реализации ассоциативного массива для задачи построения частотного словаря с производительностью TreeMap и HashMap.
Оценивание: стандартная задача, 20 баллов.