import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class SizeBalancedTree > {
public class Node {
//data域：å˜æ”¾æ•°æ®é¡¹
T data;
//size域：å˜æ”¾æ ‘的大å°ï¼ˆèŠ‚点数目）
int size;
Node parent;
Node left;
Node right;
public Node(T data, int size, Node parent, Node left, Node right) {
this.data = data;
this.size = size;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString() {
return "[data=" + data + ",size=" + size + "]";
}
}
//æ ¹èŠ‚ç‚¹
private Node root;
public Node root() {
return root;
}
public SizeBalancedTree() {
root = null;
}
public SizeBalancedTree(T data) {
root = new Node(data, 1, null, null, null);
}
/**
* å¾€æ ¹ä¸ºrootçš„æ ‘ä¸æ’å…¥data
*
* @param data
* @param root
**/
public void insert(T data) {
if (root == null) { //å¦‚æžœæ ¹ä¸ºç©º
root = new Node(data, 1, null, null, null);
} else {
Node current = root;
Node parent = null;
int result = 0;
while (current != null) {
parent = current;
result = data.compareTo(current.data);
if (result > 0) {
current = current.right;
} else {
current = current.left;
}
}
Node newNode = new Node(data, 1, parent, null, null);
if (result > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
ancestorAdd1(newNode);
maintain(newNode);
}
}
private void ancestorAdd1(Node node) {
Node current = node;
while (current.parent != null) {
current.parent.size += 1;
current = current.parent;
}
}
private void ancestorminu1(Node node) {
Node current = node;
while (current.parent != null) {
current.parent.size -= 1;
current = current.parent;
}
}
private boolean trueOrFalse(Node node) {
Node current = node;
while (current != null) {
if (current == root.left) {
return false;
} else if (current == root.right) {
return true;
}
current = current.parent;
}
return false;
}
private void maintain(Node node) { //nodeä¸ºæ–°æ·»åŠ çš„èŠ‚ç‚¹
if (root == node.parent) {
return;
} else {
maintainHelp(root, trueOrFalse(node));
}
}
private void maintainHelp(Node node, boolean flag) { //ä¼ è¿‡æ¥çš„nodeä¸ºæ–°æ·»åŠ çš„èŠ‚ç‚¹
if (node != null) {
/*Node t = node;
Node l = t.left;
Node r = t.right;*/
if (!flag && node.left != null) { //左边
if ((node.right == null && node.left.left != null) || (node.left.left != null && node.left.left.size > node.right.size)) { //case1
right_rot(node);
} else if ((node.right == null && node.left.right != null) || (node.left.right != null && node.left.right.size > node.right.size)) {//case2
left_rot(node.left);
right_rot(node);
} else {
return;
}
maintainHelp(node.left, false);
maintainHelp(node.right, true);
maintainHelp(node, false);
maintainHelp(node, true);
} else if (flag && node.right != null) { //å³è¾¹
if ((node.left == null && node.right.left != null) || (node.right.left != null && node.right.left.size > node.left.size)) { //case2*
right_rot(node.right);
left_rot(node);
} else if ((node.left == null && node.right.right != null) || (node.right.right != null && node.right.right.size > node.left.size)) {//case1*
left_rot(node);
} else {
return;
}
maintainHelp(node.left, false);
maintainHelp(node.right, true);
maintainHelp(node, false);
maintainHelp(node, true);
}
}
}
/**
* ä»Žæ ¹ä¸ºnodeçš„æ ‘ä¸åˆ 除数æ®å…ƒç´ 为data的节点
*
* @param node
* @param data
*/
public void remove(Node node, T data) {
Node del = find(data);
if (del != null) {
boolean what = trueOrFalse(del);
if (del.left == null && del.right == null) {
if (del == root) {
root = null;
} else {
ancestorminu1(del);
if (del == del.parent.left) {
del.parent.left = null;
} else {
del.parent.right = null;
}
del.parent = null;
maintainHelp(root, what);
}
} else if (del.right != null && del.left == null) {
//å› ä¸ºå·²ç»å¹³è¡¡ï¼Œæ‰€ä»¥è¦åˆ 除的节点del有且仅有一个å³å节点
if (root == del) {
root = del.right;
del.right.parent = null;
del.right = null;
} else {
ancestorminu1(del);
if (del == del.parent.left) {
del.parent.left = del.right;
} else {
del.parent.right = del.right;
}
del.right.parent = del.parent;
del.parent = del.right = null;
maintainHelp(root, what);
}
} else if (del.left != null && del.right == null) {
//å› ä¸ºå·²ç»å¹³è¡¡ï¼Œæ‰€ä»¥è¦åˆ 除的节点del有且仅有一个左å节点
if (root == del) {
root = del.left;
del.left.parent = null;
del.left = null;
} else {
ancestorminu1(del);
if (del == del.parent.left) {
del.parent.left = del.left;
} else {
del.parent.right = del.left;
}
del.left.parent = del.parent;
del.parent = del.left = null;
maintainHelp(root, what);
}
} else { //å·¦å³åæ ‘éƒ½ä¸ä¸ºç©º
Node preOfDel = pre(del, data);
del.data = preOfDel.data;
ancestorminu1(preOfDel);
preOfDel.parent.left = preOfDel.left;
if (preOfDel.left != null) {
preOfDel.left.parent = preOfDel.parent;
}
preOfDel.parent = preOfDel.left = null;
maintainHelp(root, what);
}
} else {
return;
}
}
/**
* åœ¨æ ‘ä¸æŸ¥æ‰¾é”®å€¼ä¸ºdata的结点
*
* @param data
* @return
*/
public Node find(T data) {
Node current = root;
if (root == null) {
return null;
} else {
int result;
while (current != null) {
result = data.compareTo(current.data);
if (result > 0) {
current = current.right;
} else if (result < 0) {
current = current.left;
} else {
return current;
}
}
}
return null;
}
/**
* MAC地å€çš„查询与替æ¢
*
* @param data
*/
public void findAndChange(T data) {
Node current = root;
if (root == null) {
System.out.println("Changed Error: Root");
} else {
int result;
while (current != null) {
result = data.compareTo(current.data);
if (result > 0) {
current = current.right;
} else if (result < 0) {
current = current.left;
} else {
current.data = data;
break;
}
}
}
}
/**
* 返回IPæ ‘ä¸å¯¹åº”IP范围代表的çœä»½
*
* @param data
* @return
*/
public String findIp(T data) {
Node current = root;
if (root == null) {
return null;
} else {
int result;
while (current != null) {
result = data.compareTo(current.data);
if (result > 0 && current.right != null) {
current = current.right;
} else if (result > 0 && current.right == null) {
return current.data.toString();
} else if (result < 0 && current.left != null) {
current = current.left;
} else if (result < 0 && current.left == null) {
return current.data.toString();
} else if (result == 0) {
return current.parent.data.toString();
}
}
}
return current.parent.data.toString();
}
/**
* åœ¨æ ‘ä¸æŸ¥æ‰¾æŽ’å为k的节点
*
* @param node
* @param k
* @return
*/
public Node select(Node node, int k) {
if (root == null) {
try {
throw new Exception("è¯¥æ ‘ä¸ºç©º");
} catch (Exception e) {
e.printStackTrace();
}
} else if (root.size < k) {
try {
throw new Exception("该节点ä¸å˜åœ¨ä¸€ä¸ªæŽ’å为" + k + "的节点，但å˜åœ¨ä¸€ä¸ªæœ€å¤§æŽ’å为" + root.size + "的节点");
} catch (Exception e) {
e.printStackTrace();
}
} else {
if (node != null) {
int result;
if (node.left != null) {
result = node.left.size + 1;
if (result == k) {
return node;
} else if (result < k) {
return select(node.right, k - result);
} else {
return select(node.left, k);
}
} else if (node.right != null) {
if (k == 1) {
return node;
} else {
return select(node.right, k - 1);
}
} else {
return node;
}
}
}
return null;
}
//最大值
public T minData() {
return select(root, 1).data;
}
//最å°å€¼
public T maxData() {
return select(root, this.root().size).data;
}
//这里考虑到了è¦æŸ¥çœ‹æŽ’åçš„æ•°æ®å…ƒç´ ä¸åœ¨æ ‘ä¸
public int rank(Node node, T data) {
Node p = find(data);
T m = minData();
return data.compareTo(m) < 0 ? 1 : (p == null ? cRank(node, data) + 1 : cRank(node, data));
}
//返回以nodeä¸ºæ ¹çš„æ ‘ä¸å…ƒç´ 值为data的排å
private int cRank(Node node, T data) {
if (node != null) {
int result = data.compareTo(node.data);
if (node.left != null && node.right != null) {
if (result < 0) {
return cRank(node.left, data);
} else if (result > 0) {
return cRank(node.left, data) + cRank(node.right, data) + 1;
}
return node.left.size + 1;
} else if (node.right != null && node.left == null) {
if (result < 0) {
return 0;
} else if (result > 0) {
return cRank(node.right, data) + 1;
}
return 1;
} else if (node.left != null && node.right == null) {
if (result < 0) {
return cRank(node.left, data);
} else if (result > 0) {
return cRank(node.left, data) + 1;
}
return cRank(node.left, data) + 1;
} else {
if (result < 0) {
return 0;
} else if (result > 0) {
return 1;
}
return 1;
}
}
return 0;
}
//以nodeèŠ‚ç‚¹ä¸ºæ ¹æŸæ•°æ®å…ƒç´ çš„å‰é©±
public Node pre(Node node, T data) {
Node current = node;
Node preNode = null;
int result;
while (current != null) {
result = data.compareTo(current.data);
/*if(result == 0){
return current;
}else*/
if (result > 0) {
preNode = current;
current = current.right;
} else {
current = current.left;
}
}
return preNode;
}
//以nodeèŠ‚ç‚¹ä¸ºæ ¹æŸæ•°æ®å…ƒç´ çš„åŽç»§
public Node succ(Node node, T data) {
Node current = node;
Node preNode = null;
int result;
while (current != null) {
result = data.compareTo(current.data);
/*if(result == 0){
return current;
}else */
if (result < 0) {
preNode = current;
current = current.left;
} else {
current = current.right;
}
}
return preNode;
}
/**
* å³æ—‹(x/yæ‰æ˜¯å…³é”®)
*
* @param x │ │
* x y
* ││ - ││
* y──┘└─γ α──┘└─x
* ││ ││
* α─┘└─β β─┘└─γ
*/
private void right_rot(Node x) {
Node y = x.left;
y.parent = x.parent;
if (x.parent != null) {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
x.left = y.right;
if (y.right != null) {
y.right.parent = x;
}
y.right = x;
x.parent = y;
y.size = x.size;
x.size = (y.left == null ? y.size - 0 - 1 : y.size - y.left.size - 1);
if (root == x) {
root = y;
}
}
/**
* 左旋(x/yæ‰æ˜¯å…³é”®)
*
* @param x │ │
* x y
* ││ -> ││
* α──┘└─y x──┘└─γ
* ││ ││
* β─┘└─γ α─┘└─β
*/
private void left_rot(Node x) {
Node y = x.right;
y.parent = x.parent;
if (x.parent != null) {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
y.left = x;
x.parent = y;
y.size = x.size;
x.size = (y.right == null ? y.size - 0 - 1 : y.size - y.right.size - 1);
if (root == x) {
root = y;
}
}
//广度优先é历
public List breadthFirstSearch() {
return cBreadthFirstSearch(root);
}
//TODO: æ¤å¤„需è¦é’ˆå¯¹IPå’ŒMACé‡å†™BFS,ä»…æå–å„自所需è¦çš„ä¿¡æ¯å³å¯
private List cBreadthFirstSearch(Node node) {
List nodes = new ArrayList();
Deque deque = new ArrayDeque();
if (node != null) {
deque.offer(node);
}
while (!deque.isEmpty()) {
Node tmp = deque.poll();
nodes.add(tmp);
if (tmp.left != null) {
deque.offer(tmp.left);
}
if (tmp.right != null) {
deque.offer(tmp.right);
}
}
return nodes;
}
}