1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15 package com.google.common.collect; 16 17 import com.google.common.annotations.GwtCompatible; 18 19 import javax.annotation.Nullable; 20 21 /** 22 * A local balancing policy for modified nodes in binary search trees. 23 * 24 * @author Louis Wasserman 25 * @param <N> The type of the nodes in the trees that this {@code BstRebalancePolicy} can 26 * rebalance. 27 */ 28 @GwtCompatible 29 interface BstBalancePolicy<N extends BstNode<?, N>> { 30 /** 31 * Constructs a locally balanced tree around the key and value data in {@code source}, and the 32 * subtrees {@code left} and {@code right}. It is guaranteed that the resulting tree will have 33 * the same inorder traversal order as the subtree {@code left}, then the entry {@code source}, 34 * then the subtree {@code right}. 35 */ balance(BstNodeFactory<N> nodeFactory, N source, @Nullable N left, @Nullable N right)36 N balance(BstNodeFactory<N> nodeFactory, N source, @Nullable N left, @Nullable N right); 37 38 /** 39 * Constructs a locally balanced tree around the subtrees {@code left} and {@code right}. It is 40 * guaranteed that the resulting tree will have the same inorder traversal order as the subtree 41 * {@code left}, then the subtree {@code right}. 42 */ 43 @Nullable combine(BstNodeFactory<N> nodeFactory, @Nullable N left, @Nullable N right)44 N combine(BstNodeFactory<N> nodeFactory, @Nullable N left, @Nullable N right); 45 } 46