src/vs/base/common/ternarySearchTree.ts/TernarySearchTree/_delete
class TernarySearchTree:	private _delete(key: K, superStr: boolean): void {
		const iter = this._iter.reset(key);
		const stack: [Dir, TernarySearchTreeNode<K, V>][] = [];
		let node = this._root;

		// find node
		while (node) {
			const val = iter.cmp(node.segment);
			if (val > 0) {
				// left
				stack.push([Dir.Left, node]);
				node = node.left;
			} else if (val < 0) {
				// right
				stack.push([Dir.Right, node]);
				node = node.right;
			} else if (iter.hasNext()) {
				// mid
				iter.next();
				stack.push([Dir.Mid, node]);
				node = node.mid;
			} else {
				break;
			}
		}

		if (!node) {
			// node not found
			return;
		}

		if (superStr) {
			// removing children, reset height
			node.left = undefined;
			node.mid = undefined;
			node.right = undefined;
			node.height = 1;
		} else {
			// removing element
			node.key = undefined;
			node.value = undefined;
		}

		// BST node removal
		if (!node.mid && !node.value) {
			if (node.left && node.right) {
				// full node
				// replace deleted-node with the min-node of the right branch.
				// If there is no true min-node leave things as they are
				const min = this._min(node.right);
				if (min.key) {
					const { key, value, segment } = min;
					this._delete(min.key!, false);
					node.key = key;
					node.value = value;
					node.segment = segment;
				}

			} else {
				// empty or half empty
				const newChild = node.left ?? node.right;
				if (stack.length > 0) {
					const [dir, parent] = stack[stack.length - 1];
					switch (dir) {
						case Dir.Left: parent.left = newChild; break;
						case Dir.Mid: parent.mid = newChild; break;
						case Dir.Right: parent.right = newChild; break;
					}
				} else {
					this._root = newChild;
				}
			}
		}

		// AVL balance
		for (let i = stack.length - 1; i >= 0; i--) {
			const node = stack[i][1];

			node.updateHeight();
			const bf = node.balanceFactor();
			if (bf > 1) {
				// right heavy
				if (node.right!.balanceFactor() >= 0) {
					// right, right -> rotate left
					stack[i][1] = node.rotateLeft();
				} else {
					// right, left -> double rotate
					node.right = node.right!.rotateRight();
					stack[i][1] = node.rotateLeft();
				}

			} else if (bf < -1) {
				// left heavy
				if (node.left!.balanceFactor() <= 0) {
					// left, left -> rotate right
					stack[i][1] = node.rotateRight();
				} else {
					// left, right -> double rotate
					node.left = node.left!.rotateLeft();
					stack[i][1] = node.rotateRight();
				}
			}

			// patch path to parent
			if (i > 0) {
				switch (stack[i - 1][0]) {
					case Dir.Left:
						stack[i - 1][1].left = stack[i][1];
						break;
					case Dir.Right:
						stack[i - 1][1].right = stack[i][1];
						break;
					case Dir.Mid:
						stack[i - 1][1].mid = stack[i][1];
						break;
				}
			} else {
				this._root = stack[0][1];
			}
		}
	}