Definition 1.
Binary search tree (BST) is also called binary search tree, binary sort tree. A binary search tree is a binary tree, but it has the characteristics of a search tree:
- Each node is larger than its left node and smaller than its right node.
- The left and right subtrees of each node are binary search trees.
- Middle order traversal of a binary search tree is the result of sorting from smallest to largest.
2. Time complexity
Binary search tree combines the flexibility of linked list insertion and deletion with the efficiency of array search.
- Best case:The binary search tree in the best case is a full binary tree, where the length from the root to all the leaves is zero
lgNAnd the corresponding height of the tree is alsolgN. At this point no matter search, insert, delete can be inO(lgN)Finish in time. - Worst case:The worst-case binary search tree has only one child per node, almost like a linked list, and the height of the tree is N. In this case, the time complexity of search, insert and delete is
O(N). - Average case: The average case of a binary search tree should be between best and best case.
3. The implementation
Next I use a binary search tree to implement a symbol table, a symbol table is a data structure that stores key-value pairs, where keys cannot be repeated, values can be repeated. The following operations are defined:
- Put (Key Key, Value Value) Inserts the Key and Value Value into the symbol table
- Delete (Key Key) Deletes the specified key-value pair
- Get (Key Key) Gets the value of the Key, or returns NULL if the Key does not exist
- DeleteMax () deletes the key pairs corresponding to the largest key
- DeleteMin () deletes the key-value pair corresponding to the smallest key
- Min () gets the smallest key
- Max () gets the largest key
- Size () Gets the size of the symbol table
- IsEmpty () checks whether the symbol table isEmpty
The code is described in Java, using generics. The keys must implement the Comparable interface because they need to be compared. In the BST class, an inner class Node is used to represent the nodes of the binary search tree, which is also a key-value pair. All operations are iterative.
Code implementation
public class BST<Key extends Comparable<Key>, Value> {
private class Node {
Key key;
Value value;
Node left;
Node right;
public Node(Key key, Value value, Node left, Node right){
this.key = key;
this.value = value;
this.left = left;
this.right = right; }}private Node root;
private int size;
public int size(a){
return size;
}
public boolean isEmpty(a){
return root == null;
}
public Value get(Key key){
Node node = root;
int cmp;
while(node ! =null){
cmp = key.compareTo(node.key);
if (cmp < 0)
node = node.left;
else if (cmp > 0)
node = node.right;
else
return node.value;
}
return null;
}
public void put(Key key, Value value){
if (root == null) {
root = new Node(key, value, null.null);
size = 1;
return;
}
Node node = root;
Node parent = null;
int cmp;
while(node ! =null){
parent = node;
cmp = key.compareTo(node.key);
if (cmp < 0)
node = node.left;
else if (cmp > 0)
node = node.right;
else {
node.value = value;
return; }}if (key.compareTo(parent.key) < 0)
parent.left = new Node(key, value, null.null);
else
parent.right = new Node(key, value, null.null);
++size;
}
private Node max(Node node){
if (node == null)
return null;
while(node.right ! =null)
node = node.right;
return node;
}
private Node min(Node node){
if (node == null)
return null;
while(node.left ! =null)
node = node.left;
return node;
}
public Key max(a){
Node node = max(root);
return node == null ? null : node.key;
}
public Key min(a){
Node node = min(root);
return node == null ? null : node.key;
}
private Node deleteMax(Node node) {
Node x = node;
if (node == null)
return null;
Node parent = null;
while(node.right ! =null){
parent = node;
node = node.right;
}
--size;
if (parent == null)
return node.left;
else
parent.right = node.left;
return x;
}
private Node deleteMin(Node node) {
Node x = node;
if (node == null)
return null;
Node parent = null;
while(node.left ! =null){
parent = node;
node = node.left;
}
--size;
if (parent == null)
return node.right;
else
parent.left = node.right;
return x;
}
public void deleteMax(a){
root = deleteMax(root);
}
public void deleteMin(a){
root = deleteMin(root);
}
public void traverse(a){
traverse(root);
}
// middle order traversal
private void traverse(Node node){
if (node == null)
return;
traverse(node.left);
System.out.println(node.key);
traverse(node.right);
}
public void delete(Key key) {
if (root == null)
return;
Node node = root;
Node parent = root;
int cmp;
while(node ! =null){
cmp = key.compareTo(node.key);
if (cmp == 0) {
--size;
cmp = key.compareTo(parent.key);
if (node.left == null) {if (cmp < 0)
parent.left = node.right;
else if (cmp > 0)
parent.right = node.right;
else
root = node.right;
return;
}
if (node.right == null) {if (cmp < 0)
parent.left = node.left;
else if (cmp > 0)
parent.right = node.left;
else
root = node.left;
return;
}
Node x = min(node.right);
node.key = x.key;
node.value = x.value;
node.right = deleteMax(node.right);
}
else {
parent = node;
if (cmp < 0)
node = node.left;
elsenode = node.right; }}}public static void main(String[] args){
BST<Integer, String> bst = new BST<>();
bst.put(2."qw");
bst.put(3."fy");
bst.put(5."naoko");
bst.put(1."qw");
bst.put(4."naoko");
bst.put(-3."naoko");
bst.deleteMax();
bst.deleteMin();
bst.delete(10); bst.traverse(); }}Copy the code4. The last
Binary search trees are simple but do not perform well in the worst case. However, it is the basis of data structures for other tree types, binary search trees and other variants such as AVL trees, red black trees, Treap trees, etc. In C++ and Java collections apis, symbol tables or sets are implemented using red-black trees.