package demo;
import java.util.LinkedList;
import java.util.prefs.BackingStoreException;
import org.w3c.dom.Node;
/**
* 自平衡二叉树
*
* @author Administrator
*
* @param <K>
* @param <V>
*/
public class BSTAvl<K extends Comparable<K>, V> {
private final Node EmptyNode = null;
private Node head; // 头结点
private int count;// 树中的节点个数
private final static int balancerThreadhold = 2;// 树调整阈值
/**
* 私有节点
*
* @author Administrator
*
* @param <K>
* @param <V>
*/
private class Node {
K key;
V value;
Node left;
Node right;
int height;
private Node(K key, V val) {
this.key = key;
this.value = val;
this.left = EmptyNode;
this.right = EmptyNode;
this.height = 1;
}
private Node(Node node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
this.height = node.height;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{ ").append(key).append(":").append(value).append(" }");
return sb.toString();
}
}
public BSTAvl() {
head = EmptyNode;
count = 0;
}
/**
* 当前节点中的元素个数
*
* @return
*/
public int size() {
return count;
}
/**
* 当前树是否为空
*
* @return
*/
public boolean isEmpty() {
return count == 0;
}
/**
* 添加公共方法
*
* @param key
* @param val
*/
/**
* @param key
* @param val
*/
public void insert(K key, V val) {
checkArg(key, "key is null");
head = insert(head, key, val);
}
/**
* 实际的内部添加方法
*
* @param root
* @param key
* @param val
* @return
*/
private Node insert(Node root, K key, V val) {
if (root == EmptyNode) {
count++;
return new Node(key, val);
}
if (root.key.compareTo(key) > 0)
root.left = insert(root.left, key, val);
else if (root.key.compareTo(key) < 0)
root.right = insert(root.right, key, val);
else
root.value = val;
root = tryBalance(root);
return root;
}
private Node tryBalance(Node root) {
// 计算新的高度
root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
// 根据平衡因子和节点数的高度，判断是否需要左旋或是右旋
// LL
if (getBalanceFactor(root) > 1 && getBalanceFactor(root.left) >= 0)
return rotationRight(root);
// RR
if (getBalanceFactor(root) < -1 && getBalanceFactor(root.right) <= 0)
return rotationLeft(root);
// LR
if (getBalanceFactor(root) > 1 && getBalanceFactor(root.left) < 0) {
root.left = rotationLeft(root.left);
return rotationRight(root);
}
// RL
if (getBalanceFactor(root) < -1 && getBalanceFactor(root.right) > 0) {
root.right = rotationRight(root.right);
return rotationLeft(root);
}
return root;
}
/**
* 根据key查找指定的值公共方法
*
* @param key
* @return
*/
public V search(K key) {
return (V) search(head, key);
}
/**
* 实际的搜索方法
*
* @param root
* @param key
* @return
*/
private V search(Node root, K key) {
checkArg(key, "key is null");
if (root == EmptyNode)
return null;
if (root.key.compareTo(key) == 0)
return root.value;
else if (root.key.compareTo(key) > 0)
return (V) search(root.left, key);
else
return (V) search(root.right, key);
}
/**
* 前序遍历
*/
public void preOrder() {
preOrder(head);
}
private void preOrder(Node root) {
if (root == EmptyNode)
return;
System.out.print(root);
preOrder(root.left);
preOrder(root.right);
}
/**
* 中序遍历
*/
public void midOrder() {
midOrder(head);
}
private void midOrder(Node root) {
if (root == EmptyNode)
return;
midOrder(root.left);
System.out.print(root);
midOrder(root.right);
}
/**
* 后序遍历
*/
public void postOrder() {
postOrder(head);
}
private void postOrder(Node root) {
if (root == EmptyNode)
return;
postOrder(root.left);
postOrder(root.right);
System.out.println(root);
}
/**
* 非空检查
*
* @param key
* @param thrStr
*/
private void checkArg(Object key, String thrStr) {
if (key == null)
throw new IllegalArgumentException(thrStr);
}
/**
* 层级遍历
*/
public void levelOrder() {
if (head == EmptyNode)
return;
LinkedList<Node> ll = new LinkedList();
ll.addLast(head);
while (!ll.isEmpty()) {
Node node = ll.removeFirst();
System.out.println(node);
if (node.left != EmptyNode)
ll.addLast(node.left);
if (node.right != EmptyNode)
ll.addLast(node.right);
}
}
/**
* 获取最小的节点
*
* @return
*/
public K getMinNode() {
checkArg(head, "this tree is empty!!");
return (K) getMinNode(head).key;
}
private Node getMinNode(Node root) {
if (root.left == EmptyNode)
return root;
return getMinNode(root.left);
}
/**
* 获取最大的节点
*
* @return
*/
public K getMaxNode() {
checkArg(head, "this tree is empty!!");
return (K) getMaxNode(head).key;
}
private Node getMaxNode(Node root) {
if (root.right == EmptyNode)
return root;
return getMaxNode(root.right);
}
/**
* 删除最小的节点
*/
public void removeMin() {
checkArg(head, "the tree is empty");
head = removeMin(head);
}
private Node removeMin(Node root) {
if (root.left == EmptyNode) {
Node rightNode = root.right;
root = EmptyNode;
count--;
return rightNode;
}
root.left = removeMin(root.left);
return root;
}
public void removeMax() {
checkArg(head, "the tree is empty");
head = removeMax(head);
}
private Node removeMax(Node root) {
if (root.right == EmptyNode) {
Node leftNode = root.left;
root = null;
count--;
return leftNode;
}
root.right = removeMax(root.right);
return root;
}
public void remove(K key) {
head = remove(head, key);
}
/**
* 删除指定
*
* @param root
* @param key
* @return
*/
private Node remove(Node root, K key) {
if (root == EmptyNode)
return EmptyNode;
Node retNode;
if (root.key.compareTo(key) < 0) {//
root.right = remove(root.right, key);
retNode = root;
} else if (root.key.compareTo(key) > 0) {
root.left = remove(root.left, key);
retNode = root;
} else {// equal
if (root.left == EmptyNode) {// 没有左节点
Node rightNode = root.right;
root = EmptyNode;
count--;
retNode = rightNode;
} else if (root.right == EmptyNode) {// 没有右节点
Node leftNode = root.right;
root = EmptyNode;
count--;
retNode = leftNode;
} else {
// 左右节点都存在
Node min = getMinNode(root.right);
Node s = new Node(min);
s.right = remove(root.right,s.key);
s.left = root.left;
retNode = s;
}
if (retNode == EmptyNode)
return EmptyNode;
}
retNode = tryBalance(retNode);
return retNode;
}
/**
* 获取平衡因子
*
* @param node
* @return
*/
public int getBalanceFactor(Node node) {
checkArg(node, "节点为空!!");
return getHeight(node.left) - getHeight(node.right);
}
/**
* 获取节点高度
*
* @param node
* @return
*/
public int getHeight(Node node) {
if (node == null)
return 0;
return node.height;
}
/**
* 节点左旋
*
* @param node
*/
public Node rotationLeft(Node node) {
Node x = node.right;
Node T3 = x.left;
x.left = node;
node.right = T3;
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
public Node rotationRight(Node node) {
Node x = node.left;
Node T3 = x.right;
x.right = node;
node.left = T3;
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
public boolean isAvl() {
return isAvl(head);
}
/**
* 判断当前树是否为平衡树
*
* @param head
* @return
*/
private boolean isAvl(Node node) {
if (node == null)
return true;
if (Math.abs(getBalanceFactor(node)) > 1)
return false;
return isAvl(node.left) && isAvl(node.right);
}
/**
* 主要的测试函数
*
* @param args
*/
public static void main(String[] args) {
BSTAvl<Integer, Object> bst = new BSTAvl();
bst.insert(1, "hello");
bst.insert(10, "hello");
bst.insert(9, "hello");
bst.insert(20, "hello");
bst.insert(11, "hello");
bst.insert(14, "hello");
bst.insert(90, "hello");
bst.insert(25, "hello");
// bst.insert(60, "hello");
bst.insert(78, "hello");
bst.midOrder();
System.out.println("");
System.out.println(bst.isAvl());
bst.remove(14);
// System.out.println("");
System.out.println(bst.isAvl());
bst.midOrder();
}
}
网友评论