Binary Search Tree ist ein Algorithmus, der die Flexibilität des Einfügens verknüpfter Listen mit der Effizienz der geordneten Array-Suche kombiniert. Das Folgende ist der reine Code zum Implementieren verschiedener BST-Methoden.
Suchschlüssel, um den Wert für den Basisknoten des binären Sortierbaums zu erhaltenDer binäre Sortierbaum ist entweder ein leerer Baum oder ein Binärbaum mit den folgenden Eigenschaften:
Wenn der linke Teilbaum nicht leer ist, dann die Werte aller Knoten auf dem linken Teilbaum sind kleiner oder gleich dem Wert seines Wurzelknotens
Wenn der rechte Teilbaum nicht leer ist, dann rechter Teilbaum Die Werte aller Knoten auf sind größer oder gleich dem Wert seines Wurzelknotens
und Die linken und rechten Teilbäume sind ebenfalls Implementieren Sie den
public class BST<K extends Comparable<K>, V> {
private Node root;
private class Node {
private K key;
private V value;
private Node left;
private Node right;
private int N;
public Node(K key, V value, int N) {
this.key = key;
this.value = value;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null)
return 0;
else
return x.N;
}
}public V get(K key) {
return get(root, key);
}
private V get(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0)
return root.value;
else if (comp < 0)
return get(root.left, key);
else
return get(root.right, key);
} public void put(K key, V value) {
root = put(root, key, value);
}
private Node put(Node root, K key, V value) {
if (root == null)
return new Node(key, value, 1);
int comp = key.compareTo(root.key);
if (comp == 0)
root.value = value;
else if (comp < 0)
root.left = put(root.left, key, value);
else
root.right = put(root.right, key, value);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public K min() {
return min(root).key;
}
private Node min(Node root) {
if (root.left == null)
return root;
return min(root.left);
} public K max() {
return max(root).key;
}
private Node max(Node root2) {
if (root.right == null)
return root;
return max(root.right);
} public K floor(K key) {
Node x = floor(root, key);
if (x == null)
return null;
return x.key;
}
private Node floor(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp < 0)
return floor(root.left, key);
else if (comp > 0 && root.right != null
&& key.compareTo(min(root.right).key) >= 0)
return floor(root.right, key);
else
return root;
} public K ceiling(K key) {
Node x = ceiling(root, key);
if (x == null)
return null;
return x.key;
}
private Node ceiling(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp > 0)
return ceiling(root.right, key);
else if (comp < 0 && root.left != null
&& key.compareTo(max(root.left).key) >= 0)
return ceiling(root.left, key);
else
return root;
} public K select(int k) {
//找出BST中序号为k的键
return select(root, k);
}
private K select(Node root, int k) {
if (root == null)
return null;
int comp = k - size(root.left);
if (comp < 0)
return select(root.left, k);
else if (comp > 0)
return select(root.right, k - (size(root.left) + 1));
else
return root.key;
} public int rank(K key) {
//找出BST中键为key的序号是多少
return rank(root, key);
}
private int rank(Node root, K key) {
if (root == null)
return 0;
int comp = key.compareTo(root.key);
if (comp == 0)
return size(root.left);
else if (comp < 0)
return rank(root.left, key);
else
return 1 + size(root.left) + rank(root.right, key);
} public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node root) {
if (root.left == null)
return root.right;
root.left = deleteMin(root.left);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public void deleteMax() {
root = deleteMax(root);
}
private Node deleteMax(Node root) {
if (root.right == null)
return root.left;
root.right = deleteMax(root.right);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0) {
if (root.right == null)
return root = root.left;
if (root.left == null)
return root = root.right;
Node t = root;
root = min(t.right);
root.left = t.left;
root.right = deleteMin(t.right);
} else if (comp < 0)
root.left = delete(root.left, key);
else
root.right = delete(root.right, key);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public void print() {
print(root);
}
private void print(Node root) {
if (root == null)
return;
print(root.left);
System.out.println(root.key);
print(root.right);
}Das obige ist der detaillierte Inhalt vonBeispielcode-Freigabe für den Java-Binary Search Tree (BST)-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
