二叉搜索树(Binary Search Tree)(Java实现)

@

1、二叉搜索树

1.1、 基本概念

二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多。分析表明其平均深度为\(\mathcal{O}(\sqrt{N})\),而对于特殊类型的二叉树,即二叉查找树(binary search tree),其深度的平均值为\(\mathcal{O}(log N)\)。

二叉查找树的性质: 对于树中的每个节点X,它的左子树中所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项。

由于树的递归定义,通常是递归地编写那些操作的例程。因为二叉查找树的平均深度为\(\mathcal{O}(log N)\),所以一般不必担心栈空间被用尽。

1.2、树的节点(BinaryNode)

二叉查找树要求所有的项都能够排序,有两种实现方式;

  1. 对象实现接口 Comparable, 树中的两项使用compareTo方法进行比较;
  2. 使用一个函数对象,在构造器中传入一个比较器;

本篇文章采用了构造器重载,并定义了myCompare方法,使用了泛型,因此两种方式都支持,在后续的代码实现中可以看到。

节点定义:

    /**
* 节点
*
* @param <AnyType>
*/
private static class BinaryNode<AnyType> {
BinaryNode(AnyType theElement) {
this(theElement, null, null);
} BinaryNode(AnyType theElement, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
element = theElement;
left = left;
right = right;
} AnyType element; // the data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}

1.3、构造器和成员变量

    private BinaryNode<AnyType> root;
private Comparator<? super AnyType> cmp; /**
* 无参构造器
*/
public BinarySearchTree() {
this(null);
} /**
* 带参构造器,比较器
*
* @param c 比较器
*/
public BinarySearchTree(Comparator<? super AnyType> c) {
root = null;
cmp = c;
}

关于比较器的知识可以参考下面这篇文章:

Java中Comparator的使用

关于泛型的知识可以参考下面这篇文章:

如何理解 Java 中的 <T extends Comparable<? super T>>

1.3、公共方法(public method)

主要包括插入,删除,找到最大值、最小值,清空树,查看元素是否包含;


/**
* 清空树
*/
public void makeEmpty() {
root = null;
} public boolean isEmpty() {
return root == null;
} public boolean contains(AnyType x){
return contains(x,root);
} public AnyType findMin(){
if (isEmpty()) throw new BufferUnderflowException();
return findMin(root).element;
} public AnyType findMax(){
if (isEmpty()) throw new BufferUnderflowException();
return findMax(root).element;
} public void insert(AnyType x){
root = insert(x, root);
} public void remove(AnyType x){
root = remove(x,root);
}

1.4、比较函数

如果有比较器,就使用比较器,否则要求对象实现了Comparable接口;

    private int myCompare(AnyType lhs, AnyType rhs) {
if (cmp != null) {
return cmp.compare(lhs, rhs);
} else {
return lhs.compareTo(rhs);
}
}

1.5、contains 函数

本质就是一个树的遍历;

    private boolean contains(AnyType x, BinaryNode<AnyType> t) {
if (t == null) {
return false;
} int compareResult = myCompare(x, t.element);
if (compareResult < 0) {
return contains(x, t.left);
} else if (compareResult > 0) {
return contains(x, t.right);
} else {
return true;
}
}

1.6、findMin

因为二叉搜索树的性质,最小值一定是树的最左节点,要注意树为空的情况。

    /**
* Internal method to find the smallest item in a subtree
* @param t the node that roots the subtree
* @return node containing the smallest item
*/
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
if (t == null) {
return null;
}
if (t.left == null) {
return t;
}
return findMin(t.left);
}

1.7、findMax

最右节点;

    /**
* Internal method to find the largest item in a subtree
* @param t the node that roots the subtree
* @return the node containing the largest item
*/
private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
if (t == null){
return null;
}
if (t.right == null){
return t;
}
return findMax(t.right);
}

1.8、insert

这个主要是根据二叉搜索树的性质,注意当树为空的情况,就可以加入新的节点了,还有当该值已经存在时,默认不进行操作;

    /**
* Internal method to insert into a subtree
* @param x the item to insert
* @param t the node that roots the subtree
* @return the new root of the subtree
*/
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return new BinaryNode<>(x,null,null);
}
int compareResult = myCompare(x,t.element); if (compareResult < 0){
t.left = insert(x,t.left);
}
else if (compareResult > 0){
t.right = insert(x,t.right);
}
else{
//Duplicate; do nothing
} return t;
}

1.9、remove

二叉搜索树(Binary Search Tree)(Java实现)

二叉搜索树(Binary Search Tree)(Java实现)

二叉搜索树(Binary Search Tree)(Java实现)

注意当空树时,返回null;

最后一个三元表达式,是在之前已经排除掉节点有两个儿子的情况下使用的。

    /**
* Internal method to remove from a subtree
* @param x the item to remove
* @param t the node that roots the subtree
* @return the new root of the subtree
*/
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return t; // Item not found ,do nothing
}
int compareResult = myCompare(x,t.element); if (compareResult < 0){
t.left = remove(x,t.left);
}
else if (compareResult > 0){
t.right = remove(x,t.right);
}
else if (t.left !=null && t.right!=null){
//Two children
t.element = findMin(t.right).element;
t.right = remove(t.element,t.right);
}
else
t = (t.left !=null) ? t.left:t.right;
return t;
}

二、完整代码实现(Java)

/**
* @author LongRookie
* @description: 二叉搜索树
* @date 2021/6/26 19:41
*/ import com.sun.source.tree.BinaryTree; import java.nio.BufferUnderflowException;
import java.util.Comparator; /**
* 二叉搜索树
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> { /**
* 节点
*
* @param <AnyType>
*/
private static class BinaryNode<AnyType> {
BinaryNode(AnyType theElement) {
this(theElement, null, null);
} BinaryNode(AnyType theElement, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
element = theElement;
left = left;
right = right;
} AnyType element; // the data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
} private BinaryNode<AnyType> root;
private Comparator<? super AnyType> cmp; /**
* 无参构造器
*/
public BinarySearchTree() {
this(null);
} /**
* 带参构造器,比较器
*
* @param c 比较器
*/
public BinarySearchTree(Comparator<? super AnyType> c) {
root = null;
cmp = c;
} /**
* 清空树
*/
public void makeEmpty() {
root = null;
} public boolean isEmpty() {
return root == null;
} public boolean contains(AnyType x){
return contains(x,root);
} public AnyType findMin(){
if (isEmpty()) throw new BufferUnderflowException();
return findMin(root).element;
} public AnyType findMax(){
if (isEmpty()) throw new BufferUnderflowException();
return findMax(root).element;
} public void insert(AnyType x){
root = insert(x, root);
} public void remove(AnyType x){
root = remove(x,root);
} private int myCompare(AnyType lhs, AnyType rhs) {
if (cmp != null) {
return cmp.compare(lhs, rhs);
} else {
return lhs.compareTo(rhs);
}
} private boolean contains(AnyType x, BinaryNode<AnyType> t) {
if (t == null) {
return false;
} int compareResult = myCompare(x, t.element);
if (compareResult < 0) {
return contains(x, t.left);
} else if (compareResult > 0) {
return contains(x, t.right);
} else {
return true;
}
} /**
* Internal method to find the smallest item in a subtree
* @param t the node that roots the subtree
* @return node containing the smallest item
*/
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
if (t == null) {
return null;
}
if (t.left == null) {
return t;
}
return findMin(t.left);
} /**
* Internal method to find the largest item in a subtree
* @param t the node that roots the subtree
* @return the node containing the largest item
*/
private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
if (t == null){
return null;
}
if (t.right == null){
return t;
}
return findMax(t.right);
} /**
* Internal method to remove from a subtree
* @param x the item to remove
* @param t the node that roots the subtree
* @return the new root of the subtree
*/
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return t; // Item not found ,do nothing
}
int compareResult = myCompare(x,t.element); if (compareResult < 0){
t.left = remove(x,t.left);
}
else if (compareResult > 0){
t.right = remove(x,t.right);
}
else if (t.left !=null && t.right!=null){
//Two children
t.element = findMin(t.right).element;
t.right = remove(t.element,t.right);
}
else
t = (t.left !=null) ? t.left:t.right;
return t;
} /**
* Internal method to insert into a subtree
* @param x the item to insert
* @param t the node that roots the subtree
* @return the new root of the subtree
*/
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return new BinaryNode<>(x,null,null);
}
int compareResult = myCompare(x,t.element); if (compareResult < 0){
t.left = insert(x,t.left);
}
else if (compareResult > 0){
t.right = insert(x,t.right);
}
else{
//Duplicate; do nothing
} return t;
} }
上一篇:SVN Server配置详解 及备份


下一篇:《数据结构与算法分析——C语言描述》ADT实现(NO.03) : 二叉搜索树/二叉查找树(Binary Search Tree)