二叉树分析之二：二叉搜索树的相关特性分析

二叉搜索树的定义

    和前面一篇讨论二叉树有一点不一样，二叉搜索树它本身是一种二叉树，但是它有一个特殊的地方。任何一个二叉树中间的节点都是可以比较的。他们有一个key的值用于比较节点之间的大小。而且，对于任意一个二叉搜索树中间的节点，它左子树中间的节点值小于它，而它右子树的节点值则大于或等于它。一个典型的搜索二叉树如下图所示：

 

    在有的情况下，我们为了实现某些方法方便会在树中间增加一些属性，比如指向父节点的引用，当前节点所有子节点元素个数。

    下面是一种二叉树节点的定义：

private static class BinaryNodeWithSize<T> extends BinaryNode<T>
{
	BinaryNodeWithSize(T x)
	{
		super(x);
		size = 0;
	}

	int size;
}

class BinaryNode<T>
{
	T element;
	BinaryNode<T> left;
	BinaryNode<T> right;
	BinaryNode<T> parent;

	BinaryNode(T element)
	{
		this.element = element;
		left = right = parent = null;
	}
}

     这里通过继承的方式实现一种包含指向父节点引用和子节点个数的节点类型。

 

前驱(predecessor)

    前驱指的是对指定的一个节点找到一个比它小但是和它值最接近的节点。要求一个节点的前驱比较理想的情况是需要用到节点指向父节点的引用。在具体查找元素的时候需要向上访问。我们主要针对两种情况进行讨论：

1. 如果该节点有左子树，那么和它最接近的那个前驱元素肯定是左子树的最大值。这种情况对应的图如下所示：

    实际上这种情况就是要找到节点左子树的最大值。

2. 如果该节点没有左子树，我们需要向上来查找。对于7这个节点来说，我们需要找到比它小的。但是如果它是它父节点的左儿子，则该父节点比它大，不符合要求。需要一直找到将它或者它上面的节点作为右儿子的那个节点。如下图：

 

     所以针对这种情况我们可以得出如下的代码：

public BinaryNode<T> predecessor(BinaryNode<T> t)
{ 
	if(t != null)
	{
		if(t.left != null)
			return findMax(t.left);
		BinaryNode<T> y = t.parent;
		while(y != null && t == y.left)
		{
			t = y;
			y = y.parent;
		}

		return y;
	}

	return null;
}

里面的findMax实现如下：

private BinaryNode<T> findMax(BinaryNode<T> t)
{
	if(t != null)
		while(t.right != null)
			t = t.right;

	return t;
}

  

后继(successor)

    后继节点就是比当前节点大的节点集合中最小的那个。求节点的后继和前驱类似。也要考虑两种情况。

1. 如果它有右子树，肯定后继是右子树的最小值。

 

2. 如果它没有右子树，则后继节点是它向上的树中第一个以它的上级节点为左子树的那个节点。如下图所示：

    对应的实现代码则如下：

public BinaryNode<T> successor(BinaryNode<T> t)
{
	if(t != null)
	{
		if(t.right != null)
			return findMin(t.right);
		BinaryNode<T> y = t.parent;
		while(y != null && t == y.right)
		{
			t = y;
			y = y.parent;
		}

		return y;
	}

	return null;
}

protected BinaryNode<T> findMin(BinaryNode<T> t)
{
	if(t != null)
		while(t.left != null)
			t = t.left;

	return t;
}

 

插入元素(insert)

    假定我们要插入一个元素，最基本的思路就是先根据这个要插入的值和树中间的节点进行比较，如果该节点比目标值大，则在节点的左子树里面寻找插入的地方，否则在右子树里面寻找。这里的一个实现用到了递归的思路，使得很多需要考虑的细节都被简化了：

protected BinaryNode<T> insert(T x, BinaryNode<T> tt)
{
	BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>) tt;

	if(t == null)
		t = new BinaryNodeWithSize<T>();
	else if(x.compareTo(t.element) < 0)
		t.left = insert(x, t.left);
	else if(x.compareTo(t.element) > 0)
		t.right = insert(x, t.right);
	else
		throw new DuplicateItemException(x.toString());
	t.size++;
	return t;
}

    这里递归的一个妙用就是在每次要插入一个元素的时候，我们需要修改经历过的节点size值。size表示该节点下面所有子树元素的个数。通过返回修改后的根节点很多需要考虑修改的细节都通过递归给自动实现了。

    如果我们考虑一个非递归的版本实现，则会发现要繁琐一些，当然，这里返回的不再是修改后的树的根节点，而是当前插入的元素节点：

protected BinaryNode<T> insertIter(T x, BinaryNode<T> t)
{
    BinaryNode<T> prev = null, node = t;
    while(t != null)
    {
        prev = t;
	if(x.compareTo(t.element) < 0)
        {
            t.size++;
	    t = t.left;
        }
	else if(x.compareTo(t.element) > 0)
        {
            t.size++;
	    t = t.right;
        }
	else 
	    throw new DuplicateItemException(x.toString());
    }
    if(prev == null)
        node = new BinaryNode<T>(x);
    else
    {
	if(x.compareTo(prev.element) < 0)
	{
            prev.left = new BinaryNode<T>(x);
	    prev.left.parent = prev;
	}
	else
	{
	    prev.right = new BinaryNode<T>(x);
	    prev.right.parent = prev;
	}
    }
    return node;
}

    通过比较这两部分的代码，我们会发现使用递归有的时候确实可以隐藏了很多需要考虑的细节，而且代码也会简单很多。 

删除元素(remove)

    和前面添加元素的方式相反，这里要找到需要删除的元素然后删除它。删除元素的过程可能会复杂一点。针对它所在节点的情况。我们分别进行讨论。

1. 如果该节点是一个叶节点。

    直接删除该元素，将该父节点所指向它的引用置为null。

2. 如果该节点只有一个子树

    将它的左/右子节点替换它本身。

3. 如果该节点有两个子树

    笼统的来说，既然它有左右两个子节点，可以取它的后继元素，也就是右子树的最小值来替换它。然后在右子树中删除这个最小值节点。根据右子节点是否有左子树，具体的形式还会稍微有点不一样。

    一种情况如下，右子节点没有左子树，这意味着它的右子节点就是右子树最小的元素：

     如果节点的右子节点有左子树的话，则对应下面的情形：

 

 

    针对前面的那些讨论，下面是remove方法的实现：

protected BinaryNode<T> remove(T x, BinaryNode<T> tt)
{
	BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>) tt;

	if(t == null)
		throw new ItemNotFoundException(x.toString());
	if(x.compareTo(t.element) < 0)
		t.left = remove(x, t.left);
	else if(x.compareTo(t.element) > 0)
		t.right = remove(x, t.right);
	else if(t.left != null && t.right != null)
	{
		t.element = findMin(t.right).element;
		t.right = removeMin(t.right);
	}
	else
		return (t.left != null) ? t.left : t.right;

	t.size--;
	return t;
}

protected BinaryNode<T> removeMin(BinaryNode<T> tt)
{
	BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>) tt;

	if(t == null)
		throw new ItemNotFoundException();
	if(t.left == null)
		return t.right;

	t.left = removeMin(t.left);
	t.size--;
	return t;
}

    remove方法在这里采用递归的方式返回待删除子树的根节点，和前面的思路类似。

第k小的元素

    在节点增加了size属性之后，我们需要求这个第k小元素的问题就比较简单了。首先我们从树的根节点开始，比较这个目标k值和它的左子节点的元素个数，如果它小于或者等于左子节点元素个数的话，则需要在左子树里面继续查找。如果k大于左子树个数+1的话，则在右子树里查找k-t.left.size - 1。这里判断查找到的条件是k == t.left.size + 1。因为这正好表示k的值和当前节点对应。

protected BinaryNode<T> findKth(int k, BinaryNode<T> t)
{
	if(t == null)
		throw new IllegalArgumentException();
	int leftSize = (t.left != null) ? ((BinaryNodeWithSize<T>) t.left).size : 0;

	if(k <= leftSize)
		return findKth(k, t.left);
	if(k == leftSize + 1)
		return t;
	return findKth(k - leftSize - 1, t.right);
}

 

总结

     二叉搜索树的定义使得查找和插入元素的时候可以按照一个类似于二分法的思路去操作节点。在它的基础上衍生出来的计算节点和各种插入删除操作都比较常见，这里对他们的过程做一个简单的整理。里面还有一些结合指向父节点的小细节的地方考虑还不够成熟。

参考资料

Introduction to algorithms

Data Structures and Problem Solving Using Java

Algorithms