搜索二叉树
搜索二叉树的删除
- 若是叶子节点直接删除
- 若是度为1的节点，用子节点替代原节点的位置
- 若是度为2的节点，
- 先用前驱或者后继节点的值覆 盖原节点的值
- 然后删除相应的前驱或者后继节点
- 如果一个节点的度为2，那么 它的前驱、后继节点的度只可能是1和0
裸的搜索二叉树有什么问题？
- 输入状况决定性能
- 如果左右子树高度差不多，那么整体性能可以收敛到O(logN)
- 但是若输入状况很差，导致退化成链表，那么就是O(N)
public class AbstractBinarySearchTree {public Node root;protected int size;protected Node createNode(int value, Node parent, Node left, Node right) {return new Node(value, parent, left, right);}protected 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 > newNode.value) {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;}}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;}//将一个节点从树（newnode）放到另一个（nodetoreplace）的地方。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;}protected Node getMinimum(Node node) {while (node.left != null) {node = node.left;}return node;}public int getMinimum() {return getMinimum(root).value;}public int getMaximum() {return getMaximum(root).value;}protected Node getMaximum(Node node) {while (node.right != null) {node = node.right;}return node;}public boolean contains(int element) {return search(element) != null;}public int getSize() {return size;}public int getSuccessor(int element) {return getSuccessor(search(element)).value;}protected 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 static class Node{public Integer value;public Node parent;public Node left;public Node right;public Node(Integer value, Node parent, Node left, Node right) {super();this.value = value;this.parent = parent;this.left = left;this.right = right;}public boolean isLeaf() {return left == null && right == null;}@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + ((value == null) ? 0 : value.hashCode());return result;}@Overridepublic 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;}}}
平衡搜索二叉树
那么接下来就引入平衡搜索二叉树
- 自平衡机制， 平衡的代价不超过O(logN),
- 所以整体的性能就能是O(logN)
左旋、右旋是针对头节点说的，（即对哪个节点执行）
对a右旋， 没有破坏搜索二叉树的含义，但是树的高度降低了
对a左旋
public class AbstractSelfBalancingBinarySearchTree extends AbstractBinarySearchTree {
// 左旋
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 = node;
} else {
temp.parent.right = node;
}
} else {
root = temp;
}
return temp;
}
// 右旋
protected Node rotateRight(Node node) {
Node temp = node.left;
temp.parent = node.parent;
node.left = temp.left;
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 = node;
} else {
temp.parent.right = node;
}
} else {
root = temp;
}
return temp;
}
}
- 有序表TreeMap
- treemap的底层是平衡搜索二叉树
有序表是一个接口名， 只要key是有序组织，然后性能O(logN)这些都叫做有序表
不管是AVL树、SizeBalance树、还是红黑树来实现几乎无差别，差别可能就在于常数时间
- 不管是AVL树、SizeBalance树、还是红黑树，基本的动作都是左旋和右旋，不同的是具体的策略细节
- AVL树怎么维持平衡性的？
- 从受影响的节点开始往上检查每个父节点的平衡性， 若有节点平衡性被破坏了，去调整
- 删除的情况
- 若用后继节点替你的环境，应该是从原来后继节点的位置往上去检查
其实AVL树、sb树、红黑树的这个动作都是一样的，只是调整的方式不同
- 从受影响的节点开始往上检查每个父节点的平衡性， 若有节点平衡性被破坏了，去调整
- 若用后继节点替你的环境，应该是从原来后继节点的位置往上去检查
- 现在来看具体到某个节点的调整方式
- AVL树四种违规情况
- LL
- LR
- RL
- RR
- 四种违规情况只会中一个， 因为每次添加删除一个节点都会检查，
- 然后 | 左子树高度 - 右子树高度 | < 2, 那就不违规， 否则违规
- 违规了，那必然是有一侧高一侧低嘛，但是注意，它们的高度差最多就是2，因为每次添加或删除一个节点，都会检查，怎么可能一下子高度差拉到2以上呢？
- LL 型， 根节点是因为左树的左树而不平的
- 其他三种类型同理，
- 简单的情况好理解，主要是复杂起来了你怎么判断？
- 比如这个， 根节点左子树高度7， 右子树高度5，违规了，
- 首先，左子树高，那么第一个字母就是L, 也就是要么是LL要么是LR
- 那么左子树的左右子树的高度必然有一个是高度6，也可能两个都是6，
- 若两个都是6，那么LL和LR都中了，只能选择LL, 不能选LR，（同理若RR和RL都中了，只能选择RR）
- 看这个例子
- 选LR之后，b依然违规
- 若只有一个是6
- 那么就看这个高度为6的树是左子树还是右子树
- 是左子树，那么就是LL
- 是右子树，那么就是LR
- LL的情况就是对X来一次右旋即可（圆圈代表具体节点，正方形代表子树）
- 同理RR的情况就是来一次左旋即可
- 那么LR和RL的情况呢？ 这两种情况都是让孙节点上到顶部
- 比如LR, 先对a节点来一次左旋，然后再对X来一次左旋
- LL的情况就是对X来一次右旋即可（圆圈代表具体节点，正方形代表子树）
- AVL树四种违规情况
- 
- 四种情况的每个节点的调整是O(1)
- 即便我往上的这条链每个节点都调整，代价最终也是O(logN)的
- 任何节点交换的时候，主要要把它们的高度也要重新计算，不管是左旋还是右旋，旋转之间节点的高度你要维持对， 比如下面这个右旋，那么b跟a交换后，高度也要重新算
- a的高度 = max（d， t） + 1
- b的高度 = max（c，a）+ 1
- 每次交换后，从受影响的节点往上都要重新计算高度，这个过程也是O(1)的
public class AVLTree extends AbstractSelfBalancingBinarySearchTree {
protected static class AVLNode extends Node{
public int height;
public AVLNode(int 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 delete(int element) {
Node deleteNode = super.search(element);
if (deleteNode != null) {
Node successorNode = super.delete(deleteNode);
if (successorNode != null) {
// 不区分几种情况了，统一找到后继节点往上开始查，虽然会有冗余查询，但是冗余就冗余了，反正高度最多也就logN，
// 当然你也可以写几个if 去区分，优化的也只是常数时间
// 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;
}
@Override
public Node insert(int element) {
Node newNode = super.insert(element);
rebalance((AVLNode)newNode);
return newNode;
}
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 && ((AVLNode)node.right.right).height == leftHeight + 1) {// RR
node = (AVLNode) avlRotateLeft(node);
break;
} else {// RL
node = (AVLNode) avlRotateRight(node);
break;
}
} else if (nodeBalance == -2) { // 左树过高
if (node.left.left != null && ((AVLNode)node.left.left).height ==rightHeight + 1) {
node = (AVLNode)avlRotateRight(node);
break;
} else {
node = (AVLNode)doubleRotateLeftRight(node);
break;
}
} else {
updateHeight(node);
}
node = (AVLNode) parent;
}
}
private void recomputeHeight(AVLNode node) {
while (node != null) {
node.height = maxHeight((AVLNode)node.left, (AVLNode)node.right) + 1;
node = (AVLNode)node.parent;
}
}
private Node avlRotateLeft(Node node) {
Node temp = super.rotateLeft(node);
updateHeight((AVLNode)temp.left);
updateHeight((AVLNode)temp);
return temp;
}
private Node avlRotateRight(Node node) {
Node temp = super.rotateRight(node);
updateHeight((AVLNode)temp.right);
updateHeight((AVLNode)temp);
return temp;
}
protected Node doubleRotateRightLeft(Node node) {
node.right = avlRotateRight(node.right);
return avlRotateLeft(node);
}
protected Node doubleRotateLeftRight(Node node) {
node.left = avlRotateLeft(node.left);
return avlRotateRight(node);
}
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);
}
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;
}
}
SizeBalance树 （比赛常用）
SB树左右子树节点个数差距最多 2倍 + 1的水平
所以我们在用叔节点和侄子节点的约束关系来保证左右子树的节点个数差距不会太多，你就能说你的高度是logN,
- 如果一个节点的左孩子节点数量不如右孩子的左儿子节点数量多，那么就是RL型
- 如果一个节点的左孩子节点数量不如右孩子的右儿子节点数量多，那么就是RR型
SizeBalance树是不算重复的key的， sb树的个数指的是不同key的数量
LL型， 对x进行右旋， 然后各自的节点数量重新计算
- 然后还没完， 检查平衡性，递归套递归，先检查新的x ，再检查新的b
- m(x)不是查x，而是查x的左右孩子违不违规
- 为什么要检查？
- 因为比如你看e，原来是跟d的儿子去pk， 右旋之后，e要去跟c的儿子pk了，pk对象变了
RR型，对X进行一次左旋
- 谁的孩子发生变化了？ x和b的孩子节点发送变化了，（只有发生节点变化的节点才需要检查）
- 然后
- 虽然整个过程是一个大递归 + 旋转O(1) + 二个递归， 但是总的发生的行为次数是O（1）
LR型
- 为什么高手在比赛的时候都喜欢用SizeBalanced树来改有序表？ 因为它维持平衡性没有AVL树那么严格，它的平衡性模糊，然后它好实现，
- 正常的SizeBalcaned树在添加删除的时候都要调整
- 改动过后的SizeBalcaned树在删除的时候不需要调整，统一放到add的时候去调整，因为我有递归
- 现在现来看正常的SizeBalanced树
- 由于我们的SizeBalanced树 没有设计parent指针，所以在做平衡性调整的时候，是通过add（root，key，value）从根节点一路往下递归的，然后它最后又会一层一层返回到根节点
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;
}
}
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;
}
// 调整
public SBTNode<K, V> maintain(SBTNode<K, V> cur) {
if (cur == null) {
return null;
}
int leftSize = cur.l != null ? cur.l.size : 0;
int rightSize = cur.r != null ? cur.r.size : 0;
int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;
int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;
int leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;
int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;
if (leftLeftSize > rightSize) {// LL
cur = rightRotate(cur);
cur.r = maintain(cur.r);
cur = maintain(cur);
} else if (leftRightSize > rightSize) { // LR
cur.l = leftRotate(cur.l);
cur = rightRotate(cur);
cur.l = maintain(cur.l);
cur.r = maintain(cur.r);
cur = maintain(cur);
} else if (rightRightSize > leftSize) { //RR
cur = leftRotate(cur);
cur.l = maintain(cur.l);
cur = maintain(cur);
} else if (rightLeftSize > leftSize) { // RL
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做检查，该调整调整
// 返回，调整完之后，整棵树的新头部
public 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) { // 叶子
cur = null;
} else if (cur.l == null && cur.r != null) {
cur = cur.r;
} else if (cur.l != null && cur.r == null) {
cur = cur.l;
} else { // 度为2
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;
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 containKey(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 (containKey(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;
}
跳表
跳表也可以实现有序表的所有操作,它的性能也是O(logN)
- 跳表的思想先进
- 通过node内部的ArrayList实现往下指针的条数
初始状态
看一下在加节点的时候是什么样的逻辑,
随机建层
- 这个节点有多少个向外的指针完全扔骰子决定 (初始是一条)
- 比如扔骰子,扔到≤0.5的就建一条, 直到扔到＞0.5的就停,
- 假设新加入的节点扔出了3层
- 然后我跳表里的最左边的那一个, 看到了新来的节点层数比我高, 那我得扩充层数到跟它一样
- 然后我要在最左边的最高层中找到最晚的≤3的key , 找不到, 就让它直接指向节点3
- 接着往下一层,接着找, 找不到,也直接指向节点3
- …..
- 接下来来了个节点5, 只扔出了2层
- 跳表最左边的层数是3层, 不需要扩充
- 然后我永远从最高层开始找最晚的≤5的key, 此时就是节点3, 但是此时是在3层, 而节点5没有3层, 所以这一层不指向5, 但是在3的内部跳转到下一层去
- 然后因为节点5有2层, 所以这一层可以指向节点5
- 接下来一样的步骤
- 接下来 来了个节点2, 只有一层
- 以上就是插入的过程
- 接下来看查询的过程, 查询永远从最高层开始找
- 如图所示怎么查6?
- 接下来看随机建层后怎么维护原有的
- 假设现在只有3层
- 然后来了个有4层的6节点
- 所以相当于这样的效果
- 假设现在只有3层
接下来告诉你跳表好在哪
比如N个节点, 那么跳表最底层一定会有N个节点
- 第2层, 期望是N/2节点 (因为扔色子嘛, 50%的概率)
- 第3层, 期望是N/4节点
- 第4层, 期望是N/8节点
- ,,,,
- ,,
- 所以你会发现, 如果最高层越过了一个节点,相当于底层越过了好多节点na
- 那为什么最终能收敛到O(logN)?
- 和我的输入状况是没关系的, 因为所有的数据都在扔色子, 完全凭运气来做高层节点到低层节点的数量分配 (跟快排那个差不多, 都是随机的)
- 注意点
- 我们认为最左边的null 比所有数都小, 最右边的null比所有数都大
```java
public class SkipListMap{
- 我们认为最左边的null 比所有数都小, 最右边的null比所有数都大
private static final double PROBABILITY = 0.5; private SkipListNode
public SkipListMap() { head = new SkipListNode<>(null, null); head.nextNodes.add(null); size = 0; maxLevel = 0; }
// 从最高层开始一路找下去 // 最终找到第0层的
mostRightLessNodeInTree(K key) { if (key == null) { return null;} int level = maxLevel; SkipListNode
cur = mostRightLessNodeInLevel(key, cur, level); level--;} return cur; } private SkipListNode
cur = next; next = cur.nextNodes.get(level);} return cur; }
public boolean containsKey(K key) { if (key == null) return false; SkipListNode
// 新增、 改value public void put(K key, V value) { if (key == null) {
return;} SkipListNode
find.val = value;} else { // 新增
size++; // 随机建层 int newNodeLevel = 0; while (Math.random() < PROBABILITY) { newNodeLevel++; } // 最左边 while (newNodeLevel > maxLevel) { head.nextNodes.add(null); maxLevel++; } SkipListNode<K, V> newNode = new SkipListNode<>(key, value); for (int i = 0; i <= newNodeLevel; i++) { newNode.nextNodes.add(null); } int level = maxLevel; SkipListNode<K, V> pre = head; while (level >= 0) { 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
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); if (next != null && next.isKeyEqual(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
SkipListNode<K, V> next = cur.nextNodes.get(level); while (next != null) { cur = next; next = next.nextNodes.get(level); } level--;} return cur.key; }
public K ceilingKey(K key) { if (key == null) {
return null;} SkipListNode
public K floorKey(K key) { if (key == null) {
return null;} SkipListNode
public int size() { return size; }
public static class SkipListNode
{ public K key; public V val; public ArrayList public SkipListNode(K key, V val) {
this.key = key; this.val = val; nextNodes = new ArrayList<>();}
// node里面的key是否比otherKey小，true，不是false public boolean isKeyLess(K otherKey) {
return otherKey != null && (key == null || key.compareTo(otherKey) < 0);}
public boolean isKeyEqual(K otherKey) {
return (key == null && otherKey == null) || (key != null && otherKey != null && key.compareTo(otherKey) == 0);红黑树
接下来看红黑树
- 红黑树
- 几个定义
- 1） 每个节点不是红就是黑
- 2） 头节点是黑、 叶节点是黑
- 3）红节点的子一定得是黑节点
- 4）从任意一个节点到叶子节点，所有的路径上黑色节点数量一样多
- 第3个规则表明了红节点不会相邻
- 那么最长的链就是黑红黑红交替的，最短的链应该是全黑的， 然后又要求长链和短链黑色节点个数一样多， 那么就说明最长链和最短链长度最多就是2倍关系
- 红黑树也是二叉搜索树，所以该怎么添加\删除还是怎么添加\删除
- 区别是添加完后从受影响的节点一路往上检查平衡性， 它被自己规定的这种规则玩得死去活来，总共有5 + 8 = 13种情况
- 插入 5种， 删除 8种
- 区别是添加完后从受影响的节点一路往上检查平衡性， 它被自己规定的这种规则玩得死去活来，总共有5 + 8 = 13种情况
不需要改写有序表的题目
- 题目 ：
- 一个二维空间，分别装着若干个一维有序数组， 分别是A、B、C……
- 求一个最窄区间，要求所有一维数组中至少有一个数在这个区间里，若有多个最窄区间符合要求，返回开头最小的那个区间
- 答案有点难想
- 一个有序表
- 第一回把1、5、4放到有序表里去， 然后有序表里最小值和最大值就构成了一个区间[1, 5], 这个区间一定是能包含每个数组中至少一个数的
- 然后有序表里弹出最小的，是1， 而1来自第一个数组，那么把第一个数组中的下一个数放到有序表里去
- 得到新答案区间[3, 5], 比老答案更窄，所以干掉老答案，
- 得到新答案区间[3, 5], 比老答案更窄，所以干掉老答案，
- 接下来继续周而复始
- 这个流程实质上是在求以全部数组中每个数开头的答案是啥，
这道题不需要改写有序表，系统提供的有序表就够用了
需要改写有序表的题目
题目一CountToRangeSum
https://leetcode-cn.com/problems/count-of-range-sum/submissions/
给定一个数组arr， 和两个整数a和b（a<=b）, 求arr中有多少个子数组，累加和在[a, b]这个范围上， 返回达标的子数组数量
数组中以i结尾的子数组
若p…..i的累加和范围是[10 ~ 30]
然后o…..i的累加和范围是100， 那么0……..p - 1的累加和范围是[70 ~ 90]
所以你在求以i结尾的数组中有多少个累加和范围落在[10, 30]中时
就是在求0~0， 0~1, 0~2, 0~3。。。。这些前缀和中有多少个落在[70, 90]范围中， 然后就可以反推
现在来做抽象化
那我们在遍历的时候，就把0~0、0~1，0 ~2.。。。。。的前缀和加到有序表里去，
有序表里存着之前所有出现的前缀和
然后我求必须以0结尾时有多少个达标的，
必须以1结尾时有多少个达标的，
必须以2结尾时有多少个达标的，
。。。。
不就解出来了么
那么这个有序表的结构
- add（num） num可以重复
- 一个接口， 允许我传入一个范围L,R, 然后告诉我有序表落在这个范围中的数有多少个
- 其实这个范围查询的接口其实可以被 <num的数有多少个 这个接口代替的
- 那么允许加入重复的数字怎么实现？
- 给节点增加字段all即可
- 这个结构SizeBalanced树、AVL树、红黑树都可以改，它只和二叉搜索树怎么改接口有关，该怎么调平衡还是怎么调平衡， 注意这个all在平衡调整交换节点的时候也要跟着换，如果是用SB树来的话，那么size怎么换all就怎么换
- 我现在要查 < 6的
- 当6要从5往右滑时，就得更新ans
- 接下来该往左滑了， 左滑， ans不增加任何数据，，，
- 滑完了，答案就出来了
- 只要右滑就更新ans ———> 父节点 - 右子树节点数量
- 左滑就不更新
上图滑到最后，找到了6节点， 若6节点没有左子树，那么就返回答案， 若6节点有左子树，那么最终答案还要加上这课左子树的数量 ```java public static class SBTNode { public long key; public CounttoRangeSum.SBTNode l; public CounttoRangeSum.SBTNode r; // 不同key的数量 public long size; // 为了重复key而设置的 public long all;
public SBTNode(long key) {
this.key = key; size = 1; all = 1;} }
public static class SizeBalancedTreeSet { private CounttoRangeSum.SBTNode root; private HashSet
set = new HashSet<>(); private CounttoRangeSum.SBTNode rightRotate(CounttoRangeSum.SBTNode cur) {
long same = cur.all - (cur.l != null ? cur.l.all : 0) - (cur.r != null ? cur.r.all : 0); CounttoRangeSum.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; leftNode.all = cur.all; cur.all = (cur.l != null ? cur.l.all : 0) + (cur.r != null ? cur.r.all : 0) + same; return leftNode;}
private CounttoRangeSum.SBTNode leftRotate(CounttoRangeSum.SBTNode cur) {
long same = cur.all - (cur.l != null ? cur.l.all : 0) - (cur.r != null ? cur.r.all : 0); CounttoRangeSum.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; rightNode.all = cur.all; cur.all = (cur.l != null ? cur.l.all : 0) + (cur.r != null ? cur.r.all : 0) + same; return rightNode;}
private CounttoRangeSum.SBTNode maintain(CounttoRangeSum.SBTNode cur) {
if (cur == null) { return null; } Long leftSize = cur.l != null ? cur.l.size : 0; Long leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0; Long leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0; Long rightSize = cur.r != null ? cur.r.size : 0; Long rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0; Long rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0; if (leftLeftSize > rightSize) { // LL cur = rightRotate(cur); cur.r = maintain(cur.r); cur = maintain(cur); } else if (leftRightSize > rightSize) { // LR cur.l = leftRotate(cur.l); cur = rightRotate(cur); cur.l = maintain(cur.l); cur.r = maintain(cur.r); cur = maintain(cur); } else if (rightRightSize > leftSize) { // RR cur = leftRotate(cur); cur.l = maintain(cur.l); cur = maintain(cur); } else if (rightLeftSize > leftSize) { // RL cur.r = rightRotate(cur.r); cur = leftRotate(cur); cur.l = maintain(cur.l); cur.r = maintain(cur.r); cur = maintain(cur); } return cur;}
public CounttoRangeSum.SBTNode add(CounttoRangeSum.SBTNode cur, Long key, boolean contains) {
if (cur == null) { return new CounttoRangeSum.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 maintain(cur); } }}
public void add(long sum) {
boolean contains = set.contains(sum); root = add(root, sum, contains); set.add(sum);}
public Long lessKeySize(Long key) {
CounttoRangeSum.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;
}
public Long moreKeySize(Long key) {
return root != null ? (root.all - lessKeySize(key + 1)) : 0;
}
}
public static int countRangeSum(int[] nums, int lower, int upper) {
CounttoRangeSum.SizeBalancedTreeSet treeSet = new CounttoRangeSum.SizeBalancedTreeSet();
long sum = 0;
int ans = 0;
treeSet.add(0); //一个数都没有的时候，就已经有一个前缀和累加和为0
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// sum i结尾的时候[lower, upper]
// 之前所有前缀累加和中，有多少累加和落在[sum - upper, sum - lower]
// 查 ？ < sum - lower + 1 a
// 查 ？ < sum - upper b
long a = treeSet.lessKeySize(sum - lower + 1);
long b = treeSet.lessKeySize(sum - upper);
ans += a - b;
treeSet.add(sum);
}
return ans;
}
<a name="WruZ2"></a>
## 题目二SlidingWindowMedian
<br />给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
来源：力扣（LeetCode）<br />链接：[https://leetcode-cn.com/problems/sliding-window-median](https://leetcode-cn.com/problems/sliding-window-median)
这个中位数是严格中位数，也就是如果个数是偶数的话，那么要把（上中位数 + 下中位数） / 2的那个数返回
- **因此你的有序表允许增加某个数字，删除某个数字，允许查询第k小的数是啥**
- **增加all字段**
- **查第55小**
- **从根节点往左滑， 30个小于55个，所以左树排除，然后右树有60个 ， 100 - 30 - 60 = 10， 所以根节点也排除，接下来滑到右节点，那么你已经滑过了40个数了，接下来是需要在右树上找第15小的**
- 
- **我把node封装成value和index的组合，这样即使value一样，节点也是不同的节点，所以就不用增加all字段了**
- 
```java
public static class SBTNode<K extends Comparable<K>>{
public K key;
public SBTNode<K> l;
public SBTNode<K> r;
public int size;
public SBTNode(K k) {
key = k;
size = 1;
}
}
// 把Node当成key
public static class Node implements Comparable<Node> {
public int index;
public int value;
public Node(int key, int value) {
this.index = key;
this.value = value;
}
@Override
public int compareTo(Node o) {
return value != o.value ? Integer.valueOf(value).compareTo(o.value)
: Integer.valueOf(index).compareTo(o.index);
}
}
public static class SizeBalancedTreeMap<K extends Comparable<K>> {
private SBTNode<K> root;
private SBTNode<K> rightRotate(SBTNode<K> cur) {
SBTNode<K> 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> leftRotate(SBTNode<K> cur) {
SBTNode<K> 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> maintain(SBTNode<K> cur) {
if (cur == null) {
return null;
}
int leftSize = cur.l != null ? cur.l.size : 0;
int leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;
int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;
int rightSize = cur.r != null ? cur.r.size : 0;
int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;
int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;
if (leftLeftSize > rightSize) { // LL
cur = rightRotate(cur);
cur.r = maintain(cur.r);
cur = maintain(cur);
} else if (leftRightSize > rightSize) { // LR
cur.l = leftRotate(cur.l);
cur = rightRotate(cur);
cur.l = maintain(cur.l);
cur.r = maintain(cur.r);
cur = maintain(cur);
} else if (rightRightSize > leftSize) { // RR
cur = leftRotate(cur);
cur.l = maintain(cur.l);
cur = maintain(cur);
} else if (rightLeftSize > leftSize) {
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> findLastIndex(K key) {
SBTNode<K> pre = root;
SBTNode<K> 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> add(SBTNode<K> cur, K key) {
if (cur == null) {
return new SBTNode<>(key);
} else {
cur.size++;
if (key.compareTo(cur.key) < 0) {
cur.l = add(cur.l, key);
} else {
cur.r = add(cur.r, key);
}
return maintain(cur);
}
}
private SBTNode<K> delete(SBTNode<K> 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) {
cur = null;
} else if (cur.l == null && cur.r != null) {
cur = cur.r;
} else if (cur.l != null && cur.r == null) {
cur = cur.l;
} else {
SBTNode<K> pre = null;
SBTNode<K> 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;
cur = des;
}
}
return cur;
}
private SBTNode<K> getIndex(SBTNode<K> 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> lastNode = findLastIndex(key);
return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
}
public void add(K key) {
if (key == null) {
throw new RuntimeException("invalid parameter");
}
SBTNode<K> lastNode = findLastIndex(key);
if (lastNode == null || key.compareTo(lastNode.key) != 0) {
root = add(root, key);
}
}
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 double[] medianSlidingWindow(int[] nums, int k) {
SizeBalancedTreeMap<Node> map = new SizeBalancedTreeMap<>();
for (int i = 0; i < k - 1; i++) {
map.add(new Node(i, nums[i]));
}
double[] ans = new double[nums.length - k + 1];
int index = 0;
for (int i = k - 1; i < nums.length; i++) {
map.add(new Node(i, nums[i]));
if (map.size() % 2 == 0) {
Node upmid = map.getIndexKey(map.size() / 2 - 1);
Node downmid = map.getIndexKey(map.size() / 2);
ans[index++] = ((double) upmid.value + (double) downmid.value) / 2;
} else {
Node mid = map.getIndexKey(map.size() / 2);
ans[index++] = (double) mid.value;
}
map.remove(new Node(i - k + 1, nums[i - k + 1]));
}
return ans;
}
add、getIndexKey， size、remove
若有收获，就点个赞吧
0 人点赞
