一些树的定义：满二叉树、完全二叉树、二叉搜索树、平衡二叉树
二叉查找树
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
定义：
- 一棵二叉查找树是一棵二叉树，每个节点都含有一个 Comparable 的键（以及对应的值）
- 每个节点的键都大于左子树中任意节点的键而小于右子树中任意节点的键
- 每个节点都有两个链接，左链接、右链接，分别指向自己的左子节点和右子节点，链接也可以指向 null
- 尽管链接指向的是节点，可以将每个链接看做指向了另一棵二叉树。这个思路能帮助理解二叉查找树的递归方法
二叉查找树的特性：
- 左子树上所有结点的值均小于或等于它的根结点的值
- 右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉排序树 ```java public class BinarySearchTree { public Node root; protected int size;
protected Node createNode(int value, Node parent, Node left, Node right) {
return new Node(value, parent, left, right);
}
public Node search(int element) {
Node node = root; while (node != null && node.value != null && node.value != element) { if (element < node.value) { node = node.left; } else { node = node.right; } } return node;}
public Node insert(int element) {
if (root == null) { root = createNode(element, null, null, null); size++; return root; } Node insertParentNode = null; Node searchTempNode = root; while (searchTempNode != null && searchTempNode.value != null) { insertParentNode = searchTempNode; if (element < searchTempNode.value) { searchTempNode = searchTempNode.left; } else { searchTempNode = searchTempNode.right; } } Node newNode = createNode(element, insertParentNode, null, null); if (insertParentNode.value > element) { insertParentNode.left = newNode; } else { insertParentNode.right = newNode; } size++; return newNode;}
public Node delete(int element) {
Node deleteNode = search(element); if (deleteNode != null) { return delete(deleteNode); } else { return null; }}
private Node delete(Node deleteNode) {
if (deleteNode == null) return null; Node nodeToReturn = null; if (deleteNode.left == null) { nodeToReturn = transplant(deleteNode, deleteNode.right); } else if (deleteNode.right == null) { nodeToReturn = transplant(deleteNode, deleteNode.left); } else { Node sucessorNode = getMinimum(deleteNode.right); if (sucessorNode.parent != deleteNode) { transplant(sucessorNode, sucessorNode.right); sucessorNode.right = deleteNode.right; sucessorNode.right.parent = sucessorNode; } transplant(deleteNode, sucessorNode); sucessorNode.left = deleteNode.left; sucessorNode.left.parent = sucessorNode; nodeToReturn = sucessorNode; } size--; return nodeToReturn;}
/**
* 将树中的一个节点（newNode）放置到另一个节点（nodeToReplace）的位置
*
* @param nodeToReplace
* @param newNode
* @return
*/
private Node transplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == null) {
root = newNode;
} else if (nodeToReplace == nodeToReplace.parent.left) {
nodeToReplace.parent.left = newNode;
} else {
nodeToReplace.parent.right = newNode;
}
if (newNode != null) newNode.parent = nodeToReplace.parent;
return newNode;
}
public boolean contains(int element) {
return search(element) != null;
}
public int getMinimum() {
return getMinimum(root).value;
}
public Node getMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
public int getMaximum() {
return getMaximum(root).value;
}
public Node getMaximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}
public int getSuccessor(int element) {
return getSuccessor(search(element)).value;
}
private Node getSuccessor(Node node) {
if (node.right != null) {
return getMinimum(node.right);
} else {
Node currentNode = node;
Node parentNode = node.parent;
while (parentNode != null && currentNode == parentNode.right) {
currentNode = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
public int getSize() {
return size;
}
/**
* Tree traversal with printing element values. In order method.
*/
public void printTreeInOrder() {
printTreeInOrder(root);
}
/**
* Tree traversal with printing element values. Pre order method.
*/
public void printTreePreOrder() {
printTreePreOrder(root);
}
/**
* Tree traversal with printing element values. Post order method.
*/
public void printTreePostOrder() {
printTreePostOrder(root);
}
/*-------------------PRIVATE HELPER METHODS-------------------*/
private void printTreeInOrder(Node entry) {
if (entry != null) {
printTreeInOrder(entry.left);
if (entry.value != null) {
System.out.println(entry.value);
}
printTreeInOrder(entry.right);
}
}
private void printTreePreOrder(Node entry) {
if (entry != null) {
if (entry.value != null) {
System.out.println(entry.value);
}
printTreeInOrder(entry.left);
printTreeInOrder(entry.right);
}
}
private void printTreePostOrder(Node entry) {
if (entry != null) {
printTreeInOrder(entry.left);
printTreeInOrder(entry.right);
if (entry.value != null) {
System.out.println(entry.value);
}
}
}
// -------------------------------- TREE PRINTING ------------------------------------
public void printTree() {
printSubtree(root);
}
public void printSubtree(Node node) {
if (node.right != null) {
printTree(node.right, true, "");
}
printNodeValue(node);
if (node.left != null) {
printTree(node.left, false, "");
}
}
private void printNodeValue(Node node) {
if (node.value == null) {
System.out.print("<null>");
} else {
System.out.print(node.value.toString());
}
System.out.println();
}
private void printTree(Node node, boolean isRight, String indent) {
if (node.right != null) {
printTree(node.right, true, indent + (isRight ? " " : " | "));
}
System.out.print(indent);
if (isRight) {
System.out.print(" /");
} else {
System.out.print(" \\");
}
System.out.print("----- ");
printNodeValue(node);
if (node.left != null) {
printTree(node.left, false, indent + (isRight ? " | " : " "));
}
}
}
这里需要注意的是在删除一个节点时的操作：
- 如果该节点没有子节点，那么直接删除
- 如果该节点只有一个子树，那么将该节点删除后把该子树放到删除节点的位置上，并设置新的父子关系
- 如果该节点有两个子树，那么将右子树的最小节点放到删除节点的位置上，并设置新的父子关系
**二叉查找树的优点：**
- 二叉排序树是一种比较有用的折中方案
- 数组的搜索比较方便，可以直接用下标，但删除或者插入某些元素就比较麻烦
- 链表与之相反，删除和插入元素很快，但查找很慢
- 二叉排序树就既有链表的好处，也有数组的好处
- 在处理大批量的动态的数据是比较有用
**二叉查找树的缺点：**
- 顺序存储可能会浪费空间（在非完全二叉树的时候），但是读取某个指定的节点的时候效率比较高
- 链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低
<a name="2Ecv2"></a>
# 树的平衡性
用户如果使用二叉查找树保存类似于 `[1,2,3,4,5]` 的数据时，可以会使该树变成一个类似链表的只有右子树的结构。使二叉查找树的优势完全丧失，那么怎么才能让整棵树的左右子树保持平衡呢？
<a name="JhKun"></a>
## 旋转
如在二叉查找树中：<br />A 节点**左旋**就是 A 节点倒向左子树<br />对于二叉查找树来说，C 节点成为新的根节点，G 节点依旧是 C 的右子节点，A < C，A 成为 C 的左子节点。F < C 且 F > A，F 成为 A 的右子节点<br /><br />A 节点**右旋**就是 A 节点倒向右子树<br />对于二叉查找树来说，B 节点成为新的根节点，D 节点依旧是 C 的左子节点，B > A，A 成为 B 的左子节点。E < B 且 E > A，E 成为 A 的右子节点<br />
对于所有的树，都可以通过左旋或者右旋操作来达到平衡状态，每种树旋转的操作需要根据自身的特性来转移节点。上面的旋转操作只适用于二叉查找树。
```java
/**
* 平衡二叉查找树
* 带有旋转操作的二叉查找树
*/
public class SelfBalancingBinarySearchTree extends BinarySearchTree {
/**
* 左旋
*
* @param node
* @return
*/
protected Node rotateLeft(Node node) {
Node temp = node.right;
temp.parent = node.parent;
node.right = temp.left;
if (node.right != null) {
node.right.parent = node;
}
temp.left = node;
node.parent = temp;
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
/**
* 右旋
*
* @param node
* @return
*/
protected Node rotateRight(Node node) {
Node temp = node.left;
temp.parent = node.parent;
node.left = temp.right;
if (node.left != null) {
node.left.parent = node;
}
temp.right = node;
node.parent = temp;
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
}
平衡调整
树的平衡性已经能解决了，那么在什么时候检查树现在是不平衡的呢？
对于二叉查找树来说，假设当前是平衡状态：
- 当新增节点时，检查该节点已经改节点的所有父节点是否是平衡的，如果不平衡就通过旋转操作来达到平衡状态
- 当删除某节点时，会找到一个节点 successor 来补充删除节点的位置，就从 successor 节点的父节点开始向上所有父节点检查平衡性
那如何才能确定数当前是否平衡的呢？平衡性被破坏的情况：
LL 型可以右旋调整 和 RR 可以左旋型调整
LR 型调整 和 RL 型调整都可以转为 LL 型 和 RR 型
AVL 树
AVL树本质上还是一棵二叉查找树，它的特点是：
- 本身首先是一棵二叉查找树。
- 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
上面已经说了二叉查找树的平衡性调整，那么根据 AVL 树的定义，只需要在插入新节点或者删除节点时判断树的高度差是否大于平衡因子，如果大于就对树进行调整。始终保持二叉查找树的高度差保持 <= 平衡因子，那么这棵二叉查找树就是一棵 AVL 树
代码实现：
public class AVLTree extends SelfBalancingBinarySearchTree {
/**
* 这里重写了 Node，需要高度来计算树是否平衡
*/
protected static class AVLNode extends Node {
public int height;
public AVLNode(Integer value, Node parent, Node left, Node right) {
super(value, parent, left, right);
}
}
@Override
protected Node createNode(int value, Node parent, Node left, Node right) {
return new AVLNode(value, parent, left, right);
}
@Override
public Node insert(int element) {
Node node = super.insert(element);
rebalance((AVLNode) node);
return node;
}
@Override
public Node delete(int element) {
Node deleteNode = super.search(element);
if (deleteNode == null) return null;
Node successorNode = super.delete(element);
if (successorNode != null) {
AVLNode minimum = (AVLNode) (successorNode.right != null ? getMinimum(successorNode.right) : successorNode);
recomputeHeight(minimum);
rebalance(minimum);
} else {
recomputeHeight((AVLNode) deleteNode.parent);
rebalance((AVLNode) deleteNode.parent);
}
return successorNode;
}
/**
* 判断是否平衡， 如果不平衡就进行调整达到平衡
*
* @param node
*/
private void rebalance(AVLNode node) {
while (node != null) {
Node parent = node.parent;
int leftHeight = node.left == null ? -1 : ((AVLNode) node.left).height;
int rightHeight = node.right == null ? -1 : ((AVLNode) node.right).height;
int nodeBalance = rightHeight - leftHeight;
if (nodeBalance == 2) {
// 不平衡 且 右树比左树高
if (node.right.right != null) {
// RR 型
node = (AVLNode) avlRotateLeft(node);
break;
} else {
// RL 型
node = (AVLNode) doubleRotateRightLeft(node);
break;
}
} else if (nodeBalance == -2) {
// 不平衡 且 左树比右树高
if (node.left.left != null) {
// LL 型
node = (AVLNode) avlRotateRight(node);
} else {
// LR 型
node = (AVLNode) doubleRotateLeftRight(node);
break;
}
} else {
// 平衡
updateHeight(node);
}
node = (AVLNode) parent;
}
}
/**
* LR 型旋转
*
* @param node
* @return
*/
private Node doubleRotateLeftRight(AVLNode node) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
/**
* RL 型旋转
*
* @param node
* @return
*/
private Node doubleRotateRightLeft(AVLNode node) {
node.right = avlRotateRight(node.right);
return avlRotateLeft(node);
}
/**
* AVL 右旋
*
* @param node
* @return
*/
private Node avlRotateRight(Node node) {
Node temp = super.rotateRight(node);
updateHeight((AVLNode) temp.left);
updateHeight((AVLNode) temp);
return temp;
}
/**
* AVL 左旋
*
* @param node
* @return
*/
private Node avlRotateLeft(AVLNode node) {
Node temp = super.rotateLeft(node);
updateHeight((AVLNode) temp.left);
updateHeight((AVLNode) temp);
return temp;
}
/**
* 更新高度
*
* @param node
*/
private void updateHeight(AVLNode node) {
int leftHeight = node.left == null ? -1 : ((AVLNode) node.left).height;
int rightHeight = node.right == null ? -1 : ((AVLNode) node.right).height;
node.height = Math.max(leftHeight, rightHeight) + 1;
}
/**
* 重新计算 node 以及 node 的所有父节点的高度，删除 node 后调用
*
* @param node
*/
private void recomputeHeight(AVLNode node) {
while (node != null) {
node.height = maxHeight((AVLNode) node.left, (AVLNode) node.right) + 1;
node = (AVLNode) node.parent;
}
}
private int maxHeight(AVLNode node1, AVLNode node2) {
if (node1 != null && node2 != null) {
return Math.max(node1.height, node2.height);
} else if (node1 == null) {
return node2 == null ? -1 : node2.height;
} else if (node2 == null) {
return node1 == null ? -1 : node1.height;
}
return -1;
}
}
SB Tree
SB Tree （Size Blanced Tree）是平衡树的一种。
平衡性：每棵子树的大小，不小于其兄弟的子树大小。即：每棵叔叔树的大小，不小于其任何侄子树的大小。
如下图中，B <= max(F, G) 且 C >= max(D, E)
LL 型调整
LL 型，如下图中：
B < max(F, G) ，就将失衡的节点 A 右旋使 节点 B 作为树的头节点。在这个过程中，有可能会导致旋转中改变的子树不平衡，需要将这些被修改的节点也做同样修改，在 LL 型中，发生变化的节点为：
- 节点 A，该节点的左子树发生了变化
- 节点 B，该节点的右子树发生了变化
伪代码如下：
public Node m(Node node) {
// 右旋 返回头节点
node = rightRotate(node);
// 调整节点 A
node.right = m(node.right);
// 调整节点 B
node = m(node);
return node;
}
RR 型调整
RR 型，如下图：
C < max(D, E) ，就将失衡的节点 A 左旋使 节点 C 作为树的头节点。在这个过程中，有可能会导致旋转中改变的子树不平衡，需要将这些被修改的节点也做同样修改，在 RR 型中，发生变化的节点为：
- 节点 A，该节点的右子树发生了变化
- 节点 C，该节点的左子树发生了变化
伪代码如下：
public Node m(Node node) {
// 左旋 返回头节点
node = leftRotate(node);
// 调整节点 A
node.left = m(node.left);
// 调整节点 C
node = m(node);
return node;
}
LR 型调整
LR 型，如下图：
E < max(F, G) ，就要使 节点 E 作为树的头节点。那就需要先将 节点B 左旋然后再将 节点 A 右旋。在这个过程中，有可能会导致旋转中改变的子树不平衡，需要将这些被修改的节点也做同样修改，在 LR 型中，发生变化的节点为：
- 节点 A，该节点的左子树发生了变化
- 节点 B，该节点的右子树发生了变化
- 节点 E，该节点的左右子树都发生了变化
伪代码如下：
public Node m(Node node) {
// 左旋
node.left = leftRotate(node.left);
// 右旋
node = rightRotate(node);
// 调整节点 A
node.left = m(node.left);
// 调整节点 B
node.right = m(node.right);
// 调整节点 E
node = m(node);
return node;
}
RL 型调整
RL 型，如下图：
F < max(D, E) ，就要使 节点 F 作为树的头节点。那就需要先将 节点C 右旋然后再将 节点 A 左旋。在这个过程中，有可能会导致旋转中改变的子树不平衡，需要将这些被修改的节点也做同样修改，在 RL 型中，发生变化的节点为：
- 节点 A，该节点的右子树发生了变化
- 节点 C，该节点的左子树发生了变化
- 节点 F，该节点的左右子树都发生了变化
伪代码如下：
public Node m(Node node) {
// 右旋
node.right = rightRotate(node.right);
// 左旋
node = leftRotate(node);
// 调整节点 A
node.left = m(node.left);
// 调整节点 C
node.right = m(node.right);
// 调整节点 F
node = m(node);
return node;
}
代码实现
综上，知道了 SB-Tree 的平衡性调整，就可以简单实现下，代码如下：
public class SizeBalancedTreeMap1 {
public static class SBTNode<K extends Comparable<K>, V> {
public K key;
public V value;
public SBTNode<K, V> l;
public SBTNode<K, V> r;
public int size;
public SBTNode(K key, V value) {
this.key = key;
this.value = value;
size = 1;
}
}
public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
private SBTNode<K, V> root;
private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
SBTNode<K, V> leftNode = cur.l;
cur.l = leftNode.r;
leftNode.r = cur;
leftNode.size = cur.size;
cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
return leftNode;
}
private SBTNode<K, V> leftRotate(SBTNode<K, V> cur) {
SBTNode<K, V> rightNode = cur.r;
cur.r = rightNode.l;
rightNode.l = cur;
rightNode.size = cur.size;
cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
return rightNode;
}
private SBTNode<K, V> matain(SBTNode<K, V> cur) {
if (cur == null) {
return null;
}
if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
cur = rightRotate(cur);
cur.r = matain(cur.r);
cur = matain(cur);
} else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {
cur.l = leftRotate(cur.l);
cur = rightRotate(cur);
cur.l = matain(cur.l);
cur.r = matain(cur.r);
cur = matain(cur);
} else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {
cur = leftRotate(cur);
cur.l = matain(cur.l);
cur = matain(cur);
} else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {
cur.r = rightRotate(cur.r);
cur = leftRotate(cur);
cur.l = matain(cur.l);
cur.r = matain(cur.r);
cur = matain(cur);
}
return cur;
}
private SBTNode<K, V> findLastIndex(K key) {
SBTNode<K, V> pre = root;
SBTNode<K, V> cur = root;
while (cur != null) {
pre = cur;
if (key.compareTo(cur.key) == 0) {
break;
} else if (key.compareTo(cur.key) < 0) {
cur = cur.l;
} else {
cur = cur.r;
}
}
return pre;
}
private SBTNode<K, V> findLastNoSmallIndex(K key) {
SBTNode<K, V> ans = null;
SBTNode<K, V> cur = root;
while (cur != null) {
if (key.compareTo(cur.key) == 0) {
ans = cur;
break;
} else if (key.compareTo(cur.key) < 0) {
ans = cur;
cur = cur.l;
} else {
cur = cur.r;
}
}
return ans;
}
private SBTNode<K, V> findLastNoBigIndex(K key) {
SBTNode<K, V> ans = null;
SBTNode<K, V> cur = root;
while (cur != null) {
if (key.compareTo(cur.key) == 0) {
ans = cur;
break;
} else if (key.compareTo(cur.key) < 0) {
cur = cur.l;
} else {
ans = cur;
cur = cur.r;
}
}
return ans;
}
private SBTNode<K, V> add(SBTNode<K, V> cur, K key, V value) {
if (cur == null) {
return new SBTNode<K, V>(key, value);
} else {
cur.size++;
if (key.compareTo(cur.key) < 0) {
cur.l = add(cur.l, key, value);
} else {
cur.r = add(cur.r, key, value);
}
return matain(cur);
}
}
private SBTNode<K, V> delete(SBTNode<K, V> cur, K key) {
cur.size--;
if (key.compareTo(cur.key) > 0) {
cur.r = delete(cur.r, key);
} else if (key.compareTo(cur.key) < 0) {
cur.l = delete(cur.l, key);
} else {
if (cur.l == null && cur.r == null) {
// free cur memory -> C++
cur = null;
} else if (cur.l == null && cur.r != null) {
// free cur memory -> C++
cur = cur.r;
} else if (cur.l != null && cur.r == null) {
// free cur memory -> C++
cur = cur.l;
} else {
SBTNode<K, V> pre = null;
SBTNode<K, V> des = cur.r;
des.size--;
while (des.l != null) {
pre = des;
des = des.l;
des.size--;
}
if (pre != null) {
pre.l = des.r;
des.r = cur.r;
}
des.l = cur.l;
des.size = des.l.size + des.r.size + 1;
// free cur memory -> C++
cur = des;
}
}
return cur;
}
private SBTNode<K, V> getIndex(SBTNode<K, V> cur, int kth) {
if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
return cur;
} else if (kth <= (cur.l != null ? cur.l.size : 0)) {
return getIndex(cur.l, kth);
} else {
return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
}
}
public int size() {
return root == null ? 0 : root.size;
}
public boolean containsKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNode = findLastIndex(key);
return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
}
public void put(K key, V value) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNode = findLastIndex(key);
if (lastNode != null && key.compareTo(lastNode.key) == 0) {
lastNode.value = value;
} else {
root = add(root, key, value);
}
}
public void remove(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
if (containsKey(key)) {
root = delete(root, key);
}
}
public K getIndexKey(int index) {
if (index < 0 || index >= this.size()) {
throw new RuntimeException("invalid parameter.");
}
return getIndex(root, index + 1).key;
}
public V getIndexValue(int index) {
if (index < 0 || index >= this.size()) {
throw new RuntimeException("invalid parameter.");
}
return getIndex(root, index + 1).value;
}
public V get(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNode = findLastIndex(key);
if (lastNode != null && key.compareTo(lastNode.key) == 0) {
return lastNode.value;
} else {
return null;
}
}
public K firstKey() {
if (root == null) {
return null;
}
SBTNode<K, V> cur = root;
while (cur.l != null) {
cur = cur.l;
}
return cur.key;
}
public K lastKey() {
if (root == null) {
return null;
}
SBTNode<K, V> cur = root;
while (cur.r != null) {
cur = cur.r;
}
return cur.key;
}
public K floorKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
return lastNoBigNode == null ? null : lastNoBigNode.key;
}
public K ceilingKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
SBTNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
return lastNoSmallNode == null ? null : lastNoSmallNode.key;
}
}
// for test
public static void printAll(SBTNode<String, Integer> head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
// for test
public static void printInOrder(SBTNode<String, Integer> head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.r, height + 1, "v", len);
String val = to + "(" + head.key + "," + head.value + ")" + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.l, height + 1, "^", len);
}
// for test
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
SizeBalancedTreeMap<String, Integer> sbt = new SizeBalancedTreeMap<String, Integer>();
sbt.put("d", 4);
sbt.put("c", 3);
sbt.put("a", 1);
sbt.put("b", 2);
// sbt.put("e", 5);
sbt.put("g", 7);
sbt.put("f", 6);
sbt.put("h", 8);
sbt.put("i", 9);
sbt.put("a", 111);
System.out.println(sbt.get("a"));
sbt.put("a", 1);
System.out.println(sbt.get("a"));
for (int i = 0; i < sbt.size(); i++) {
System.out.println(sbt.getIndexKey(i) + " , " + sbt.getIndexValue(i));
}
printAll(sbt.root);
System.out.println(sbt.firstKey());
System.out.println(sbt.lastKey());
System.out.println(sbt.floorKey("g"));
System.out.println(sbt.ceilingKey("g"));
System.out.println(sbt.floorKey("e"));
System.out.println(sbt.ceilingKey("e"));
System.out.println(sbt.floorKey(""));
System.out.println(sbt.ceilingKey(""));
System.out.println(sbt.floorKey("j"));
System.out.println(sbt.ceilingKey("j"));
sbt.remove("d");
printAll(sbt.root);
sbt.remove("f");
printAll(sbt.root);
}
}
另一种实现
package com.example.test.advance.sorted;
import java.util.ArrayList;
public class SizeBalancedTreeMap2 {
public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
private int root;
private int len;
private int[] left;
private int[] right;
private int[] size;
private ArrayList<K> keys;
private ArrayList<V> values;
public SizeBalancedTreeMap(int init) {
left = new int[init + 1];
right = new int[init + 1];
size = new int[init + 1];
keys = new ArrayList<K>();
values = new ArrayList<V>();
keys.add(null);
values.add(null);
root = 0;
len = 0;
}
private int rightRotate(int index) {
int iLeft = left[index];
left[index] = right[iLeft];
right[iLeft] = index;
size[iLeft] = size[index];
size[index] = size[left[index]] + size[right[index]] + 1;
return iLeft;
}
private int leftRotate(int index) {
int iRight = right[index];
right[index] = left[iRight];
left[iRight] = index;
size[iRight] = size[index];
size[index] = size[left[index]] + size[right[index]] + 1;
return iRight;
}
private int matain(int index) {
if (size[left[left[index]]] > size[right[index]]) {
index = rightRotate(index);
right[index] = matain(right[index]);
index = matain(index);
} else if (size[right[left[index]]] > size[right[index]]) {
left[index] = leftRotate(left[index]);
index = rightRotate(index);
left[index] = matain(left[index]);
right[index] = matain(right[index]);
index = matain(index);
} else if (size[right[right[index]]] > size[left[index]]) {
index = leftRotate(index);
left[index] = matain(left[index]);
index = matain(index);
} else if (size[left[right[index]]] > size[left[index]]) {
right[index] = rightRotate(right[index]);
index = leftRotate(index);
left[index] = matain(left[index]);
right[index] = matain(right[index]);
index = matain(index);
}
return index;
}
private int findLastIndex(K key) {
int pre = root;
int cur = root;
while (cur != 0) {
pre = cur;
if (key.compareTo(keys.get(cur)) == 0) {
break;
} else if (key.compareTo(keys.get(cur)) < 0) {
cur = left[cur];
} else {
cur = right[cur];
}
}
return pre;
}
private int findLastNoSmallIndex(K key) {
int ans = 0;
int cur = root;
while (cur != 0) {
if (key.compareTo(keys.get(cur)) == 0) {
ans = cur;
break;
} else if (key.compareTo(keys.get(cur)) < 0) {
ans = cur;
cur = left[cur];
} else {
cur = right[cur];
}
}
return ans;
}
private int findLastNoBigIndex(K key) {
int ans = 0;
int cur = root;
while (cur != 0) {
if (key.compareTo(keys.get(cur)) == 0) {
ans = cur;
break;
} else if (key.compareTo(keys.get(cur)) < 0) {
cur = left[cur];
} else {
ans = cur;
cur = right[cur];
}
}
return ans;
}
private int add(int index, K key, V value) {
if (index == 0) {
index = ++len;
keys.add(key);
values.add(value);
size[index] = 1;
left[index] = 0;
right[index] = 0;
return index;
} else {
size[index]++;
if (key.compareTo(keys.get(index)) < 0) {
left[index] = add(left[index], key, value);
} else {
right[index] = add(right[index], key, value);
}
return matain(index);
}
}
private int getIndex(int index, int kth) {
if (kth == size[left[index]] + 1) {
return index;
} else if (kth <= size[left[index]]) {
return getIndex(left[index], kth);
} else {
return getIndex(right[index], kth - size[left[index]] - 1);
}
}
public int size() {
return len;
}
public boolean containsKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
int lastIndex = findLastIndex(key);
return lastIndex != 0 && key.compareTo(keys.get(lastIndex)) == 0 ? true : false;
}
public void put(K key, V value) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
if (len == size.length - 1) {
throw new RuntimeException("size balanced tree is full.");
}
int lastIndex = findLastIndex(key);
if (lastIndex != 0 && key.compareTo(keys.get(lastIndex)) == 0) {
values.set(lastIndex, value);
} else {
root = add(root, key, value);
}
}
public K getIndexKey(int index) {
if (index < 0 || index >= len) {
throw new RuntimeException("invalid parameter.");
}
return keys.get(getIndex(root, index + 1));
}
public V getIndexValue(int index) {
if (index < 0 || index >= len) {
throw new RuntimeException("invalid parameter.");
}
return values.get(getIndex(root, index + 1));
}
public V get(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
int lastIndex = findLastIndex(key);
if (lastIndex != 0 && key.compareTo(keys.get(lastIndex)) == 0) {
return values.get(lastIndex);
} else {
return null;
}
}
public K firstKey() {
int cur = root;
while (left[cur] != 0) {
cur = left[cur];
}
return cur == 0 ? null : keys.get(cur);
}
public K lastKey() {
int cur = root;
while (right[cur] != 0) {
cur = right[cur];
}
return cur == 0 ? null : keys.get(cur);
}
public K floorKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
int lastNoBigIndex = findLastNoBigIndex(key);
return lastNoBigIndex == 0 ? null : keys.get(lastNoBigIndex);
}
public K ceilingKey(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
int lastNoSmallIndex = findLastNoSmallIndex(key);
return lastNoSmallIndex == 0 ? null : keys.get(lastNoSmallIndex);
}
}
public static void main(String[] args) {
SizeBalancedTreeMap<String, Integer> sbt = new SizeBalancedTreeMap<String, Integer>(10000);
sbt.put("pos", 512);
sbt.put("zyp", 7123);
sbt.put("unz", 542);
sbt.put("abc", 5113);
sbt.put("yzk", 665);
sbt.put("fgi", 38776);
sbt.put("bke", 2500540);
sbt.put("lmn", 44334);
sbt.put("abc", 11);
sbt.put("abc", 111);
for (int i = 0; i < sbt.size(); i++) {
System.out.println(sbt.getIndexKey(i) + " , " + sbt.getIndexValue(i));
}
System.out.println(sbt.get("abc"));
System.out.println(sbt.firstKey());
System.out.println(sbt.lastKey());
System.out.println(sbt.floorKey("bke"));
System.out.println(sbt.ceilingKey("bke"));
System.out.println(sbt.floorKey("ooo"));
System.out.println(sbt.ceilingKey("ooo"));
System.out.println(sbt.floorKey("aaa"));
System.out.println(sbt.ceilingKey("aaa"));
System.out.println(sbt.floorKey("zzz"));
System.out.println(sbt.ceilingKey("zzz"));
}
}
红黑树
可以直接看：
红黑树的定义（特性）：
- 每个节点要么是【黑色】要么是【红色】
- 根节点是【黑色】
- 每个叶子节点（NIL）都是【黑色】
- 每个【红色】节点的两个子节点一定都是【黑色】（红色节点不能相邻）
- 任意一个节点的路径到叶子节点所包含的【黑色】节点的数量是相同的。这个也称之为【黑色完美平衡】
- 新插入的节点必须是【红色】->为什么？如果新插入的节点是【黑色】，那不管是在插入到那里，一定会破坏黑色完美平衡的，因为任意一个节点的路径到叶子节点的黑色节点的数量肯定不一样了（第 6 点我自己加的，实际特性的定义是前 5 个）
检查的时机和调整方式和AVL树一样，只是要遵循红黑树的特性来完成旋转。这里就不介绍了。
代码实现：
/**
* Not implemented by zuochengyun
* <p>
* Red-Black tree implementation. From Introduction to Algorithms 3rd edition.
*
* @author Ignas Lelys
* @created May 6, 2011
*/
public class RedBlackTree extends SelfBalancingBinarySearchTree {
protected enum ColorEnum {
RED,
BLACK
}
;
protected static final RedBlackNode nilNode = new RedBlackNode(null, null, null, null, ColorEnum.BLACK);
@Override
public Node insert(int element) {
Node newNode = super.insert(element);
newNode.left = nilNode;
newNode.right = nilNode;
root.parent = nilNode;
insertRBFixup((RedBlackNode) newNode);
return newNode;
}
/**
* Slightly modified delete routine for red-black tree.
* <p>
* {@inheritDoc}
*/
@Override
public Node delete(Node deleteNode) {
Node replaceNode = null; // track node that replaces removedOrMovedNode
if (deleteNode != null && deleteNode != nilNode) {
Node removedOrMovedNode = deleteNode; // same as deleteNode if it has only one child, and otherwise it replaces deleteNode
ColorEnum removedOrMovedNodeColor = ((RedBlackNode) removedOrMovedNode).color;
if (deleteNode.left == nilNode) {
replaceNode = deleteNode.right;
rbTreeTransplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == nilNode) {
replaceNode = deleteNode.left;
rbTreeTransplant(deleteNode, deleteNode.left);
} else {
removedOrMovedNode = getMinimum(deleteNode.right);
removedOrMovedNodeColor = ((RedBlackNode) removedOrMovedNode).color;
replaceNode = removedOrMovedNode.right;
if (removedOrMovedNode.parent == deleteNode) {
replaceNode.parent = removedOrMovedNode;
} else {
rbTreeTransplant(removedOrMovedNode, removedOrMovedNode.right);
removedOrMovedNode.right = deleteNode.right;
removedOrMovedNode.right.parent = removedOrMovedNode;
}
rbTreeTransplant(deleteNode, removedOrMovedNode);
removedOrMovedNode.left = deleteNode.left;
removedOrMovedNode.left.parent = removedOrMovedNode;
((RedBlackNode) removedOrMovedNode).color = ((RedBlackNode) deleteNode).color;
}
size--;
if (removedOrMovedNodeColor == ColorEnum.BLACK) {
deleteRBFixup((RedBlackNode) replaceNode);
}
}
return replaceNode;
}
@Override
protected Node createNode(int value, Node parent, Node left, Node right) {
return new RedBlackNode(value, parent, left, right, ColorEnum.RED);
}
/**
* {@inheritDoc}
*/
@Override
public Node getMinimum(Node node) {
while (node.left != nilNode) {
node = node.left;
}
return node;
}
/**
* {@inheritDoc}
*/
@Override
public Node getMaximum(Node node) {
while (node.right != nilNode) {
node = node.right;
}
return node;
}
/**
* {@inheritDoc}
*/
@Override
protected Node rotateLeft(Node node) {
Node temp = node.right;
temp.parent = node.parent;
node.right = temp.left;
if (node.right != nilNode) {
node.right.parent = node;
}
temp.left = node;
node.parent = temp;
// temp took over node's place so now its parent should point to temp
if (temp.parent != nilNode) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
/**
* {@inheritDoc}
*/
@Override
protected Node rotateRight(Node node) {
Node temp = node.left;
temp.parent = node.parent;
node.left = temp.right;
if (node.left != nilNode) {
node.left.parent = node;
}
temp.right = node;
node.parent = temp;
// temp took over node's place so now its parent should point to temp
if (temp.parent != nilNode) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
/**
* Similar to original transplant() method in BST but uses nilNode instead of null.
*/
private Node rbTreeTransplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == nilNode) {
this.root = newNode;
} else if (nodeToReplace == nodeToReplace.parent.left) {
nodeToReplace.parent.left = newNode;
} else {
nodeToReplace.parent.right = newNode;
}
newNode.parent = nodeToReplace.parent;
return newNode;
}
/**
* Restores Red-Black tree properties after delete if needed.
*/
private void deleteRBFixup(RedBlackNode x) {
while (x != root && isBlack(x)) {
if (x == x.parent.left) {
RedBlackNode w = (RedBlackNode) x.parent.right;
if (isRed(w)) { // case 1 - sibling is red
w.color = ColorEnum.BLACK;
((RedBlackNode) x.parent).color = ColorEnum.RED;
rotateLeft(x.parent);
w = (RedBlackNode) x.parent.right; // converted to case 2, 3 or 4
}
// case 2 sibling is black and both of its children are black
if (isBlack(w.left) && isBlack(w.right)) {
w.color = ColorEnum.RED;
x = (RedBlackNode) x.parent;
} else if (w != nilNode) {
if (isBlack(w.right)) { // case 3 sibling is black and its left child is red and right child is black
((RedBlackNode) w.left).color = ColorEnum.BLACK;
w.color = ColorEnum.RED;
rotateRight(w);
w = (RedBlackNode) x.parent.right;
}
w.color = ((RedBlackNode) x.parent).color; // case 4 sibling is black and right child is red
((RedBlackNode) x.parent).color = ColorEnum.BLACK;
((RedBlackNode) w.right).color = ColorEnum.BLACK;
rotateLeft(x.parent);
x = (RedBlackNode) root;
} else {
x.color = ColorEnum.BLACK;
x = (RedBlackNode) x.parent;
}
} else {
RedBlackNode w = (RedBlackNode) x.parent.left;
if (isRed(w)) { // case 1 - sibling is red
w.color = ColorEnum.BLACK;
((RedBlackNode) x.parent).color = ColorEnum.RED;
rotateRight(x.parent);
w = (RedBlackNode) x.parent.left; // converted to case 2, 3 or 4
}
// case 2 sibling is black and both of its children are black
if (isBlack(w.left) && isBlack(w.right)) {
w.color = ColorEnum.RED;
x = (RedBlackNode) x.parent;
} else if (w != nilNode) {
if (isBlack(w.left)) { // case 3 sibling is black and its right child is red and left child is black
((RedBlackNode) w.right).color = ColorEnum.BLACK;
w.color = ColorEnum.RED;
rotateLeft(w);
w = (RedBlackNode) x.parent.left;
}
w.color = ((RedBlackNode) x.parent).color; // case 4 sibling is black and left child is red
((RedBlackNode) x.parent).color = ColorEnum.BLACK;
((RedBlackNode) w.left).color = ColorEnum.BLACK;
rotateRight(x.parent);
x = (RedBlackNode) root;
} else {
x.color = ColorEnum.BLACK;
x = (RedBlackNode) x.parent;
}
}
}
}
private boolean isBlack(Node node) {
return node != null ? ((RedBlackNode) node).color == ColorEnum.BLACK : false;
}
private boolean isRed(Node node) {
return node != null ? ((RedBlackNode) node).color == ColorEnum.RED : false;
}
/**
* Restores Red-Black tree properties after insert if needed. Insert can
* break only 2 properties: root is red or if node is red then children must
* be black.
*/
private void insertRBFixup(RedBlackNode currentNode) {
// current node is always RED, so if its parent is red it breaks
// Red-Black property, otherwise no fixup needed and loop can terminate
while (currentNode.parent != root && ((RedBlackNode) currentNode.parent).color == ColorEnum.RED) {
RedBlackNode parent = (RedBlackNode) currentNode.parent;
RedBlackNode grandParent = (RedBlackNode) parent.parent;
if (parent == grandParent.left) {
RedBlackNode uncle = (RedBlackNode) grandParent.right;
// case1 - uncle and parent are both red
// re color both of them to black
if (((RedBlackNode) uncle).color == ColorEnum.RED) {
parent.color = ColorEnum.BLACK;
uncle.color = ColorEnum.BLACK;
grandParent.color = ColorEnum.RED;
// grandparent was recolored to red, so in next iteration we
// check if it does not break Red-Black property
currentNode = grandParent;
}
// case 2/3 uncle is black - then we perform rotations
else {
if (currentNode == parent.right) { // case 2, first rotate left
currentNode = parent;
rotateLeft(currentNode);
}
// do not use parent
parent.color = ColorEnum.BLACK; // case 3
grandParent.color = ColorEnum.RED;
rotateRight(grandParent);
}
} else if (parent == grandParent.right) {
RedBlackNode uncle = (RedBlackNode) grandParent.left;
// case1 - uncle and parent are both red
// re color both of them to black
if (((RedBlackNode) uncle).color == ColorEnum.RED) {
parent.color = ColorEnum.BLACK;
uncle.color = ColorEnum.BLACK;
grandParent.color = ColorEnum.RED;
// grandparent was recolored to red, so in next iteration we
// check if it does not break Red-Black property
currentNode = grandParent;
}
// case 2/3 uncle is black - then we perform rotations
else {
if (currentNode == parent.left) { // case 2, first rotate right
currentNode = parent;
rotateRight(currentNode);
}
// do not use parent
parent.color = ColorEnum.BLACK; // case 3
grandParent.color = ColorEnum.RED;
rotateLeft(grandParent);
}
}
}
// ensure root is black in case it was colored red in fixup
((RedBlackNode) root).color = ColorEnum.BLACK;
}
protected static class RedBlackNode extends Node {
public ColorEnum color;
public RedBlackNode(Integer value, Node parent, Node left, Node right, ColorEnum color) {
super(value, parent, left, right);
this.color = color;
}
}
}
若有收获，就点个赞吧
0 人点赞
