算法自学笔记：二分查找树（3）删除操作

要完全实现符号表，我们还需要实现删除一个键-值对

一个笨办法是直接把该键对应的值设为null，但是键还保留在树中。显然，这么做会导致大量无用的键占用内存

如何彻底删除键-值对？我们可以先从一个简单问题入手：删除最小值或最大值

1 删除最小/最大值

// delete the minimum value
	public void deleteMin() {
		root = deleteMin(root);
	}
	
	private Node deleteMin(Node x) {
		if (x.left == null) {	// find the smallest
			return x.right;
		}
		x.left = deleteMin(x.left);
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}

删除最小值操作类似于put。

基线条件：如果找到最小值（x.left == null）则返回x.right，这样上一次递归调用的x.left就会被更新为该节点的右子节点。而最小值由于无引用会被GC自动清理

状态转移方程：如果没有找到最小值，左移

注意要更新各节点count

删除最大值同理

	// delete the maximum value
	public void deleteMax() {
		root = deleteMin(root);
	}
	
	private Node deleteMax(Node x) {
		if (x.right == null) {	// find the smallest
			return x.left;
		}
		x.right = deleteMax(x.right);
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}

对于删除任意其他节点，我们使用Hibbard方法

要删除一个节点，我们可以考虑三种情况实现：

1 该节点无子节点

直接把其设为null

2 该节点有一个子节点

让其父节点指向其子节点，该节点将会被GC自动回收

3 该节点有两个子节点

寻找其右子节点最小值，和该节点交换，此时就把问题变为删除有一个子节点的情况。

	// Hibbard's deletion
	public void delete(Key key) {
		delete(root, key);
	}
	
	private Node delete(Node x, Key key) {
		if (x == null) {
			return null;
		}
		// find the location of the key
		int cmp = key.compareTo(x.key);
		if (cmp > 0) {	// smaller, move to the right
			x.right =  delete(x.right, key);
		} else if (cmp < 0) {	// larger, move to the left
			x.left = delete(x.left, key);
		} else {
			if (x.left == null && x.right == null) {	// no children
				return null;
			} else if (x.left == null) {	// one child
				return x.right;
			} else if (x.right == null) {
				return x.left;
			} else {	// two children
				Node t = x;	// save the original node
				x = min(t.right);
				x.left = t.left;
				x.right = deleteMin(t.right);
			}
		}
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}

该程序分为以下几部分：

1 寻找要删除的值

和之前查找操作同理，比较当前节点键大小和目标键进行左移或右移

2 删除操作：

找到要删除的值之后进行判断：

如没有子节点返回null

如只有一个子节点返回其子节点，使得子节点和父节点相连，要删除的节点由于失去指向其的指针会被清除

如果有两个子节点，找出右子树的最小值，放在原来节点位置，此时二叉树的条件还符合

至此，二叉树实现的符号表查找，添加，删除功能全部实现，此为完整程序：

public class BSTSymbolTable <Key extends Comparable, Value> {
	
	private class Node {
		private Key key;
		private Value value;
		private Node left;
		private Node right;
		private int count;
		private Node(Key key, Value value, int count) {
			this.key = key;
			this.value = value;
			this.count = count;
		}
	}
	
	public Node root;
	
	
	public int size() {
		return size(root);
	}
	
	private int size(Node x) {
		if (x == null) {
			return 0;
		} else {
			return x.count;
		}
	}
	
	// constructor
	public BSTSymbolTable () {
		root = null;
	}
	
	
	// put a key-value pair into the tree
	public void put (Key key, Value value) {
		root = insert(key, value, root);
	}
	
	private Node insert(Key key, Value value, Node x) {
		if (x == null) {
			return new Node(key, value, 1);
		}
		if (x.key.compareTo(key) > 0) {	// smaller, move to the left
			x.left =  insert(key, value, x.left);
		} else if (x.key.compareTo(key) < 0) {	// larger, move to the right
			x.right =  insert(key, value, x.right);
		} else {
			x.value = value;	// key existed, replace it
		}
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}
	
	
	// find a certain value according to its key
	public Value get(Key key) {
		Node result = get(key, root);
		if (result == null) {
			return null;
		}
		return result.value;
	}
	
	private Node get(Key key, Node x) {
		if (x == null) {	// no this key
			return null;
		}
		
		if (x.key.compareTo(key) > 0) {	// smaller, move to the left
			return get(key, x.left);
		} else if (x.key.compareTo(key) < 0) {	// larger, move to the right
			return get(key, x.right);
		} else {
			return x;	// find it
		}
	}
	
	
	// find the smallest key
	public Key min() {
		return min(root).key;
	}
	
	private Node min(Node x) {
		if (x.left == null) {
			return x;
		} else {
			return min(x.left);
		}
	}
	
	
	// find the largest key
	public Key max() {
		return max(root).key;
	}
	
	private Node max(Node x) {
		if (x.right == null) {
			return x;
		} else {
			return max(x.right);
		}
	}
	
	
	// find the largest key less or equals k
	public Key floor (Key k) {
		Node x = floor(root, k);
		if (x == null) {
			return null;
		} else {
			return x.key;
		}
	}
	
	private Node floor(Node x, Key k) {
		if (x == null) {
			return null;
		} 
		int cmp = k.compareTo(x.key);
		if (cmp == 0) {	// the same key, return it
			return x;
		} else if (cmp < 0) {
			return floor(x.left, k);	// smaller, move to the left
		} else {	// larger, attempt to move to the right
			Node t = floor(x.right, k);
			if (t != null) {
				return t;
			} else {
				return x;
			}
		}
	}
	
	
	// find the smallest key larger or equals k
	public Key ceiling (Key k) {
		Node x = ceiling(root, k);
		if (x == null ) {
			return null;
		}
		return x.key;
	}
	
		
	private Node ceiling(Node x, Key k) {
		if (x == null) {
			return null;
		}
		int cmp = k.compareTo(x.key);
		if (cmp == 0) {	// the exact value
			return x;
		} else if (cmp > 0) {
			return ceiling(x.right, k);	// larger, move to the left
		} else {	// smaller, attempt to move to the right
			Node t = ceiling(x.left, k);
			if (t != null) {
				return t;
			} else {
				return x;
			}
		}
	}
	
	
	// return the kth smallest key
	public Key select(int k) {
		Node x = select(k, root);
		if (x == null) {
			return null;
		}
		return x.key;
	}
	
	private Node select(int k, Node x) {
		if (x == null) {
			return null;
		}
		int rank = size(x.left);
		if (rank == k) {	// find the correct index
			return x;
		} else if (rank > k) { // move to the left
			return select(k, x.left);
		} else {	// move to the right
			return select(k - rank - 1, x.right);
		}
	}
	
	
	// find the rank of a given key
	public int rank(Key key) {
		return rank(key, root);
	}
	
	private int rank(Key key, Node x) {
		if (x == null) {
			return 0;
		}
		int cmp = key.compareTo(x.key);
		if (cmp == 0) {	// find the key
			return size(x.left);
		} else if (cmp > 0) {	// smaller, move to the right
			return size(x.left) + 1 + rank(key, x.right);
		} else {	// larger, move to the left
			return rank(key, x.left);
		}
	}
	
	
	// delete the minimum value
	public void deleteMin() {
		root = deleteMin(root);
	}
	
	private Node deleteMin(Node x) {
		if (x.left == null) {	// find the smallest
			return x.right;
		}
		x.left = deleteMin(x.left);
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}
	
	// delete the maximum value
	public void deleteMax() {
		root = deleteMin(root);
	}
	
	private Node deleteMax(Node x) {
		if (x.right == null) {	// find the smallest
			return x.left;
		}
		x.right = deleteMax(x.right);
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}
	
	
	// Hibbard's deletion
	public void delete(Key key) {
		delete(root, key);
	}
	
	private Node delete(Node x, Key key) {
		if (x == null) {
			return null;
		}
		// find the location of the key
		int cmp = key.compareTo(x.key);
		if (cmp > 0) {	// smaller, move to the right
			x.right =  delete(x.right, key);
		} else if (cmp < 0) {	// larger, move to the left
			x.left = delete(x.left, key);
		} else {
			if (x.left == null && x.right == null) {	// no children
				return null;
			} else if (x.left == null) {	// one child
				return x.right;
			} else if (x.right == null) {
				return x.left;
			} else {	// two children
				Node t = x;	// save the original node
				x = min(t.right);
				x.left = t.left;
				x.right = deleteMin(t.right);
			}
		}
		x.count = size(x.left) + size(x.right) + 1;
		return x;
	}

Hibbard删除操作的局限性：

反复调用Hibbard删除操作会导致树变得更不平衡，从而增加树高度，增加查找等操作时间开销。如果反复执行插入与删除，二叉树的插入，查找，删除时间复杂度都会退化为O(N（½）)而非理想情况下O(logN)

一种特殊的二分查找树，红黑查找树，可以保证任何情况下的O(logN)时间复杂度

原文链接：https://blog.csdn.net/Raine_Yang/article/details/122783922

你可能也喜欢