[Design] BST Node Insertion / Deletion

First Word

For BST it’s very important to do insert and delete (balancing not required).

Insertion is easy, but deletion is very difficult. However, it’s a good idea to at least know the principles.

Insert a node

Steps:

1. check whether new value = current node value. If not, proceed.

2. if new value is less, than:

   1. if current node has no left child, set left to new value, and return

   2. otherwise, go to left child and start over

3. if new value is greater, than:

   1. if current node has no right child, set right to new value

   2. otherwise, go to right child and start over

Note:

The BST may not be balanced after the insertion.

Code

Code snippet from this article

public boolean add(TreeNode node, int value) {
	if (value == node.val)
		return false;
	if (value < node.val) {
		if (node.left == null) {
			node.left = new TreeNode(value);
			return true;
		} else {
			return add(node.left, value);
		}
	} else if (value > node.val) {
		if (node.right == null) {
			node.right = new TreeNode(value);
			return true;
		} else {
			return add(node.right, value);
		}
	}
	return false;
}

Delete a node

Steps:

1. Find the node
2. Find the maximum node in the left subtree
3. Replace the node with the maximum node in the left subtree.

Special Cases:

1. The node doest have a left child.
2. The maximum node in the left subtree has a left child.
3. The node is the root of the tree

Code

The source code given by ninechap

private void myDeleteNode(TreeNode parent, TreeNode node) {
	if (node.left == null) {
		if (parent.right == node) {
			parent.right = node.right;
		} else {
			parent.left = node.right;
		}
	} else {
		TreeNode maxNodeParent = node;
		TreeNode maxNode = node.left;

		// find the maximum node in the left sub tree
		while (maxNode.right != null) {
			maxNodeParent = maxNode;
			maxNode = maxNode.right;
		}

		if (maxNodeParent.left == maxNode) {
			maxNodeParent.left = maxNode.left;
		} else {
			maxNodeParent.right = maxNode.left;
		}

		// move replacedNode to node
		maxNode.left = node.left;
		maxNode.right = node.right;
		if (parent.left == node) {
			parent.left = maxNode;
		} else {
			parent.right = maxNode;
		}
	}
}

private void findAndDelete(TreeNode parent, TreeNode node, int val) {
	if (node == null) {
		return;
	}
	if (node.val == val) {
		myDeleteNode(parent, node);
	} else if (node.val < val) {
		findAndDelete(node, node.right, val);
	} else {
		findAndDelete(node, node.left, val);
	}
}

public TreeNode deleteNode(TreeNode root, int val) {
	TreeNode dummyNode = new TreeNode(0);
	dummyNode.left = root;
	findAndDelete(dummyNode, root, val);
	return dummyNode.left;
}

A little bit on balancing

There are 2 ways to balance a tree. Most common method is tree rotation:

An AVL Trees means a self-balancing search trees. If balance gets out of range −1…+1, the subtree is rotated to bring into balance.

Second way is to convert tree into a linkedlist, then build the tree again (we have discussed this algorithm before, pick the middle element).

This method is slow if we insert and re-balance on each step, but we can do bulk insert/delete forgetting about the re-balancing for a while. This will make the data structure faster! more details