Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами.
Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше.
Описание методов, реализованных в классе BinarySearchTree:
- метод add():
- если дерево пустое, то говорим, что корень — это наш узел;
- сравниваем поступивший ключ с ключом узла:
- если ключ меньше, то идём в левое поддерево;
- если ключ равен, то задаём узлу новое поступившее значение;
- если ключ больше, то идём в правое поддерево;
- методы minKey() и maxKey():
- по свойству дерева, минимальный ключ располагается в самом левом поддереве, а максимальный — в самом правом;
- метод delete():
- сначала находим нужный элемент по ключу (если такового нет, то выходим из метода);
- если у удаляемого узла нет правого поддерева, то мы просто замещаем узел его левым поддеревом;
- иначе находим в правом поддереве узел с минимальным ключом:
- если у этого узла родитель — это удаляемый узел, то мы просто говорим, что правое поддерево удаляемого узла есть правое поддерево найденного, а ключ и значение удаляемого узла — это ключ и значение найденного;
- если у этого узла другой родитель, то мы замещаем найденный узел его же правым поддеревом, а ключ и значение удаляемого узла — это ключ и значение найденного;
Код программы (http://ideone.com/Z2hbBv):
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class BinarySearchTree <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 = new Node(key, value); else { int compareResult = key.compareTo(node.key); if(compareResult < 0) node.left = add(node.left, key, value); else if (compareResult == 0) node.value = value; else node.right = add(node.right, key, value); } return node; } public void add(Key key, Value value) { root = add(root, key, value); } public Key MinKey(){ Node cur = root; while (cur.left != null) cur = cur.left; return cur.key; } public Key MaxKey(){ Node cur = root; while (cur.right != null) cur = cur.right; return cur.key; } public void delete(Key key) { Node cur = root; Node prev = null; while (true) { if (cur == null) return; int compareResult = key.compareTo(cur.key); if (compareResult < 0) { prev = cur; cur = cur.left; } else if (compareResult == 0) break; else { prev = cur; cur = cur.right; } } if (cur.right == null) { if (cur == prev.left) prev.left = cur.left; else prev.right = cur.left; } else { Node minFromRight = cur.right; prev = null; while (minFromRight.left != null) { prev = minFromRight; minFromRight = minFromRight.left; } if (prev == null) cur.right = minFromRight.right; else prev.left = minFromRight.right; cur.key = minFromRight.key; cur.value = minFromRight.value; } } public Value get(Key key) { Node cur = root; while (true) { if (cur == null) break; int compareResult = key.compareTo(cur.key); if (compareResult < 0) cur = cur.left; else if (compareResult == 0) break; else cur = cur.right; } return cur == null ? (Value)null : cur.value; } 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); //System.out.println(node.key + " -> " + node.value); print(node.left, level + 1); } } public void print() { print(root, 0); } } class Ideone { public static void main (String[] args) { BinarySearchTree<Integer, Integer> a = new BinarySearchTree<Integer, Integer>(); int n = 10; for(int i = 0; i < n; i++) { a.add((int)(Math.random()*10), (int)(Math.random()*1000)); } System.out.println(a.MaxKey() + " -> " + a.get(a.MaxKey())); System.out.println(a.MinKey() + " -> " + a.get(a.MinKey())); a.print(); System.out.println("\n\n"); Integer x = (int)(Math.random()*10); System.out.println(x); System.out.println("\n\n"); a.delete(x); a.print(); } } |