有序表
有序表
- 作用：支持哈希表的所有操作，key是按照有序进行组织的（哈希表是无序的）
- 时间复杂度：所有的操作都是O(log N)级别的
- 实现方式：
（1）红黑树
（2）AVL
（3）SBT
（4）跳表（skiplist）
（1），（2），（3）均属性BST（平衡搜索二叉树）
搜索二叉树
- 搜索二叉树中，一般没有重复项，可以在节点中增加数据项，记录节点数据出现的次数
- 插入：每次插入节点均从头节点，若插入节点比头节点小往左与其子节点进行比较，若比头节点大往右进行比较，重复比较，直至到空节点，将该节点插入到空节点即可
- 删除：
（1）叶子节点，搜索该节点，并记录该节点的父节点，修改父节点指针便可实现删除
（2）只有左 / 右节点，搜索该节点，记录其父节点与其子节点，修改父节点指针，使用子节点替换删除节点
（3）左右孩子都有：搜索该节点，使用该节点左树的最右节点 / 右树的最左节点 替换删除节点，再将最右 / 最左节点的子节点与其父节点相连即可 - 缺点：时间复杂度受数据提供顺序的影响
- 改变树的平衡性：
- 左旋：头节点向左边倒
（1）p节点向左边倒，右孩子 x，成为头节点
（2）p成为x的左孩子
（3）将x 的左孩子给到p，成为p的右孩子
public void leftRotate(Node cur) { Node right = cur.r; cur.r = right.l; right.l = cur; }
- 右旋：头节点向左边倒
（1）p节点向右边倒，左孩子 x，成为头节点
（2）p成为x的右孩子
（3）将x 的右孩子给到p，成为p的左孩子
public Node rightRotate(Node cur) { Node left = cur.l; cur.l = left.r; left.r = cur; }
AVL
- 平衡性要求：左右子树均为AVL且左右子树的高度差的决定值小于等于1
- 平衡性的检查：
（1）增加节点：从增加节点的位置开始以及往上进行平衡性判断
（2）删除节点：从删除节点的位置开始以及往上进行平衡性判断，特殊的删除左右节点都存在的节点时，从替换该节点的父节点开始检查 - 平衡性被破会的四种情况：技巧，使三个节点的中间值作为头节点，进行调整
（1）LL：左树的左边破坏平衡，x为中间值，使x作头节点，就是y的右旋
（2）RR：右树的右边破坏平衡，x为中间值，使x作头节点，就是y的左旋
（3）LR：左树的右边破坏平衡，z为中间值，使z作头节点，先x左旋，再y右旋
（4）RL：右树的左边破坏平衡，z为中间值，使z作头节点，先x右旋，再y左旋
public static class AVLNode<K extends Comparable<K>, V> { public K k; public V v; public AVLNode<K, V> l; public AVLNode<K, V> r; public int h; public AVLNode(K key, V value) { k = key; v = value; h = 1; } } public static class AVLTreeMap<K extends Comparable<K>, V> { private AVLNode<K, V> root; private int size; public AVLTreeMap() { root = null; size = 0; } private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) { AVLNode<K, V> left = cur.l; cur.l = left.r; left.r = cur; cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1; left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1; return left; } private AVLNode<K, V> leftRotate(AVLNode<K, V> cur) { AVLNode<K, V> right = cur.r; cur.r = right.l; right.l = cur; cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1; right.h = Math.max((right.l != null ? right.l.h : 0), (right.r != null ? right.r.h : 0)) + 1; return right; } private AVLNode<K, V> maintain(AVLNode<K, V> cur) { if (cur == null) { return null; } int leftHeight = cur.l != null ? cur.l.h : 0; int rightHeight = cur.r != null ? cur.r.h : 0; if (Math.abs(leftHeight - rightHeight) > 1) { if (leftHeight > rightHeight) { int leftLeftHeight = cur.l != null && cur.l.l != null ? cur.l.l.h : 0; int leftRightHeight = cur.l != null && cur.l.r != null ? cur.l.r.h : 0; if (leftLeftHeight >= leftRightHeight) { cur = rightRotate(cur); } else { cur.l = leftRotate(cur.l); cur = rightRotate(cur); } } else { int rightLeftHeight = cur.r != null && cur.r.l != null ? cur.r.l.h : 0; int rightRightHeight = cur.r != null && cur.r.r != null ? cur.r.r.h : 0; if (rightRightHeight >= rightLeftHeight) { cur = leftRotate(cur); } else { cur.r = rightRotate(cur.r); cur = leftRotate(cur); } } } return cur; } private AVLNode<K, V> findLastIndex(K key) { AVLNode<K, V> pre = root; AVLNode<K, V> cur = root; while (cur != null) { pre = cur; if (key.compareTo(cur.k) == 0) { break; } else if (key.compareTo(cur.k) < 0) { cur = cur.l; } else { cur = cur.r; } } return pre; } private AVLNode<K, V> findLastNoSmallIndex(K key) { AVLNode<K, V> ans = null; AVLNode<K, V> cur = root; while (cur != null) { if (key.compareTo(cur.k) == 0) { ans = cur; break; } else if (key.compareTo(cur.k) < 0) { ans = cur; cur = cur.l; } else { cur = cur.r; } } return ans; } private AVLNode<K, V> findLastNoBigIndex(K key) { AVLNode<K, V> ans = null; AVLNode<K, V> cur = root; while (cur != null) { if (key.compareTo(cur.k) == 0) { ans = cur; break; } else if (key.compareTo(cur.k) < 0) { cur = cur.l; } else { ans = cur; cur = cur.r; } } return ans; } private AVLNode<K, V> add(AVLNode<K, V> cur, K key, V value) { if (cur == null) { return new AVLNode<K, V>(key, value); } else { if (key.compareTo(cur.k) < 0) { cur.l = add(cur.l, key, value); } else { cur.r = add(cur.r, key, value); } cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1; return maintain(cur); } } // 在cur这棵树上，删掉key所代表的节点 // 返回cur这棵树的新头部 private AVLNode<K, V> delete(AVLNode<K, V> cur, K key) { if (key.compareTo(cur.k) > 0) { cur.r = delete(cur.r, key); } else if (key.compareTo(cur.k) < 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 { AVLNode<K, V> des = cur.r; while (des.l != null) { des = des.l; } cur.r = delete(cur.r, des.k); des.l = cur.l; des.r = cur.r; cur = des; } } if (cur != null) { cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1; } return maintain(cur); } public int size() { return size; } public boolean containsKey(K key) { if (key == null) { return false; } AVLNode<K, V> lastNode = findLastIndex(key); return lastNode != null && key.compareTo(lastNode.k) == 0 ? true : false; } public void put(K key, V value) { if (key == null) { return; } AVLNode<K, V> lastNode = findLastIndex(key); if (lastNode != null && key.compareTo(lastNode.k) == 0) { lastNode.v = value; } else { size++; root = add(root, key, value); } } public void remove(K key) { if (key == null) { return; } if (containsKey(key)) { size--; root = delete(root, key); } } public V get(K key) { if (key == null) { return null; } AVLNode<K, V> lastNode = findLastIndex(key); if (lastNode != null && key.compareTo(lastNode.k) == 0) { return lastNode.v; } return null; } public K firstKey() { if (root == null) { return null; } AVLNode<K, V> cur = root; while (cur.l != null) { cur = cur.l; } return cur.k; } public K lastKey() { if (root == null) { return null; } AVLNode<K, V> cur = root; while (cur.r != null) { cur = cur.r; } return cur.k; } public K floorKey(K key) { if (key == null) { return null; } AVLNode<K, V> lastNoBigNode = findLastNoBigIndex(key); return lastNoBigNode == null ? null : lastNoBigNode.k; } public K ceilingKey(K key) { if (key == null) { return null; } AVLNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key); return lastNoSmallNode == null ? null : lastNoSmallNode.k; } }
SBT（SizeBalancedTree）
- 平衡性要求：每颗子树的大小，不小于其兄弟子树的大小，即每颗叔叔树的大小，不小于其任何侄子树的大小
- 平衡性的检查：
（1）增加节点：从增加节点的位置开始以及往上进行平衡性判断
（2）删除节点：从删除节点的位置开始以及往上进行平衡性判断，特殊的删除左右节点都存在的节点时，从替换该节点的父节点开始检查 - 平衡性被破会的四种情况：
（1）LL：左树的左边破坏平衡，maintain为递归函数，将子树变化过的节点再次进行m调用
（2）RR：右树的右边破坏平衡，左旋，再将子树变化的调用m函数
（3）LR：左树的右边破坏平衡，先左，再右旋，再将子树变化的调用m函数
（4）RL：右树的左边破坏平衡，先右，再左旋，再将子树变化的调用m函数
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; // 不同的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; 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> maintain(SBTNode<K, V> 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 rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0; int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0; if (leftLeftSize > rightSize) { cur = rightRotate(cur); cur.r = maintain(cur.r); cur = maintain(cur); } else if (leftRightSize > rightSize) { 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) { 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, 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; } } // cur = maintain(cur); 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; } // （key，value） put -> 有序表 新增、改value 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; } }
红黑树
- 概述：
（1）每个节点不是红就是黑
（2）叶节点：不是没有左右孩子的节点，而是空节点
（3）头和叶节点，必须为黑
（4）任何两个红节点都不能相邻
（5）任意节点出发，到每一个叶节点的所有路径，经过的黑节点个数相同 - 效果：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的
AVL，SBT，红黑树对比
- 共性
（1）都是搜索二叉树
（2）插入、删除、查询（一切查询）都是基于搜索二叉树的
（3）使用调整的基本动作都只有左旋、右旋
（4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查
（5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN) - 不同点
（1）平衡性的约束不同：AVL树最严格、SBT树稍宽松、红黑树最宽松（平衡性：左右子树的规模大致相同）
（2）因为平衡性的约束不同，所以在插入，删除平衡性变化的调整上有常数时间的差别
跳表（skiplist）
- 概述：
（1）开始有一个默认节点（链表，其key是最小的） head
（2）每次出发均从head出发
（3）添加节点，该节点随机产生一个高度，若头结点的高度比其小，头结点扩充高度（只有头结点可以扩充，要保证头结点的高度最高的）
（4）将头结点中的指针向连接节点对应层连接
如图：就是一个含10个数据跳表，1产生的随机高度是4，2产生的随机高度是1…… - 基本操作
（1）查找：通过head找到最高层，直接通过最高层对应的元素进行比较，若最高层不行就跳到下一层，因为整体是有序的所以可以减少节点的查找
例：查找40，最高层开始是20，小于40，于是可以跳过2，10，15，下一次直接可以100，大于，从20开始到下一层50，大于，再下一层找到40
（2）插入：先生成插入元素对应的层数，通过查找，确定插入位置，使用插入层改变节点的连接
例：插入70，对应2层
（3）删除：先查找，直接将待删除节点前的节点忽略该节点与后面节点连接即可 - 复杂度：
（1）用空间来换时间
（2）如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)，我们可以看出来这是一个等比数列
（3）所以跳表的空间复杂度为 O(n)
（4）跳表的高度计算类似与满二叉树：整个跳表的高度就是 log(n)，跳表的查询的时间复杂度为 O(logn）
public static class SkipListNode<K extends Comparable<K>, V> { public K key; public V val; public ArrayList<SkipListNode<K, V>> nextNodes; public SkipListNode(K k, V v) { key = k; val = v; nextNodes = new ArrayList<SkipListNode<K, V>>(); } // 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束 // 头(null), 头节点的null，认为最小 // node -> 头，node(null, "") node.isKeyLess(!null) true // node里面的key是否比otherKey小，true，不是false public boolean isKeyLess(K otherKey) { // otherKey == null -> false 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); } } 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); // 0 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) { // 从上层跳下层 // 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); } // 新增、改value public void put(K key, V value) { if (key == null) { return; } // 0层上，最右一个，< key 的Node -> >key SkipListNode<K, V> less = mostRightLessNodeInTree(key); SkipListNode<K, V> find = less.nextNodes.get(0); if (find != null && find.isKeyEqual(key)) { find.val = value; } else { // find == null 8 7 9 size++; int newNodeLevel = 0; while (Math.random() < PROBABILITY) { newNodeLevel++; } // 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 = 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 ceilingKey(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; } }
