- 1 有序表原理及扩展
1 有序表原理及扩展
1.1 搜索二叉树
经典的搜索二叉树，是没有重复值的，任何节点为头的数，左孩子都比自己小，右孩子都比自己大
允许重复值的改进的搜索二叉树，可以在每个节点上增加一个统计词频的数据项。表示出现了几次；但是不可相等的放到左右孩子上，搜索二叉树变平衡时，会影响后续的旋转
1、搜索二叉树一定要说明以什么标准来排序
2、经典的搜索二叉树，树上没有重复的用来排序的key值
3、如果有重复节点的需求，可以在一个节点内部增加数据项
1.2 搜索二叉树的增删改查
1.2.1 搜索二叉树的查找和添加
- 查找
搜索二叉树查询key（查询某个key存在还是不存在），当前节点比自己小，到右子树上去找，当前节点比自己大，到其左孩子上去找，越界，说明不存在
1、如果当前节点的value==key，返回true
2、如果当前节点的value<key，当前节点向左移动
3、如果当前节点的value>key，当前节点向右移动
4、如果当前节点变成null，返回false
- 添加
和查询过程一样，但当前节点滑到空的时候，就插入在这里
- 删除
1、先找到key所在的节点
2、如果该节点没有左孩子、没有右孩子，直接删除即可（好理解）
3、如果该节点有左孩子、没有右孩子，直接用左孩子顶替该节点（好理解）
4、如果该节点没有左孩子、有右孩子，直接用右孩子顶替该节点（好理解）
5、如果该节点有左孩子、有右孩子，用该节点后继节点顶替该节点（需要旋转调整，没法有左右孩子去替换，原因是左右孩子也有左右孩子）
==一个节点的后继节点，就是该节点右孩子的最左的那个节点。==
graph TD
2-->1
2-->5
5-->3
5-->10
10-->8
10-->13
8-->6
6-->7
比如我要删除5节点，那么5节点的后继节点就是其右子树的最左的孩子，也就是6。把6替换掉5，6的右孩子给它父亲作为左孩子，得到
graph TD
2-->1
2-->6
6-->3
6-->10
10-->8
10-->13
8-->7
package class05;
/**
* Not implemented by zuochengyun
*
* Abstract binary search tree implementation. Its basically fully implemented
* binary search tree, just template method is provided for creating Node (other
* trees can have slightly different nodes with more info). This way some code
* from standart binary search tree can be reused for other kinds of binary
* trees.
*
* @author Ignas Lelys
* @created Jun 29, 2011
*
*/
public class AbstractBinarySearchTree {
/** Root node where whole tree starts. */
public Node root;
/** Tree size. */
protected int size;
/**
* Because this is abstract class and various trees have different
* additional information on different nodes subclasses uses this abstract
* method to create nodes (maybe of class {@link Node} or maybe some
* different node sub class).
*
* @param value
* Value that node will have.
* @param parent
* Node's parent.
* @param left
* Node's left child.
* @param right
* Node's right child.
* @return Created node instance.
*/
protected Node createNode(int value, Node parent, Node left, Node right) {
return new Node(value, parent, left, right);
}
/**
* Finds a node with concrete value. If it is not found then null is
* returned.
* 查找节点
*
* @param element
* Element value.
* @return Node with value provided, or null if not found.
*/
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;
}
/**
* Insert new element to tree.
* 插入一个节点
*
* @param element
* Element to insert.
*/
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 > newNode.value) {
insertParentNode.left = newNode;
} else {
insertParentNode.right = newNode;
}
size++;
return newNode;
}
/**
* Removes element if node with such value exists.
* 删除节点，每个节点由于加入向上的指针，那么旋转的时候会方便些
*
* @param element
* Element value to remove.
*
* @return New node that is in place of deleted node. Or null if element for
* delete was not found.
*/
public Node delete(int element) {
Node deleteNode = search(element);
if (deleteNode != null) {
return delete(deleteNode);
} else {
return null;
}
}
/**
* Delete logic when node is already found.
*
* @param deleteNode
* Node that needs to be deleted.
*
* @return New node that is in place of deleted node. Or null if element for
* delete was not found.
* 注意，删除方法返回的是删除后接管删除节点的位置的节点，返回
*/
protected Node delete(Node deleteNode) {
if (deleteNode != null) {
Node nodeToReturn = null;
if (deleteNode != null) {
if (deleteNode.left == null) {
// 左孩子为空，右孩子直接替换该节点，达到删除的效果
// transplant(a,b) b去替换a的环境，a断连掉，把b返回
nodeToReturn = transplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == null) {
// 右孩子为空，左孩子直接替换，达到删除的目的
nodeToReturn = transplant(deleteNode, deleteNode.left);
} else {
// 否则，要删除的节点既有左孩子，又有右孩子，找右子树的最左的孩子
Node successorNode = getMinimum(deleteNode.right);
// 要删除的节点的右孩子，有左孩子。最左孩子的右孩子要它父亲来接管
if (successorNode.parent != deleteNode) {
transplant(successorNode, successorNode.right);
successorNode.right = deleteNode.right;
successorNode.right.parent = successorNode;
}
// 如果要删除的节点的右孩子，没有左孩子。直接用要删除的节点的右孩子进行替换即可
transplant(deleteNode, successorNode);
successorNode.left = deleteNode.left;
successorNode.left.parent = successorNode;
nodeToReturn = successorNode;
}
size--;
}
return nodeToReturn;
}
return null;
}
/**
* Put one node from tree (newNode) to the place of another (nodeToReplace).
*
* @param nodeToReplace
* Node which is replaced by newNode and removed from tree.
* @param newNode
* New node.
*
* @return New replaced node.
*/
private Node transplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == null) {
this.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;
}
/**
* @param element
* @return true if tree contains element.
*/
public boolean contains(int element) {
return search(element) != null;
}
/**
* @return Minimum element in tree.
*/
public int getMinimum() {
return getMinimum(root).value;
}
/**
* @return Maximum element in tree.
*/
public int getMaximum() {
return getMaximum(root).value;
}
/**
* Get next element element who is bigger than provided element.
*
* @param element
* Element for whom descendand element is searched
* @return Successor value.
*/
// TODO Predecessor
public int getSuccessor(int element) {
return getSuccessor(search(element)).value;
}
/**
* @return Number of elements in the tree.
*/
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);
}
}
}
protected Node getMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
protected Node getMaximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}
protected Node getSuccessor(Node node) {
// if there is right branch, then successor is leftmost node of that
// subtree
if (node.right != null) {
return getMinimum(node.right);
} else { // otherwise it is a lowest ancestor whose left child is also
// ancestor of node
Node currentNode = node;
Node parentNode = node.parent;
while (parentNode != null && currentNode == parentNode.right) {
// go up until we find parent that currentNode is not in right
// subtree.
currentNode = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
// -------------------------------- 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 ? " | " : " "));
}
}
public static class Node {
public Node(Integer value, Node parent, Node left, Node right) {
super();
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
public Integer value;
public Node parent;
public Node left;
public Node right;
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((value == null) ? 0 : value.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
}
}
1.3 传统搜索二叉树存在的问题
1）基础的搜索二叉树，添加、删除时候不照顾平衡性
2）数据状况很差时，性能就很差
==给搜索二叉树引入两个动作：左旋、右旋==
输入状况，决定性能。比如输入状况构建出来的树，严重不平衡。极端情况是只有一条通往底部的路径，高度为n;
平衡二叉树的定义，任何子树，左子树的高度和右子树的高度差，不大于1。所以对于n个节点，平衡二叉树的高度，就是logN
1.3.1 平衡搜索二叉树
平衡搜索二叉树，就是在插入和删除的过程中，动态的保持平衡性。保持平衡的代价保持在logN。平衡搜索二叉树的实现由很多，红黑树只是其中一种
1.3.2 左旋和右旋
左旋和右旋针对头结点而言的，即对哪个头结点进行左旋还是右旋；顾名思义如果对头结点为a的子树右旋，那么a倒到右边，a的左孩子顶上来，到a原来的位置上去。a原来左孩子的右孩子，现在当做a的左孩子，如下图
graph TD
a-->b
a-->c
c-->d
c-->e
b-->f
b-->g
a右旋，得到：
graph TD
b-->f
b-->a
a-->g
a-->c
c-->d
c-->e
同理，a左旋，得到：
graph TD
c-->a
c-->e
a-->b
a-->d
b-->f
b-->g
带左旋和右旋的搜索二叉树，在经典搜索二叉树上做的扩展，继承经典搜索二叉树。
package class05;
/**
* Not implemented by zuochengyun
*
* Abstract class for self balancing binary search trees. Contains some methods
* that is used for self balancing trees.
*
* @author Ignas Lelys
* @created Jul 24, 2011
*
*/
public abstract class AbstractSelfBalancingBinarySearchTree
extends AbstractBinarySearchTree {
/**
* Rotate to the left.
*
* @param node Node on which to rotate.
* @return Node that is in place of provided node after rotation.
*/
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;
// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
/**
* Rotate to the right.
*
* @param node Node on which to rotate.
* @return Node that is in place of provided node after rotation.
*/
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;
// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
}
1.4 有序表
在Java中，就是TreeMap，有序表和Hash表（HashMap）的操作类似，但是有序表中自动把我们的key排好了顺序，我们也可以传入比较器，自定义对比和排序的规则；我们可以通过TreeMap直接得到最大节点和最小节点，也可以获取大于某个值的第一个Key是什么等等
为什么TreeMap可以做到有序，原因是TreeMap的底层是一个平衡搜索二叉树
- Hash表和有序表对比
1、HashMap的所有操作是O(1)的，TreeMap的所有操作是O(logN)
2、使用有序表的Key必须是可以比较的，没法自然比较的需要传入自定义比较器
1.5 有序表的实现（AVL树，SB树，红黑树）
在有序表中，有序表是一种规范，类似于接口名。规范为key要按序组织，所有操作要是O(logN)等。各种树结构可以实现有序表的功能。其中红黑树只是有序表的一个实现
==AVL树，SB树，红黑树，都是有序表的一种实现。都是平衡搜索二叉树，这三种树在功能和时间复杂度上几乎无差别，在实现细节上也就是在常数时间上，会有差别。三种树调整检查哪些节点的平衡性相同，下文进行说明。每种树针对每个节点的平衡性调整不同，但是都是使用左旋和右旋两个动作==
- AVL树，SB树，红黑树的共性
1）都是搜索二叉树
2）插入、删除、查询（一切查询）搜索二叉树怎么做，这些结构都这么做
3）使用调整的基本动作都只有左旋、右旋
4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查
5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)
- AVL树，SB树，红黑树不同之处
1）平衡性的约束不同
AVL树最严格、SB树稍宽松、红黑树最宽松
2）插入、删除和搜索二叉树一样，但是额外，做各自的平衡性调整。各自的平衡性调整所使用的动作都是左旋或者右旋
1.5.1 AVL树
是这三个平衡搜索二叉树中，平衡性最严格的，左树高度和右树高度的绝对值，严格小于2
AVL树在插入节点的时候，只会向上检查节点的平衡性有没有被破坏。删除节点也一样，只会检查删除的那个节点向上的那条链上的节点有没被破坏。删除的时候，如果被删除的节点没有左右孩子那么直接检查，如果有右孩子，是去检查后继节点原来所在的位置的向上节点的平衡性
==实质上三种树删除和插入节点，检查哪些节点需要调整平衡都是这样的查找规则，对于删除来说，只有左树和只有右树没影响，如果左右树都存在，是去检查后继节点原来所在的位置向上的平衡性。只是具体到某个节点平衡性的处理上，三种树不一样==
1.5.1.1 AVL树针对某个节点的平衡性处理
| 1、该节点左树高度和右树高度差的绝对值 | L-R | ，小于2。不违规，无须调整 |
| 2、 | L-R | 大于1，说明要不然左树高度大了，要不然右树高度大了。而且之前的每一步都进行了调整，所以高度差不会超过2。高度不平衡对应四种情况，被称为RR形违规，RL形违规，LL形违规，LR形违规。首字母表示左树变高了还是右树变高了，比如RR和RL都表示经过插入或者删除，右树的高度变大了 |
RR表示，右子节点的右树过长，RL表示右子节点的左树过长。同理LL表示左子节点的左子树高度过长导致，LR表示左子节点的右树高度过长导致的不平衡
- LL形违规，对该节点进行一次右旋即可
graph TD
x-->y
x-->p
y-->z
y-->t
z-->k
右旋后得到：
graph TD
y-->z
y-->x
z-->k
x-->t
x-->p
-
同理RR形违规，对该节点进行一次左旋即可
-
LR形,让底部的孙子节点，来到顶部来。
下面例子，想办法让x的孙子节点t节点来到顶部，先对y节点进行一次左旋,再对x节点做一次右旋
graph TD
x-->y
x-->p
y-->z
y-->t
t-->k
先对y节点进行一次左旋
graph TD
x-->t
x-->p
y-->z
t-->y
t-->k
再对x节点做一次右旋
graph TD
t-->y
t-->x
x-->k
x-->p
y-->z
原x的孙子节点t此时，调整到的顶部
- 同理RL形,也是让超过长度的那一侧底部的孙子节点，来到顶部来。
==LL形和RR形旋转一次O(1)，LR和RL形旋转两次，也是O(1)。那么即使删除或者添加的节点影响的整个向上的链路，整体复杂度也是O(logN)==
AVL树继承自带左右旋的平衡搜索二叉树，在此基础上做的扩展，code如下：
package class05;
/**
* Not implemented by zuochengyun
*
* AVL tree implementation.
*
* In computer science, an AVL tree is a self-balancing binary search tree, and
* it was the first such data structure to be invented.[1] In an AVL tree, the
* heights of the two child subtrees of any node differ by at most one. Lookup,
* insertion, and deletion all take O(log n) time in both the average and worst
* cases, where n is the number of nodes in the tree prior to the operation.
* Insertions and deletions may require the tree to be rebalanced by one or more
* tree rotations.
*
* @author Ignas Lelys
* @created Jun 28, 2011
*
*/
public class AVLTree extends AbstractSelfBalancingBinarySearchTree {
/**
* @see trees.AbstractBinarySearchTree#insert(int)
*
* AVL tree insert method also balances tree if needed. Additional height
* parameter on node is used to track if one subtree is higher than other
* by more than one, if so AVL tree rotations is performed to regain
* balance of the tree.
*/
@Override
public Node insert(int element) {
Node newNode = super.insert(element);
// 对有影响的节点，顺着parent指针向上做平衡性检查调整
rebalance((AVLNode) newNode);
return newNode;
}
/**
* @see trees.AbstractBinarySearchTree#delete(int)
*/
@Override
public Node delete(int element) {
// 先查出来需要删的值，存在的话进行删除
Node deleteNode = super.search(element);
if (deleteNode != null) {
// 先调用父类，也就是带左右旋的平衡搜索二叉树的删除，把删除的节点后哪个节点接管了被删除的位置，该节点返回
Node successorNode = super.delete(deleteNode);
// 接管的节点不为空，检查是哪一种替换的方式，左孩子接管or右孩子接管，or后继节点接管，or既没有左孩子有没有右孩子直接删除
if (successorNode != null) {
// if replaced from getMinimum(deleteNode.right) then come back there and update
// heights
AVLNode minimum = successorNode.right != null ? (AVLNode) getMinimum(successorNode.right)
: (AVLNode) successorNode;
// 重新计算高度（重要）
recomputeHeight(minimum);
// 重新进行平衡（重要）
rebalance((AVLNode) minimum);
} else { // 并没有任何节点替代被删除节点的位置，被删除节点是孤零零被删除的
recomputeHeight((AVLNode) deleteNode.parent);
rebalance((AVLNode) deleteNode.parent);
}
return successorNode;
}
return null;
}
/**
* @see trees.AbstractBinarySearchTree#createNode(int,
* trees.AbstractBinarySearchTree.Node,
* trees.AbstractBinarySearchTree.Node,
* trees.AbstractBinarySearchTree.Node)
*/
@Override
protected Node createNode(int value, Node parent, Node left, Node right) {
return new AVLNode(value, parent, left, right);
}
/**
* Go up from inserted node, and update height and balance informations if
* needed. If some node balance reaches 2 or -2 that means that subtree must be
* rebalanced.
*
* @param node Inserted 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;
// rebalance (-2 means left subtree outgrow, 2 means right subtree)
// 右树过高
if (nodeBalance == 2) {
// 判断是RR形还是RL形，确定进行一次还是两次旋转
if (node.right.right != null) {
// 旋转，旋转的过程中，一定维护好高度信息
node = (AVLNode) avlRotateLeft(node);
break;
} else {
node = (AVLNode) doubleRotateRightLeft(node);
break;
}
// 左树过高
} else if (nodeBalance == -2) {
// 同理，判断是LL还是LR
if (node.left.left != null) {
node = (AVLNode) avlRotateRight(node);
break;
} else {
node = (AVLNode) doubleRotateLeftRight(node);
break;
}
} else {
updateHeight(node);
}
// 把当前node向上变为父节点，向上窜，继续调整平衡
node = (AVLNode) parent;
}
}
/**
* Rotates to left side.
*/
private Node avlRotateLeft(Node node) {
Node temp = super.rotateLeft(node);
updateHeight((AVLNode) temp.left);
updateHeight((AVLNode) temp);
return temp;
}
/**
* Rotates to right side.
*/
private Node avlRotateRight(Node node) {
Node temp = super.rotateRight(node);
updateHeight((AVLNode) temp.right);
updateHeight((AVLNode) temp);
return temp;
}
/**
* Take right child and rotate it to the right side first and then rotate node
* to the left side.
*/
protected Node doubleRotateRightLeft(Node node) {
node.right = avlRotateRight(node.right);
return avlRotateLeft(node);
}
/**
* Take right child and rotate it to the right side first and then rotate node
* to the left side.
*/
protected Node doubleRotateLeftRight(Node node) {
node.left = avlRotateLeft(node.left);
return avlRotateRight(node);
}
/**
* Recomputes height information from the node and up for all of parents. It
* needs to be done after delete.
*/
private void recomputeHeight(AVLNode node) {
while (node != null) {
node.height = maxHeight((AVLNode) node.left, (AVLNode) node.right) + 1;
node = (AVLNode) node.parent;
}
}
/**
* Returns higher height of 2 nodes.
*/
private int maxHeight(AVLNode node1, AVLNode node2) {
if (node1 != null && node2 != null) {
return node1.height > node2.height ? node1.height : node2.height;
} else if (node1 == null) {
return node2 != null ? node2.height : -1;
} else if (node2 == null) {
return node1 != null ? node1.height : -1;
}
return -1;
}
/**
* Updates height and balance of the node.
*
* @param node Node for which height and balance must be updated.
*/
private static final 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 = 1 + Math.max(leftHeight, rightHeight);
}
/**
* Node of AVL tree has height and balance additional properties. If balance
* equals 2 (or -2) that node needs to be re balanced. (Height is height of the
* subtree starting with this node, and balance is difference between left and
* right nodes heights).
*
* @author Ignas Lelys
* @created Jun 30, 2011
* AVLNode继承自搜索二叉树的node，额外补充一个高度信息，用这个高度信息做平衡，一个节点的高度，是以该节点做头节点的树的高度
*/
protected static class AVLNode extends Node {
public int height;
public AVLNode(int value, Node parent, Node left, Node right) {
super(value, parent, left, right);
}
}
}
1.5.2 SB树
对于平衡性而言，任何叔叔节点的子节点格式，不少于该节点的任何一个侄子节点子节点的个数
graph TD
c-->a
c-->e
a-->b
a-->d
e-->f
e-->g
即a是一个叔叔节点，一定不少于f和g的子节点个数
对于这种约束，也可保证任何节点的左右节点的个数不会有很大悬殊，即使高度不满足严格相减的绝对值小于2，也无伤大雅。整体仍然是O(logN)
1.5.2.1 SB树针对某个节点的平衡性处理
2007年，读高中的时候，承志峰研究出来的；常被用作比赛时，AVL树反而在ACM比赛中使用的相对少点
也分为LL,LR，RR，RL四种类型。
当删除和插入某个节点，影响的节点的左孩子，不如其右孩子的左孩子节点个数多，RL形
当删除和插入某个节点，影响的节点的左孩子，不如其右孩子的右孩子节点个数多，RR形
当删除和插入某个节点，影响的节点的右孩子，不如其左孩子的左孩子节点个数多，LL形
当删除和插入某个节点，影响的节点的右孩子，不如其左孩子的右孩子节点个数多，LR形
1、 对于LL形违规，对头结点x进行一次右旋，结束后，递归调用所以节点孩子个数发生变化的节点。右旋的时候，头结点x,和原x左孩子现在变成了头节点的b。这两个节点孩子个数发生了变化，要递归调用这两个节点。原因是原来不违规的节点，调整了位置后，pk的对象变了，要基于现在的结构再检查平衡性。这里虽然套了两个递归，整体仍然是O(1)，证明略
2、 RR形违规，和LL形违规类似处理；
==SB树平衡性相对于AVL树要模糊，所以平衡性调整比AVL的调整粒度要粗，也意味着SB树比AVL树速度要快，比赛常用。而且SB树可以设计成删除节点的时候，不进行平衡性调整，只有在添加节点的时候再进行平衡性调整，添加节点的时候有可能积压了很多的不平衡，但是我们有递归行为，仍然可以调整回平衡的状态；可能为棒状，有可能该次递归行为时间复杂度比较高，但是均摊下来仍然O(logN)水平；该结构比较重要==
==如果是违规的加点的左树高度超了，且左孩子的左右子节点个数相同，必须做LL形的调整，反之RR形同理==
- SB树的树结构版本
package class06;
public class Code01_SizeBalancedTreeMap {
// k继承Comparable，可比较的泛型
public static class SBTNode<K extends Comparable<K>, V> {
// 该节点的Key
public K key;
// 该节点的V
public V value;
// 节点的左孩子
public SBTNode<K, V> l;
// 节点的右孩子
public SBTNode<K, V> r;
public int size; // 不同的key的数量
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;
// 右旋交换节点时，size要互换，维护正确的size信息。返回右旋之后的新头部
private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
// 由于右旋，要维护好左子树
SBTNode<K, V> leftNode = cur.l;
// 左孩子的右，给当前节点的左
cur.l = leftNode.r;
// 左孩子的右指向当前节点，画图可以清晰看到就是右旋操作
leftNode.r = cur;
// 维护size
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> maintain(SBTNode<K, V> cur) {
if (cur == null) {
return null;
}
// LL形
if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
// 当前节点右旋
cur = rightRotate(cur);
// 递归调整右孩子
cur.r = maintain(cur.r);
// 递归调用调整当前节点
cur = maintain(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 = maintain(cur.l);
cur.r = maintain(cur.r);
cur = maintain(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 = maintain(cur.l);
cur = maintain(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 = maintain(cur.l);
cur.r = maintain(cur.r);
cur = maintain(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;
}
// 现在，以cur为头的树上，加(key, value)这样的记录
// 加完之后，会对cur做检查，该调整调整
// 返回，调整完之后，整棵树的新头部
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 maintain(cur);
}
}
// 在cur这棵树上，删掉key所代表的节点
// 返回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 { // 当前要删掉cur
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 == null ? 0 : 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;
}
// put方法，有可能是新增有可能是覆盖更新
public void put(K key, V value) {
if (key == null) {
throw new RuntimeException("invalid parameter.");
}
// 先查找该key是不是已经存在
SBTNode<K, V> lastNode = findLastIndex(key);
if (lastNode != null && key.compareTo(lastNode.key) == 0) {
lastNode.value = value;
} else {
// 不存在的话，从根节点调用递归，加入到合适的位置。sb树由于没有向上指针，这里需要从头结点开始调用递归
// 添加进去后，有可能需要调整，头部有可能会变，返回新的头部
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);
}
}
- SB树的数组版本
package class06;
import java.util.ArrayList;
public class Code02_SizeBalancedTreeMap {
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"));
}
}
1.5.3 红黑树
1、 节点有红有黑
2、头节点和叶子节点是黑
3、红节点的子，一定要是黑节点
4、从任何节点到他的子节点，所有的路径中黑节点都是一样多的
从第三点和第四点可以推出，任何长链（黑红交替）和任何段链（都为黑）保证黑一样多，那么长链的长度一定不会比短链长度的二倍还要大。实质上上面条件的目的也是保证最长的链不要比最短的链2倍还多，一定程度上保证了平衡性
1.5.3.1 红黑树针对某个节点的平衡性处理
红黑树本质上也是搜索二叉树，搜索二叉树怎么增加和删除节点，红黑树相同；同样的加完节点，删除完节点，之后从受影响的节点往上都进行平衡性检查，几种有序表的实现只有检查平衡性的评估指标不同
红黑树平衡性检查，插入的情况下，违规的情况有5种，删除的情况下违规的情况有8种。红黑树自身的这些规定，会引出来13种违规情况下的节点调整。发明红黑树的人把13种情况都研究明白了，现在让我们学，哈哈
==面试场上看到问红黑树相关的内容，可以回答本质上也是搜索二叉树，不平衡性较多有13种，AVL和SB树都只有四种LL,LR，RR，RL。比红黑树简单。如果面试官一定要问哪5种，哪8种，那么这个面试官有问题，这种不平衡性可以查文档来获取。这种就属于面试官就是不想让你过，纠结哪8种，哪5种，纯粹是磨工夫==
红黑树这么麻烦，好处在哪，为什么这么著名，原因在于红黑树的扰动小。AVL由于平衡性特别清晰，增加和删除节点特别灵敏，扰动大。SB和红黑树的平衡性相对模糊，而且SB在删除的节点的时候，可以不进行平衡性调整，扰动小
有些场景，就是需要扰动小的调整，比如硬盘io的时候，每个树的节点，就是一块硬盘区域。硬盘删除，更新，插入等，如果时间复杂度评估指标相等，还是要选择扰动小的结构。内存中无所谓，扰动大小都可
如果每次插入和删除，行为代价都非常的高，红黑树都不考虑用，而是选择用底层硬盘结构的树，不如B树，和B+树，234树。这些树是多叉树。B树和B+树牺牲了一定的查询效率，虽然也是O(logN)，常数项很大，但是没有AVL，SB,和红黑树的效率高。比如数据库组织的一些树，就是考虑到少读写硬盘，就是用的B+树
红黑树，在（AVL，SB） 和 硬盘的树（B，B+）树之间达到平衡。各有取舍
1.5.3.1.1 Redis为什么选择跳表的结构？
Redis为什么选择跳表的结构,而不是AVL和SB树呢，实质上可以选择，但是考虑到redis可能需要对有序表进行序列化的要求，SkipList就是多层的线性结构，比较好序列化。AVL和SB是个结构化的东西，不好序列化；一种技术的选型，需要根据自己的生存状态去选择的
==三种树的平衡性保证策略不同，各自实现各自的平衡性，但是三个树都只有左旋和右旋两种调整策略==
1.6 跳表SkipList（也可实现有序表功能）
==最烧脑的结构==
跳表也可实现有序表的功能，但是跳表不是搜索二叉树，实现机制跟二叉树也没关系
==跳表实现有序表，比较好实现，思想也相对更先进O(logN)==
跳表节点有多条往外指的指针，Node里面有一个List
每个节点有多少个向下指针，随机指定，高层一定和所有节点最多的向下指针的条目数保持一致
跳表的最低层一定含有所有记录节点，概率上第二层有N/2个节点，概率上第三层会有N/4个节点…
高层向底层寻找，实际上跳跃了很多的节点。这种机制跟输入的数据状况没关系，每一个节点随机层数，最后查找O(logN)
package class06;
import java.util.ArrayList;
public class Code03_SkipListMap {
// 跳表的节点定义,key是可以比较的
public static class SkipListNode<K extends Comparable<K>, V> {
public K key;
public V val;
// 0 nextNodes.get(0)
// 1 nextNodes.get(1)
// i nextNodes.get(i)
// nextNodes.size()
// 多条指向其他节点的指针
public ArrayList<SkipListNode<K, V>> nextNodes;
public SkipListNode(K k, V v) {
key = k;
val = v;
// node 7层指针
// nextNodes.add(null)
// nextNodes.add(null)
// nextNodes.add(null)
// nextNodes.add(null)
// nextNodes.add(null)
// nextNodes.add(null)
// nextNodes.add(null)
nextNodes = new ArrayList<SkipListNode<K, V>>();
}
// 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束
// 头(null), 头节点的null，认为最小
// node -> 头，node(null, "") node.isKeyLess(!null) true
// node里面的key是否比otherKey小，true，不是false
// 当前node里面的key是否比传进来的key要小。小返回true，不小返回false
public boolean isKeyLess(K otherKey) {
// otherKey == null -> false
return otherKey != null && (key == null || key.compareTo(otherKey) < 0);
}
// 判断当前node的key可传入的key是否相等
public boolean isKeyEqual(K otherKey) {
return (key == null && otherKey == null)
|| (key != null && otherKey != null && key.compareTo(otherKey) == 0);
}
}
public static class SkipListMap<K extends Comparable<K>, V> {
// 随机建层的随机数
private static final double PROBABILITY = 0.5; // < 0.5 继续做，>=0.5 停
private SkipListNode<K, V> head;
private int size;
private int maxLevel;
public SkipListMap() {
head = new SkipListNode<K, V>(null, null);
head.nextNodes.add(null);
size = 0;
maxLevel = 0;
}
// 从最高层开始，一路找下去，
// 最终，找到第0层的<key的最右的节点
private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
if (key == null) {
return null;
}
int level = maxLevel;
SkipListNode<K, V> cur = head;
while (level >= 0) { // 从上层跳下层，直到跳到0层
// cur level -> level-1
cur = mostRightLessNodeInLevel(key, cur, level--);
}
return cur;
}
// 在level层里，如何往右移动
// 现在来到的节点是cur，来到了cur的level层，在level层上，找到<key最后一个节点并返回
private SkipListNode<K, V> mostRightLessNodeInLevel(K key,
SkipListNode<K, V> cur,
int level) {
SkipListNode<K, V> next = cur.nextNodes.get(level);
while (next != null && next.isKeyLess(key)) {
cur = next;
next = cur.nextNodes.get(level);
}
return cur;
}
public boolean containsKey(K key) {
if (key == null) {
return false;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null && next.isKeyEqual(key);
}
// put进来一个节点
public void put(K key, V value) {
if (key == null) {
return;
}
// 找到小于key的最右的节点。从上层往下层跳的方式找最底层对应的节点，最底层数据是全的，直接遍历最底层就编程O(N)复杂度了
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> find = less.nextNodes.get(0);
// 找到的不是null，那么就是重复key，更新key对应的值
if (find != null && find.isKeyEqual(key)) {
find.val = value;
} else { // 否则没找到，新增一个key，size++
size++;
int newNodeLevel = 0;
while (Math.random() < PROBABILITY) {
newNodeLevel++;
}
// 如果当前节点的随机引用个数，大于起始节点的指针个数，起始节点的指针个数要更新为大的这个
while (newNodeLevel > maxLevel) {
head.nextNodes.add(null);
maxLevel++;
}
// 建立新节点
SkipListNode<K, V> newNode = new SkipListNode<K, V>(key, value);
for (int i = 0; i <= newNodeLevel; i++) {
newNode.nextNodes.add(null);
}
int level = maxLevel;
SkipListNode<K, V> pre = head;
while (level >= 0) {
// 在level层找到最右的小于key的节点，赋值给pre
pre = mostRightLessNodeInLevel(key, pre, level);
// 找到小于等于当前节点的随机层数小于的层数时，该节点的影响层数都要更新到其他层
if (level <= newNodeLevel) {
newNode.nextNodes.set(level, pre.nextNodes.get(level));
pre.nextNodes.set(level, newNode);
}
level--;
}
}
}
public V get(K key) {
if (key == null) {
return null;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null && next.isKeyEqual(key) ? next.val : null;
}
public void remove(K key) {
if (containsKey(key)) {
size--;
int level = maxLevel;
SkipListNode<K, V> pre = head;
while (level >= 0) {
pre = mostRightLessNodeInLevel(key, pre, level);
SkipListNode<K, V> next = pre.nextNodes.get(level);
// 1）在这一层中，pre下一个就是key
// 2）在这一层中，pre的下一个key是>要删除key
if (next != null && next.isKeyEqual(key)) {
// free delete node memory -> C++
// level : pre -> next(key) -> ...
pre.nextNodes.set(level, next.nextNodes.get(level));
}
// 在level层只有一个节点了，就是默认节点head
if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
head.nextNodes.remove(level);
maxLevel--;
}
level--;
}
}
}
public K firstKey() {
return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;
}
public K lastKey() {
int level = maxLevel;
SkipListNode<K, V> cur = head;
while (level >= 0) {
SkipListNode<K, V> next = cur.nextNodes.get(level);
while (next != null) {
cur = next;
next = cur.nextNodes.get(level);
}
level--;
}
return cur.key;
}
public K ceillingKey(K key) {
if (key == null) {
return null;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null ? next.key : null;
}
public K floorKey(K key) {
if (key == null) {
return null;
}
SkipListNode<K, V> less = mostRightLessNodeInTree(key);
SkipListNode<K, V> next = less.nextNodes.get(0);
return next != null && next.isKeyEqual(key) ? next.key : less.key;
}
public int size() {
return size;
}
}
// for test
public static void printAll(SkipListMap<String, String> obj) {
for (int i = obj.maxLevel; i >= 0; i--) {
System.out.print("Level " + i + " : ");
SkipListNode<String, String> cur = obj.head;
while (cur.nextNodes.get(i) != null) {
SkipListNode<String, String> next = cur.nextNodes.get(i);
System.out.print("(" + next.key + " , " + next.val + ") ");
cur = next;
}
System.out.println();
}
}
public static void main(String[] args) {
SkipListMap<String, String> test = new SkipListMap<>();
printAll(test);
System.out.println("======================");
test.put("A", "10");
printAll(test);
System.out.println("======================");
test.remove("A");
printAll(test);
System.out.println("======================");
test.put("E", "E");
test.put("B", "B");
test.put("A", "A");
test.put("F", "F");
test.put("C", "C");
test.put("D", "D");
printAll(test);
System.out.println("======================");
System.out.println(test.containsKey("B"));
System.out.println(test.containsKey("Z"));
System.out.println(test.firstKey());
System.out.println(test.lastKey());
System.out.println(test.floorKey("D"));
System.out.println(test.ceillingKey("D"));
System.out.println("======================");
test.remove("D");
printAll(test);
System.out.println("======================");
System.out.println(test.floorKey("D"));
System.out.println(test.ceillingKey("D"));
}
}
1.7 有序表例题实战
- 例题1
给定一些数组，长度不一。每个数组里面是有序的，可理解为二维数组，每一行有序，现在需要找一个a到b的区间，要求每一行都至少有一个数命中在该区间中。求满足这个这样条件的区间的最窄区间，如果存在多个最窄区间，返回区间位置起始最小的那个
解题流程：准备一个有序表，第一步，把每个数组中第0个树加入有序表，得到一个区间就是有序表中的最小值和最大值构成的区间，该区间已经可以包含每个数组中至少一个数在该区间内，但不一定是最小区间；第二步，找到有序表中最小的数在哪个数组中，弹出最小值，把该数组的下一个树加入有序表，看是否更新了最小区间，更小才更新，同样大不更新。重复。。。
最后全局最小区间，就是我们要找的区间；
解题思路：实质上解题流程，是在尝试每一个数字开头的情况下，哪个区间是最小的。以每一个数字去尝试，实质上是一种贪心思想，不去考虑数字不以数组中出现的区间，该区间一定不是最小的
整个流程，只需要运用有序表的基本功能，原始的有序表已经能够满足需求，无需改写有序表，用系统实现的即可；
1.7.1 哪些情况下需要改写系统的有序表？
- 例题-leetcode原题
给定一个数组arr，和两个整数a和b（a<=b） 求arr中有多少个子数组，累加和在[a,b]这个范围上 返回达标的子数组数量
例如a等于10，b等于30，在arr上，求0到i范围有多少子数组在10和30范围上，假设0带i和为100，反过来就是求0到i-1范围上有多少前缀和有多少落在70到90范围上；
所以，我们求0到p，p在0到i中间，前缀和在70到90上，我们可以得到p+1到i的累加和在10到30范围上。所以这题就是求0到p的前缀和有多少在我们根据a到b和0到i的累加和推出的新的范围上[sum-a, sum-b]，就等于我们要求的个数
我们把0到0的和，0到1的和，0到i的和。。。加入到我们的结构中去，求0到i结尾的子数组有多少个达标，就是求该结构上，有多少个前缀和落在了[sum-a, sum-b]的范围上；这个结构可以加入一个数字，且允许有重复值，给定一个范围[sum-a,sum-b]可以通过该结构返回加入的节点有多少个在这个范围上。例如加入到结构中的数字，有1，1，1，4，5，给定范围[1,5]，返回6
要实现这样的功能，系统实现的有序表，无法实现，一方面原始有序表无法加入重复数字，第二方面没有这样的方法返回个数。这样的方法，可以实现为，小于a的数有多少个，小于b的数有多少个，那么最终我们需要的个数就是a-b个
在SB树上改造：
package class07;
import java.util.HashSet;
public class Code01_CountofRangeSum {
public static int countRangeSum1(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n + 1];
for (int i = 0; i < n; ++i)
sums[i + 1] = sums[i] + nums[i];
return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}
// leetcode不太好理解的版本
private static int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
if (end - start <= 1)
return 0;
int mid = (start + end) / 2;
int count = countWhileMergeSort(sums, start, mid, lower, upper)
+ countWhileMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
for (int i = start, r = 0; i < mid; ++i, ++r) {
while (k < end && sums[k] - sums[i] < lower)
k++;
while (j < end && sums[j] - sums[i] <= upper)
j++;
while (t < end && sums[t] < sums[i])
cache[r++] = sums[t++];
cache[r] = sums[i];
count += j - k;
}
System.arraycopy(cache, 0, sums, start, t - start);
return count;
}
// 节点改造为，有自己的key，有左右孩子，有size,有词频数量all。all要和size同样维护起来
public static class SBTNode {
public long key;
public SBTNode l;
public SBTNode r;
public long size; // 不同key的size，sb树的平衡指标
public long all; // 总的size
public SBTNode(long k) {
key = k;
size = 1;
all = 1;
}
}
public static class SizeBalancedTreeSet {
private SBTNode root;
private HashSet<Long> set = new HashSet<>();
private SBTNode rightRotate(SBTNode cur) {
long same = cur.all - (cur.l != null ? cur.l.all : 0) - (cur.r != null ? cur.r.all : 0);
SBTNode 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;
// all modify
leftNode.all = cur.all;
cur.all = (cur.l != null ? cur.l.all : 0) + (cur.r != null ? cur.r.all : 0) + same;
return leftNode;
}
private SBTNode leftRotate(SBTNode cur) {
long same = cur.all - (cur.l != null ? cur.l.all : 0) - (cur.r != null ? cur.r.all : 0);
SBTNode 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;
// all modify
rightNode.all = cur.all;
cur.all = (cur.l != null ? cur.l.all : 0) + (cur.r != null ? cur.r.all : 0) + same;
return rightNode;
}
private SBTNode matain(SBTNode 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;
}
// add方法时，all要跟着增加
private SBTNode add(SBTNode cur, long key, boolean contains) {
if (cur == null) {
return new SBTNode(key);
} else {
cur.all++;
if (key == cur.key) {
return cur;
} else { // 还在左滑或者右滑
if (!contains) {
cur.size++;
}
if (key < cur.key) {
cur.l = add(cur.l, key, contains);
} else {
cur.r = add(cur.r, key, contains);
}
return matain(cur);
}
}
}
public void add(long sum) {
boolean contains = set.contains(sum);
root = add(root, sum, contains);
set.add(sum);
}
// 本题在原始有序表上增加的方法，小于一个key的个数有多少个
public long lessKeySize(long key) {
SBTNode cur = root;
long ans = 0;
while (cur != null) {
if (key == cur.key) {
return ans + (cur.l != null ? cur.l.all : 0);
} else if (key < cur.key) {
cur = cur.l;
} else {
ans += cur.all - (cur.r != null ? cur.r.all : 0);
cur = cur.r;
}
}
return ans;
}
// > 7 8...
// <8 ...<=7
public long moreKeySize(long key) {
return root != null ? (root.all - lessKeySize(key + 1)) : 0;
}
}
// 好理解的版本，求[a,b]上满足数量的个数
public static int countRangeSum2(int[] nums, int lower, int upper) {
SizeBalancedTreeSet treeSet = new SizeBalancedTreeSet();
long sum = 0;
int ans = 0;
// 一个数都没有的时候词频是0
treeSet.add(0);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// sum = x [a,b] start > x-a -start < -x+a x-start < a
// [a,b]
// < a > b
// i + 1 <a - <b
long lessLowers = treeSet.moreKeySize(sum - lower);
// sum = x [a,b] start < x-b -start > -x+b x-start > b
long moreUppers = treeSet.lessKeySize(sum - upper);
ans += i + 1 - lessLowers - moreUppers;
treeSet.add(sum);
}
return ans;
}
// for test
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static int[] generateArray(int len, int varible) {
int[] arr = new int[len];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * varible);
}
return arr;
}
public static void main(String[] args) {
int len = 200;
int varible = 50;
for (int i = 0; i < 10000; i++) {
int[] test = generateArray(len, varible);
int lower = (int) (Math.random() * varible) - (int) (Math.random() * varible);
int upper = lower + (int) (Math.random() * varible);
int ans1 = countRangeSum1(test, lower, upper);
int ans2 = countRangeSum2(test, lower, upper);
if (ans1 != ans2) {
printArray(test);
System.out.println(lower);
System.out.println(upper);
System.out.println(ans1);
System.out.println(ans2);
}
}
}
}
有序表结构本身比较重要，我们也经常使用系统实现的有序表，但是涉及到手动改有序表的实现，本身就已经比较难，而且面试出现的概率不是很高
Java的TreeMap底层是红黑树，但是SB树完全可以替换，没任何差别