MaxMinBinarySearchTree中的每个节点会存储以他为根结点的子树的最大值最小值，这样可以使得之前介绍的findMax,findMin操作时间复杂度降为O(1)
MaxMinNode 节点结构如下
/**
* BST树的优势在于我们可以在节点存放一些信息使得一些操作更高效
* 比如在MaxMinNode中我们可以存放当前节点子树,包括自己的最大值最小值
* 这样可以将findMax/findMin操作的时间复杂度优化到O(1)
* @author haofan.whf
* @version $Id: AugmentNode.java, v 0.1 2018年12月11日 下午7:30 haofan.whf Exp $
*/
public class MaxMinNode extends Node{
private int minValue;
private int maxValue;
@Override
public String toString() {
return "Node{" +
(this.getLeft() == null ? "" : "left=" + this.getLeft().getValue()) +
(this.getRight() == null ? "" : ",right=" + this.getRight().getValue()) +
(this.getParent() == null ? "" : ",parent=" + this.getParent().getValue()) +
", value=" + this.getValue() +
(this.getList().size() == 0 ? "" : ",list=" + this.getList()) +
", minValue=" + this.getMinValue() +
", maxValue=" + this.getMaxValue() +
'}';
}
}
MaxMinBinarySearchTree覆写了BinarySearchTree一些修改树结构的方法,在insert/delete node的时候去更新需要更新的min/max值
/**
* 需要对原始BST的修改
* @author haofan.whf
* @version $Id: MaxMinBinarySearchTree.java, v 0.1 2018年12月11日 下午7:55 haofan.whf Exp $
*/
public class MaxMinBinarySearchTree extends BinarySearchTree{
/**
* 查询最大值
* T(N) = O(1)
* @param root
* @return
*/
@Override
public int findMax(Node root){
return parseNode(root).getMaxValue();
}
/**
* 查询最小值
* T(N) = O(1)
* @param root
* @return
*/
@Override
public int findMin(Node root){
return parseNode(root).getMinValue();
}
@Override
public Node createNode(){
return new MaxMinNode();
}
@Override
public void doAfterInsert(Node n){
MaxMinNode mmn = parseNode(n);
//重新计算max/min
//新增肯定是叶子结点
mmn.setMaxValue(mmn.getValue());
mmn.setMinValue(mmn.getValue());
updateMaxMin(n, 1);
}
/**
* 分几种情况
* 1.无父节点,无需更新
* 2.被删除的节点只有左子树,并且他是父节点的右节点 需要更新父节点的max
* 3.被删除的节点只有左子树,并且他是父节点的左节点 无需更新
* 4.被删除的节点只有右子树,并且他是父节点的左节点 需要更新父节点的min
* 5.被删除的节点只有右子树,并且他是父节点的右节点 无需更新
* 6.被删除的节点有左和右子树 这种情况不存在(会在delete操作前被swap掉)
* 7.被删除的节点是叶子节点 更新父节点max or min
* @param n
*/
@Override
public void doBeforeDelete(Node n){
int leftOrRight = leftOrRight(n);
if(leftOrRight == 0){
//没有父节点,无需更新
return;
}
if(n.getLeft() != null && n.getRight() == null && leftOrRight == -1){
//被删除的节点只有左子树,并且他是父节点的左节点 无需更新
return;
}
if(n.getLeft() == null && n.getRight() != null && leftOrRight == 1){
//被删除的节点只有右子树,并且他是父节点的右节点 无需更新
return;
}
if(n.getLeft() != null && n.getRight() != null){
//被删除的节点有左和右子树 这种情况不存在(会在delete操作前被swap掉)
throw new RuntimeException("impossible");
}
MaxMinNode mmnp = parseNode(n.getParent());
if(n.getLeft() != null && n.getRight() == null && leftOrRight == 1){
//被删除的节点只有左子树,并且他是父节点的右节点 需要更新父节点的max
mmnp.setMaxValue(super.findMax(n.getLeft()));
}
if(n.getLeft() == null && n.getRight() != null && leftOrRight == -1){
//被删除的节点只有右子树,并且他是父节点的左节点 需要更新父节点的min
mmnp.setMinValue(super.findMin(n.getRight()));
}
if(n.getLeft() == null && n.getRight() == null){
if(leftOrRight == 1){
mmnp.setMaxValue(mmnp.getValue());
}else{
mmnp.setMinValue(mmnp.getValue());
}
}
//之后将父节点当作新插入的节点更新即可
updateMaxMin(n.getParent(), 0);
}
/**
* 更新该节点所有父节点的max or min值
* @param n
*/
private void updateMaxMin(Node n, int opt){
int leftOrRight = leftOrRight(n);
if(leftOrRight == 0){
//没有父节点,那么当前节点是根节点,是第一个被插入的元素
return;
}
//当前节点的leftOrRight值
int currentNodeLOR = leftOrRight;
//currentNodeLOR * leftOrRight>0则同方向,反之则是zig-zag
while (n != null && n.getParent() != null && currentNodeLOR * leftOrRight > 0){
MaxMinNode mmn = parseNode(n);
MaxMinNode mmnp = parseNode(n.getParent());
if(leftOrRight == -1){
//应当更新父节点的最小值
if(opt==1 && mmn.getMinValue() < mmnp.getMinValue()){
mmnp.setMinValue(mmn.getMinValue());
}else if(opt == 0 && mmn.getMinValue() > mmnp.getMinValue()){
mmnp.setMinValue(mmn.getMinValue());
}
}else if(leftOrRight == 1){
//应当更新父节点的最大值
if(opt == 1 && mmn.getMaxValue() > mmnp.getMaxValue()){
mmnp.setMaxValue(mmn.getMaxValue());
}else if(opt == 0 && mmn.getMaxValue() < mmnp.getMaxValue()){
mmnp.setMaxValue(mmn.getMaxValue());
}
}
currentNodeLOR = leftOrRight(n.getParent());
n = n.getParent();
}
}
/**
* throw runtime exception unless node is MaxMinNode
*/
private MaxMinNode parseNode(Node n){
if(n instanceof MaxMinNode){
return (MaxMinNode)n;
}else{
throw new RuntimeException("node type not match");
}
}
/**
* 对MaxMinBST结构进行修改后调用此方法查看结构的完整性
* T(N) = O(N)
* 需要遍历每个节点与他左右自节点的大小关系是否满足并且节点中记录的max/min值符合要求
* @param root
*/
public void checkRI(Node root){
if(root == null){
return;
}
int maxValue = super.findMax(root);
int minValue = super.findMin(root);
MaxMinNode mmn = parseNode(root);
if(maxValue != mmn.getMaxValue() || minValue != mmn.getMinValue()){
throw new RuntimeException("it's not a max/min bst");
}
if(root.getRight() != null){
if(root.getValue() > root.getRight().getValue()){
System.err.println(root);
throw new RuntimeException("it's not a bst");
}
}
if(root.getLeft() != null){
if(root.getValue() < root.getLeft().getValue()){
System.err.println(root);
throw new RuntimeException("it's not a bst");
}
}
checkRI(root.getRight());
checkRI(root.getLeft());
}
}
测试用例
public class BSTTest {
@Test
public void bstMaxMinAugment(){
BinarySearchTree bst = new MaxMinBinarySearchTree();
int[] insertArray = randomArray(1000);
//insertArray = new int[]{2,5,3,9,6,1,8,4};
Node root = new MaxMinNode();
for (int i = 0; i < insertArray.length; i++) {
bst.insert(root, insertArray[i]);
bst.checkRI(root);
}
int[] deleteArray = randomArray(100);
//deleteArray = new int[]{3,7,0,4,8};
for (int i = 0; i < deleteArray.length; i++) {
bst.delete(root, deleteArray[i]);
bst.checkRI(root);
}
}
private static int[] randomArray(int size){
Random random = new Random();
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(size);
}
return array;
}
}
