BST二叉排序树的Java实现及性能测试
先上性能测试
插入顺序为[2020083, 1380236, 593540, 4735175, 3866086, 4768997, 4042546, 6091851, 4107114, 5544658]省略以下7999990个数据..
向空BST中插入随机的800万个int节点耗时6921ms
----------
删除顺序为[4550297, 7468335, 5023455, 510970, 659394, 277607, 2929773, 7492435, 4148428, 1244599]省略以下7999990个数据..
从含有800万个int节点的BST中随机逐个删除所有节点耗时7609ms
Process finished with exit code 0
节点对象
class BinaryNode {
private int val;
private BinaryNode left;
private BinaryNode right;
//省略无参构造器
public BinaryNode(int val) {
this.val = val;
}
//省略getter和setter方法
@Override
public String toString() {
return "BinaryNode{" +
"val=" + val +
'}';
}
public void add(BinaryNode node) {
if (node == null) {
return;
}
if (node.val < this.val) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
//前序遍历
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
//中序
public void inOrder() {
if (this.left != null) {
this.left.inOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.inOrder();
}
}
//后序
public void postOrder() {
if (this.left != null) {
this.left.postOrder();
}
if (this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
public BinaryNode preOrderSearch(int val) {
BinaryNode res = null;
if (this.val == val) {
return this;
}
if (this.left != null) {
res = this.left.preOrderSearch(val);
}
if (this.right != null) {
res = this.right.preOrderSearch(val);
}
return res;
}
//找到某个节点的父节点
public BinaryNode findParent(int val) {
if (val < this.val) {
if (this.left == null) {
return null;
} else if (this.left.val == val) {
return this;
} else {
return this.left.findParent(val);
}
} else {
if (this.right == null) {
return null;
} else if (this.right.val == val) {
return this;
} else {
return this.right.findParent(val);
}
}
}
public BinaryNode findNode(int val) {
if (this.val == val) {
return this;
} else if (val < this.val) {
if (this.left == null) {
return null;
} else {
return this.left.findNode(val);
}
} else {
if (this.right == null) {
return null;
} else {
return this.right.findNode(val);
}
}
}
}
BST对象
class BinarySearchTree {
private BinaryNode root;
public void add(BinaryNode node) {
if (root == null) {
root = node;
} else {
//让BinaryNode自己去add,否则触发旋转时会有遗漏
root.add(node);
}
}
public void inOrder() {
if (root == null) {
System.out.println("bst为空 无法遍历");
} else {
if (root.getLeft() != null) {
root.getLeft().inOrder();
}
System.out.println(root);
if (root.getRight() != null) {
root.getRight().inOrder();
}
}
}
public BinaryNode findParent(int val) {
if (root == null) {
return null;
} else if (root.getVal() == val) {
//注意 由于根节点没有parent 所以即使在根节点找到了 也返回null
//所以当返回null时记得检测根节点是不是要找的节点
return null;
} else if (val < root.getVal()) {
if (root.getLeft() == null) {
return null;
} else if (root.getLeft().getVal() == val) {
return root;
} else {
return root.getLeft().findParent(val);
}
} else {
if (root.getRight() == null) {
return null;
} else if (root.getRight().getVal() == val) {
return root;
} else {
return root.getRight().findParent(val);
}
}
}
public BinaryNode findNode(int val) {
if (root == null) {
return null;
} else {
return root.findNode(val);
}
}
public BinaryNode deleteNode(int val) {
//空树
if (root == null) {
return null;
}
//没有该val对应的节点
BinaryNode target = findNode(val);
BinaryNode parent = findParent(val);
if (target == null) {
return null;
} else {
//找到了该节点
if (target.getRight() == null && target.getLeft() == null) {
//待删除节点没有子树 直接删除
if (parent == null) {
//没有子树 也没有父节点 说明这棵树里只有这唯一的节点
root = null;
return target;
} else {
//有父节点 但没有子树 直接干掉
//待删除节点是其父节点的左节点
if ( parent.getLeft()!=null && parent.getLeft().getVal() == val) {
parent.setLeft(null);
return target;
} else {
//待删除节点是其父节点的右节点
//不用判断右节点是否为null
// 因为上一个if不满足,那么target100%是parent的右节点
parent.setRight(null);
return target;
}
}
} else if (target.getLeft() == null || target.getRight() == null) {
//待删除节点有且仅有一颗子树
//特别注意待删除节点是root节点 且只有一个左子树和一个右子树的情况
if (target.getLeft() == null) {
//待删除节点仅有右子树
if(parent==null){
//待删除节点是root节点 且只有一个右子树
root=target.getRight();
return target;
}
if (parent.getLeft()!=null && parent.getLeft().getVal() == val) {
//待删除节点是其父节点的左节点
//则父节点的左节点替换为target的右子树
parent.setLeft(target.getRight());
return target;
} else {
//待删除节点是其父节点的右节点
//则父节点的右节点替换为target的右子树
parent.setRight(target.getRight());
return target;
}
}else {
//待删除节点仅有左子树
if(parent==null){
//待删除节点是root节点 且只有一个左子树
root=target.getLeft();
return target;
}
if (parent.getLeft()!=null && parent.getLeft().getVal() == val) {
//待删除节点是其父节点的左节点
//则父节点的左节点替换为target的右子树
parent.setLeft(target.getLeft());
return target;
} else {
//待删除节点是其父节点的右节点
//则父节点的右节点替换为target的右子树
parent.setRight(target.getLeft());
return target;
}
}
}else{ // 重要 待删除节点既有左子树又有右子树
BinaryNode leftleft = leftLeft(target.getRight());
int tmp = leftleft.getVal();
deleteNode(tmp);
target.setVal(tmp);
}
}
return null;
}
//寻找给定节点的左子树的左子树的左子树.......
public BinaryNode leftLeft(BinaryNode node){
BinaryNode p = node;
while(p.getLeft()!=null){
p=p.getLeft();
}
return p;
}
}
main方法&测试代码
public static void main(String[] args) {
long startTime;
long endTime;
long usedTime;
BinarySearchTree bst = new BinarySearchTree();
int arr[] = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = i;
}
Sort.shuffle(arr);
int[] insertOrder = java.util.Arrays.copyOf(arr,10);
System.out.println("插入顺序为"+Arrays.toString(insertOrder)+"省略以下7999990个数据..");
startTime = System.currentTimeMillis();
for (int i = 0; i < 8000000; i++) {
bst.add(new BinaryNode(arr[i]));
}
endTime = System.currentTimeMillis();
usedTime = (endTime-startTime);
System.out.println("向空BST中插入随机的800w个int节点耗时"+usedTime+"ms");
System.out.println("----------");
Sort.shuffle(arr);
int[] deleteOrder = java.util.Arrays.copyOf(arr,10);
System.out.println("插入顺序为"+Arrays.toString(deleteOrder)+"省略以下7999990个数据..");
startTime = System.currentTimeMillis();
for (int i = 0; i < 8000000; i++) {
bst.deleteNode(arr[i]);
}
endTime = System.currentTimeMillis();
usedTime = (endTime-startTime);
System.out.println("从含有800w个int节点的BST中随机逐个删除所有节点耗时"+usedTime+"ms");
}