import java.util.ArrayList;public class SkipList { // Node of the SkipList public static class SkipListNode<K extends Comparable, V> { public K key; public V value; public ArrayList<SkipListNode> nextNodes; public SkipListNode(K key, V value) { this.key = key; this.value = value; nextNodes = new ArrayList<SkipListNode>(); } } // SkipList public static class SkipListMap<K extends Comparable, V> { public static final double PROBABILITY = 0.5; // Probability for level generation public SkipListNode head; public int maxLevel; // Maximum level in the SkipList public int size; public SkipListMap() { // The head is the leftmost "platform" this.head = new SkipListNode(null, null); head.nextNodes.add(null); // Level 0 this.size = 0; this.maxLevel = 0; } // Add a node to the SkipList public void put(K key, V value) { if (key == null) { return; } // Check if the key already exists in the SkipList, update the value if so // Method: Find the rightmost node less than the key at the bottom level SkipListNode less = mostRightLessNodeInTree(key); // less.nextNodes.get(0) -- SkipListNode find = less.nextNodes.get(0); if (find.key.compareTo(key) == 0) { find.value = value; } else { // Generate a random level for the new node int newNodeLevel = 0; while (Math.random() maxLevel) { maxLevel++; head.nextNodes.add(null); } SkipListNode newNode = new SkipListNode(key, value); for (int i = 0; i < newNodeLevel; i++) { newNode.nextNodes.add(null); } int level = maxLevel; SkipListNode pre = head; while (level >= 0) { // Find the predecessor node at the current level pre = mostRightLessNodeInLevel(pre, key, level); // Insert the new node between the predecessor and its successor if (level <= newNodeLevel) { newNode.nextNodes.set(level, pre.nextNodes.get(level)); pre.nextNodes.set(level, newNode); } level--; } size++; } } // Remove a node from the SkipList public void remove(K key) { // Check if the key exists in the SkipList if (!containsKey(key)) { return; } size--; // Start from the top level, remove the node at each level until the bottom int level = maxLevel; SkipListNode pre = head; while (level >= 0) { // Find the predecessor node at the current level pre = mostRightLessNodeInLevel(pre, key, level); // Remove the node SkipListNode next = pre.nextNodes.get(level); if (next != null && next.key.compareTo(key) == 0) { pre.nextNodes.set(level, next.nextNodes.get(level)); } // If a level has only the head node left, remove this level if (level != 0 && pre == head && pre.nextNodes.get(level) == null) { head.nextNodes.remove(level); maxLevel--; } level--; } } // Start from the top level and traverse down to find the rightmost node less than the key at level 0 public SkipListNode mostRightLessNodeInTree(K key) { if (key == null) { return null; } int level = maxLevel; SkipListNode cur = head; while (level >= 0) { cur = mostRightLessNodeInLevel(cur, key, level); level--; } return cur; } // At a specific level, find the rightmost node less than the key public SkipListNode mostRightLessNodeInLevel(SkipListNode cur, K key, int level) { if (key == null) { return null; } SkipListNode pre = null; cur = cur.nextNodes.get(level); while (cur.key.compareTo(key) < 0) { pre = cur; cur = cur.nextNodes.get(level); } return pre; } // Check if the SkipList contains the given key public Boolean containsKey(K key) { if (key == null) { return false; } SkipListNode less = mostRightLessNodeInTree(key); SkipListNode find = less.nextNodes.get(0); return find != null && find.key.compareTo(key) == 0; } }}
以上就是写Java的Skiplist的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/191206.html
微信扫一扫 
支付宝扫一扫 
