BinarySearchTree
2018-12-12 本文已影响0人
nafoahnaw
节点数据结构
public class Node {
private Node left;
private Node right;
private Node parent;
private Integer value;
/**
* 相同value的节点将挂在该list上
*/
private List<Integer> list = new ArrayList<Integer>();
@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()) +
'}';
}
}
BinarySearchTree api
/**
* BST
* RI(Represent Invariant):
* 假设X为某一节点，则有left(X).value < X.value and right(X).value > X.value
* @author haofan.whf
* @version $Id: BinarySearchTree.java, v 0.1 2018年12月09日 下午11:13 haofan.whf Exp $
*/
public class BinarySearchTree {
/**
* 查询树中与给定value相同的Node
* T(N) = O(h)
* h为树的高度(为啥不是lgN，因为BST不一定平衡，当极端情况下(元素完全有序)会退化为链表)
* @param value
* @return
*/
public Node query(Node root, int value){
if(root.getValue() < value){
if(root.getRight() != null){
return query(root.getRight(), value);
}else{
return null;
}
}else if(root.getValue() > value){
if(root.getLeft() != null){
return query(root.getLeft(), value);
}else{
return null;
}
}else{
return root;
}
}
/**
* 向树中添加一个节点
* 如果节点已经存在,将节点加入到相同节点的list中
* T(N) = O(h)要查找空位，相当于query
* @param value
* @return
*/
public void insert(Node root, int value){
if(root.getValue() == null){
root.setValue(value);
doAfterInsert(root);
return;
}
if(root.getValue() < value){
//应该放在当前节点的右边
if(root.getRight() == null){
//右子树为空,则直接挂在当前节点的右边即可
Node n = createNode();
n.setParent(root);
n.setValue(value);
root.setRight(n);
doAfterInsert(n);
}else{
insert(root.getRight(), value);
}
}else if(root.getValue() > value){
if(root.getLeft() == null){
Node n = createNode();
n.setParent(root);
n.setValue(value);
root.setLeft(n);
doAfterInsert(n);
}else{
insert(root.getLeft(), value);
}
}else{
root.getList().add(value);
}
}
public Node createNode(){
return new Node();
}
/**
* @param node 被插入的Node
*/
public void doAfterInsert(Node node){
}
/**
* 找出继任者(如果value在root中存在)
* T(N) = O(h)
* @return
*/
public Node findSuccessor(Node root, int value){
Node node = query(root, value);
if(node == null){
throw new RuntimeException("can not found node=" + node);
}
return findSuccessor(node);
}
/**
* 找出继任者(找出整个树中仅仅比node大的节点,即node rightSubTree的最小节点,如果rightSubTree不存在则比node.value大的第一个parent)
* T(N) = O(h)
* @return
*/
public Node findSuccessor(Node node){
if(node.getRight() != null){
return query(node, findMin(node.getRight()));
}else{
int value = node.getValue();
boolean foundSuccessor = false;
while(node.getParent() != null){
if(node.getParent().getValue() > value){
foundSuccessor = true;
break;
}
node = node.getParent();
}
return foundSuccessor ? node : null;
}
}
/**
* 删除节点
* 如果删除的节点list有值也直接把节点删除
* 如果要删除的节点不存在则直接跳过
* T(N) = O(h)
* @param root
* @param value
* @return
*/
public void delete(Node root, int value){
Node node = query(root, value);
if(node == null){
return;
}
int leftOrRight = leftOrRight(node);
if(node.getRight() == null && node.getLeft() == null){
//叶子结点,直接删除即可
doBeforeDelete(node);
if(leftOrRight == -1){
node.getParent().setLeft(null);
}else if(leftOrRight == 1){
node.getParent().setRight(null);
}else{
//也没有父节点,说明这棵树只有一个元素
root = null;
}
}else if(node.getRight() == null && node.getLeft() != null){
//只有左子树
doBeforeDelete(node);
node.getLeft().setParent(node.getParent());
if(leftOrRight == -1){
node.getParent().setLeft(node.getLeft());
}else if(leftOrRight == 1){
node.getParent().setRight(node.getLeft());
}else{
//也没有父节点
node.getLeft().setParent(null);
root = node.getLeft();
}
}else if(node.getRight() != null && node.getLeft() == null){
//只有右子树
doBeforeDelete(node);
node.getRight().setParent(node.getParent());
if(leftOrRight == -1){
node.getParent().setLeft(node.getRight());
}else if(leftOrRight == 1){
node.getParent().setRight(node.getRight());
}else{
//也没有父节点
node.getRight().setParent(null);
root = node.getRight();
}
}else{
Node successor = findSuccessor(node);
swap(successor, node);
//此时node被交换到了successor的位置
//该位置有两种可能,要么是叶子结点,要么只有右子树
delete(successor, successor.getValue());
}
}
/**
* @param node 即将被删除的Node
*/
public void doBeforeDelete(Node node){
}
/**
* 交换两个node的位置(仅仅是交换值,树实际结构没有变化)
* @param node1
* @param node2
*/
public void swap(Node node1, Node node2){
int value1 = node1.getValue();
List<Integer> list1 = node1.getList();
int value2 = node2.getValue();
List<Integer> list2 = node2.getList();
node1.setValue(value2);
node2.setValue(value1);
node1.setList(list2);
node2.setList(list1);
}
/**
* 查询给定node是其parent的左/右节点
* @param node
* @return
*/
public int leftOrRight(Node node){
if(node.getParent() == null){
//无父节点
return 0;
}else{
if(node.getParent().getLeft() != null
&& node.getParent().getLeft().getValue() == node.getValue()){
//左节点
return -1;
}else if(node.getParent().getRight() != null
&& node.getParent().getRight().getValue() == node.getValue()){
//右节点
return 1;
}else {
throw new RuntimeException("impossible!");
}
}
}
/**
* 查询最大值,顺着右子树一直向下
* T(N) = O(h)
* @param root
* @return
*/
public int findMax(Node root){
if(root.getRight() != null){
return findMax(root.getRight());
}else{
return root.getValue();
}
}
/**
* 查询最小值,顺着左子树一直向下
* T(N) = O(h)
* @param root
* @return
*/
public int findMin(Node root){
if(root.getLeft() != null){
return findMin(root.getLeft());
}else{
return root.getValue();
}
}
/**
* 对BST结构进行修改后调用此方法查看结构的完整性
* T(N) = O(N)
* 需要遍历每个节点与他左右自节点的大小关系是否满足
* @param root
*/
public void checkRI(Node root){
if(root == null){
return;
}
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 bstNormal(){
BinarySearchTree bst = new BinarySearchTree();
int[] array = new int[]{3,5,6,4,2};
Node root = new Node();
for (int i = 0; i < array.length; i++) {
bst.insert(root, array[i]);
}
bst.checkRI(root);
Assert.assertTrue(bst.query(root, 6).getValue() == 6);
Assert.assertTrue(bst.findMax(root) == 6);
Assert.assertTrue(bst.findMin(root) == 2);
Assert.assertTrue(bst.findSuccessor(root, 5).getValue() == 6);
Assert.assertTrue(bst.findSuccessor(root, 6) == null);
int[] insertArray = randomArray(100);
root = new Node();
for (int i = 0; i < insertArray.length; i++) {
bst.insert(root, insertArray[i]);
bst.checkRI(root);
}
int[] deleteArray = randomArray(50);
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;
}
}
BST的优点在于无论什么操作时间复杂度都是O(h)
类BST结构的优势在于可以在节点中存储一些信息来优化某些操作，比如
MaxMinBinarySearchTree
