MaxMinBinarySearchTree中的每個節(jié)點會存儲以他為根結(jié)點的子樹的最大值最小值耕漱，這樣可以使得之前介紹的findMax,findMin操作時間復(fù)雜度降為O(1)
MaxMinNode 節(jié)點結(jié)構(gòu)如下
/**
* BST樹的優(yōu)勢在于我們可以在節(jié)點存放一些信息使得一些操作更高效
* 比如在MaxMinNode中我們可以存放當(dāng)前節(jié)點子樹,包括自己的最大值最小值
* 這樣可以將findMax/findMin操作的時間復(fù)雜度優(yōu)化到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一些修改樹結(jié)構(gòu)的方法,在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
//新增肯定是葉子結(jié)點
mmn.setMaxValue(mmn.getValue());
mmn.setMinValue(mmn.getValue());
updateMaxMin(n, 1);
}
/**
* 分幾種情況
* 1.無父節(jié)點,無需更新
* 2.被刪除的節(jié)點只有左子樹,并且他是父節(jié)點的右節(jié)點 需要更新父節(jié)點的max
* 3.被刪除的節(jié)點只有左子樹,并且他是父節(jié)點的左節(jié)點 無需更新
* 4.被刪除的節(jié)點只有右子樹,并且他是父節(jié)點的左節(jié)點 需要更新父節(jié)點的min
* 5.被刪除的節(jié)點只有右子樹,并且他是父節(jié)點的右節(jié)點 無需更新
* 6.被刪除的節(jié)點有左和右子樹 這種情況不存在(會在delete操作前被swap掉)
* 7.被刪除的節(jié)點是葉子節(jié)點 更新父節(jié)點max or min
* @param n
*/
@Override
public void doBeforeDelete(Node n){
int leftOrRight = leftOrRight(n);
if(leftOrRight == 0){
//沒有父節(jié)點,無需更新
return;
}
if(n.getLeft() != null && n.getRight() == null && leftOrRight == -1){
//被刪除的節(jié)點只有左子樹,并且他是父節(jié)點的左節(jié)點 無需更新
return;
}
if(n.getLeft() == null && n.getRight() != null && leftOrRight == 1){
//被刪除的節(jié)點只有右子樹,并且他是父節(jié)點的右節(jié)點 無需更新
return;
}
if(n.getLeft() != null && n.getRight() != null){
//被刪除的節(jié)點有左和右子樹 這種情況不存在(會在delete操作前被swap掉)
throw new RuntimeException("impossible");
}
MaxMinNode mmnp = parseNode(n.getParent());
if(n.getLeft() != null && n.getRight() == null && leftOrRight == 1){
//被刪除的節(jié)點只有左子樹,并且他是父節(jié)點的右節(jié)點 需要更新父節(jié)點的max
mmnp.setMaxValue(super.findMax(n.getLeft()));
}
if(n.getLeft() == null && n.getRight() != null && leftOrRight == -1){
//被刪除的節(jié)點只有右子樹,并且他是父節(jié)點的左節(jié)點 需要更新父節(jié)點的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());
}
}
//之后將父節(jié)點當(dāng)作新插入的節(jié)點更新即可
updateMaxMin(n.getParent(), 0);
}
/**
* 更新該節(jié)點所有父節(jié)點的max or min值
* @param n
*/
private void updateMaxMin(Node n, int opt){
int leftOrRight = leftOrRight(n);
if(leftOrRight == 0){
//沒有父節(jié)點,那么當(dāng)前節(jié)點是根節(jié)點,是第一個被插入的元素
return;
}
//當(dāng)前節(jié)點的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){
//應(yīng)當(dāng)更新父節(jié)點的最小值
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){
//應(yīng)當(dāng)更新父節(jié)點的最大值
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結(jié)構(gòu)進(jìn)行修改后調(diào)用此方法查看結(jié)構(gòu)的完整性
* T(N) = O(N)
* 需要遍歷每個節(jié)點與他左右自節(jié)點的大小關(guān)系是否滿足并且節(jié)點中記錄的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;
}
}
