有序表（O(logN)）

平衡搜索二叉树（BST）：红黑树、AVL树、SBT，
跳表，它们的时间复杂度一样
相同点：都是一棵搜索二叉树，都具有左旋和右旋操作，保持树的平衡。
不同点：左旋和右旋的实际操作不同。

何为具有平衡性的树？

介绍树的左旋
介绍树的右旋

AVL树

何时进行左旋或者右旋：在进行插入和删除时，如果左子树和右子树的高度差相差为1，进行，而且要判断当前节点的父节点的左子树和右子树的高度差相差为1，直到根结点。
旋转的时机：LL（左边的左子树过长）、RR（右边的右子树过长）、LR（左边的右子树过长）、RL（右边的左子树过长）
AbstractBinarySearchTree

  1. public class AbstractBinarySearchTree {
  3.     /** Root node where whole tree starts. */
  4.     public Node root;
  6.     /** Tree size. */
  7.     protected int size;
  9.     /**
  10.      * Because this is abstract class and various trees have different
  11.      * additional information on different nodes subclasses uses this abstract
  12.      * method to create nodes (maybe of class {@link Node} or maybe some
  13.      * different node sub class).
  14.      * 
  15.      * @param value
  16.      *            Value that node will have.
  17.      * @param parent
  18.      *            Node's parent.
  19.      * @param left
  20.      *            Node's left child.
  21.      * @param right
  22.      *            Node's right child.
  23.      * @return Created node instance.
  24.      */
  25.     protected Node createNode(int value, Node parent, Node left, Node right) {
  26.         return new Node(value, parent, left, right);
  27.     }
  29.     /**
  30.      * Finds a node with concrete value. If it is not found then null is
  31.      * returned.
  32.      * 
  33.      * @param element
  34.      *            Element value.
  35.      * @return Node with value provided, or null if not found.
  36.      */
  37.     public Node search(int element) {
  38.         Node node = root;
  39.         while (node != null && node.value != null && node.value != element) {
  40.             if (element < node.value) {
  41.                 node = node.left;
  42.             } else {
  43.                 node = node.right;
  44.             }
  45.         }
  46.         return node;
  47.     }
  49.     /**
  50.      * Insert new element to tree.
  51.      * 
  52.      * @param element
  53.      *            Element to insert.
  54.      */
  55.     public Node insert(int element) {
  56.         if (root == null) {
  57.             root = createNode(element, null, null, null);
  58.             size++;
  59.             return root;
  60.         }
  62.         Node insertParentNode = null;
  63.         Node searchTempNode = root;
  64.         while (searchTempNode != null && searchTempNode.value != null) {
  65.             insertParentNode = searchTempNode;
  66.             if (element < searchTempNode.value) {
  67.                 searchTempNode = searchTempNode.left;
  68.             } else {
  69.                 searchTempNode = searchTempNode.right;
  70.             }
  71.         }
  73.         Node newNode = createNode(element, insertParentNode, null, null);
  74.         if (insertParentNode.value > newNode.value) {
  75.             insertParentNode.left = newNode;
  76.         } else {
  77.             insertParentNode.right = newNode;
  78.         }
  80.         size++;
  81.         return newNode;
  82.     }
  84.     /**
  85.      * Removes element if node with such value exists.
  86.      * 
  87.      * @param element
  88.      *            Element value to remove.
  89.      * 
  90.      * @return New node that is in place of deleted node. Or null if element for
  91.      *         delete was not found.
  92.      */
  93.     public Node delete(int element) {
  94.         Node deleteNode = search(element);
  95.         if (deleteNode != null) {
  96.             return delete(deleteNode);
  97.         } else {
  98.             return null;
  99.         }
  100.     }
  102.     /**
  103.      * Delete logic when node is already found.
  104.      * 
  105.      * @param deleteNode
  106.      *            Node that needs to be deleted.
  107.      * 
  108.      * @return New node that is in place of deleted node. Or null if element for
  109.      *         delete was not found.
  110.      */
  111.     protected Node delete(Node deleteNode) {
  112.         if (deleteNode != null) {
  113.             Node nodeToReturn = null;
  114.             if (deleteNode != null) {
  115.                 if (deleteNode.left == null) {
  116.                     nodeToReturn = transplant(deleteNode, deleteNode.right);
  117.                 } else if (deleteNode.right == null) {
  118.                     nodeToReturn = transplant(deleteNode, deleteNode.left);
  119.                 } else {
  120.                     Node successorNode = getMinimum(deleteNode.right);
  121.                     if (successorNode.parent != deleteNode) {
  122.                         transplant(successorNode, successorNode.right);
  123.                         successorNode.right = deleteNode.right;
  124.                         successorNode.right.parent = successorNode;
  125.                     }
  126.                     transplant(deleteNode, successorNode);
  127.                     successorNode.left = deleteNode.left;
  128.                     successorNode.left.parent = successorNode;
  129.                     nodeToReturn = successorNode;
  130.                 }
  131.                 size--;
  132.             }
  133.             return nodeToReturn;
  134.         }
  135.         return null;
  136.     }
  138.     /**
  139.      * Put one node from tree (newNode) to the place of another (nodeToReplace).
  140.      * 
  141.      * @param nodeToReplace
  142.      *            Node which is replaced by newNode and removed from tree.
  143.      * @param newNode
  144.      *            New node.
  145.      * 
  146.      * @return New replaced node.
  147.      */
  148.     private Node transplant(Node nodeToReplace, Node newNode) {
  149.         if (nodeToReplace.parent == null) {
  150.             this.root = newNode;
  151.         } else if (nodeToReplace == nodeToReplace.parent.left) {
  152.             nodeToReplace.parent.left = newNode;
  153.         } else {
  154.             nodeToReplace.parent.right = newNode;
  155.         }
  156.         if (newNode != null) {
  157.             newNode.parent = nodeToReplace.parent;
  158.         }
  159.         return newNode;
  160.     }
  162.     /**
  163.      * @param element
  164.      * @return true if tree contains element.
  165.      */
  166.     public boolean contains(int element) {
  167.         return search(element) != null;
  168.     }
  170.     /**
  171.      * @return Minimum element in tree.
  172.      */
  173.     public int getMinimum() {
  174.         return getMinimum(root).value;
  175.     }
  177.     /**
  178.      * @return Maximum element in tree.
  179.      */
  180.     public int getMaximum() {
  181.         return getMaximum(root).value;
  182.     }
  184.     /**
  185.      * Get next element element who is bigger than provided element.
  186.      * 
  187.      * @param element
  188.      *            Element for whom descendand element is searched
  189.      * @return Successor value.
  190.      */
  191.     // TODO Predecessor
  192.     public int getSuccessor(int element) {
  193.         return getSuccessor(search(element)).value;
  194.     }
  196.     /**
  197.      * @return Number of elements in the tree.
  198.      */
  199.     public int getSize() {
  200.         return size;
  201.     }
  203.     /**
  204.      * Tree traversal with printing element values. In order method.
  205.      */
  206.     public void printTreeInOrder() {
  207.         printTreeInOrder(root);
  208.     }
  210.     /**
  211.      * Tree traversal with printing element values. Pre order method.
  212.      */
  213.     public void printTreePreOrder() {
  214.         printTreePreOrder(root);
  215.     }
  217.     /**
  218.      * Tree traversal with printing element values. Post order method.
  219.      */
  220.     public void printTreePostOrder() {
  221.         printTreePostOrder(root);
  222.     }
  224.     /*-------------------PRIVATE HELPER METHODS-------------------*/
  226.     private void printTreeInOrder(Node entry) {
  227.         if (entry != null) {
  228.             printTreeInOrder(entry.left);
  229.             if (entry.value != null) {
  230.                 System.out.println(entry.value);
  231.             }
  232.             printTreeInOrder(entry.right);
  233.         }
  234.     }
  236.     private void printTreePreOrder(Node entry) {
  237.         if (entry != null) {
  238.             if (entry.value != null) {
  239.                 System.out.println(entry.value);
  240.             }
  241.             printTreeInOrder(entry.left);
  242.             printTreeInOrder(entry.right);
  243.         }
  244.     }
  246.     private void printTreePostOrder(Node entry) {
  247.         if (entry != null) {
  248.             printTreeInOrder(entry.left);
  249.             printTreeInOrder(entry.right);
  250.             if (entry.value != null) {
  251.                 System.out.println(entry.value);
  252.             }
  253.         }
  254.     }
  256.     protected Node getMinimum(Node node) {
  257.         while (node.left != null) {
  258.             node = node.left;
  259.         }
  260.         return node;
  261.     }
  263.     protected Node getMaximum(Node node) {
  264.         while (node.right != null) {
  265.             node = node.right;
  266.         }
  267.         return node;
  268.     }
  270.     protected Node getSuccessor(Node node) {
  271.         // if there is right branch, then successor is leftmost node of that
  272.         // subtree
  273.         if (node.right != null) {
  274.             return getMinimum(node.right);
  275.         } else { // otherwise it is a lowest ancestor whose left child is also
  276.             // ancestor of node
  277.             Node currentNode = node;
  278.             Node parentNode = node.parent;
  279.             while (parentNode != null && currentNode == parentNode.right) {
  280.                 // go up until we find parent that currentNode is not in right
  281.                 // subtree.
  282.                 currentNode = parentNode;
  283.                 parentNode = parentNode.parent;
  284.             }
  285.             return parentNode;
  286.         }
  287.     }
  289.     // -------------------------------- TREE PRINTING
  290.     // ------------------------------------
  292.     public void printTree() {
  293.         printSubtree(root);
  294.     }
  296.     public void printSubtree(Node node) {
  297.         if (node.right != null) {
  298.             printTree(node.right, true, "");
  299.         }
  300.         printNodeValue(node);
  301.         if (node.left != null) {
  302.             printTree(node.left, false, "");
  303.         }
  304.     }
  306.     private void printNodeValue(Node node) {
  307.         if (node.value == null) {
  308.             System.out.print("<null>");
  309.         } else {
  310.             System.out.print(node.value.toString());
  311.         }
  312.         System.out.println();
  313.     }
  315.     private void printTree(Node node, boolean isRight, String indent) {
  316.         if (node.right != null) {
  317.             printTree(node.right, true, indent + (isRight ? "        " : " |      "));
  318.         }
  319.         System.out.print(indent);
  320.         if (isRight) {
  321.             System.out.print(" /");
  322.         } else {
  323.             System.out.print(" \\");
  324.         }
  325.         System.out.print("----- ");
  326.         printNodeValue(node);
  327.         if (node.left != null) {
  328.             printTree(node.left, false, indent + (isRight ? " |      " : "        "));
  329.         }
  330.     }
  332.     public static class Node {
  333.         public Node(Integer value, Node parent, Node left, Node right) {
  334.             super();
  335.             this.value = value;
  336.             this.parent = parent;
  337.             this.left = left;
  338.             this.right = right;
  339.         }
  341.         public Integer value;
  342.         public Node parent;
  343.         public Node left;
  344.         public Node right;
  346.         public boolean isLeaf() {
  347.             return left == null && right == null;
  348.         }
  350.         @Override
  351.         public int hashCode() {
  352.             final int prime = 31;
  353.             int result = 1;
  354.             result = prime * result + ((value == null) ? 0 : value.hashCode());
  355.             return result;
  356.         }
  358.         @Override
  359.         public boolean equals(Object obj) {
  360.             if (this == obj)
  361.                 return true;
  362.             if (obj == null)
  363.                 return false;
  364.             if (getClass() != obj.getClass())
  365.                 return false;
  366.             Node other = (Node) obj;
  367.             if (value == null) {
  368.                 if (other.value != null)
  369.                     return false;
  370.             } else if (!value.equals(other.value))
  371.                 return false;
  372.             return true;
  373.         }
  375.     }
  376. }

AVLTree

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);
        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);
            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) {
                if (node.right.right != null) {
                    node = (AVLNode)avlRotateLeft(node);
                    break;
                } else {
                    node = (AVLNode)doubleRotateRightLeft(node);
                    break;
                }
            } else if (nodeBalance == -2) {
                if (node.left.left != null) {
                    node = (AVLNode)avlRotateRight(node);
                    break;
                } else {
                    node = (AVLNode)doubleRotateLeftRight(node);
                    break;
                }
            } else {
                updateHeight(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
     * 
     */
    protected static class AVLNode extends Node {
        public int height;

        public AVLNode(int value, Node parent, Node left, Node right) {
            super(value, parent, left, right);
        }
    }
}

SB树

平衡性：

每棵子树的大小，不小于其兄弟的子树大小，既每棵叔叔树的大小，不小于其任何侄子树的大小

何时进行左旋和右旋？

插入和删除需要进行
LL
image.png
image.png

public class SizeBalancedTreeMap {

    public static class SBTNode<K extends Comparable<K>, V> {
        public K key;
        public V value;
        public SBTNode<K, V> l;
        public SBTNode<K, V> r;
        public int size;

        public SBTNode(K key, V value) {
            this.key = key;
            this.value = value;
            size = 1;
        }
    }

    public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
        private SBTNode<K, V> root;

        private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
            SBTNode<K, V> leftNode = cur.l;
            cur.l = leftNode.r;
            leftNode.r = cur;
            leftNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
            return leftNode;
        }

        private SBTNode<K, V> leftRotate(SBTNode<K, V> cur) {
            SBTNode<K, V> rightNode = cur.r;
            cur.r = rightNode.l;
            rightNode.l = cur;
            rightNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
            return rightNode;
        }

        // 如果出现不达标的情况，调整
        private SBTNode<K, V> matain(SBTNode<K, V> cur) {
            if (cur == null) {
                return null;
            }
            if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
                cur = rightRotate(cur);
                cur.r = matain(cur.r);
                cur = matain(cur);
            } else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {
                cur.l = leftRotate(cur.l);
                cur = rightRotate(cur);
                cur.l = matain(cur.l);
                cur.r = matain(cur.r);
                cur = matain(cur);
            } else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {
                cur = leftRotate(cur);
                cur.l = matain(cur.l);
                cur = matain(cur);
            } else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {
                cur.r = rightRotate(cur.r);
                cur = leftRotate(cur);
                cur.l = matain(cur.l);
                cur.r = matain(cur.r);
                cur = matain(cur);
            }
            return cur;
        }

        private SBTNode<K, V> findLastIndex(K key) {
            SBTNode<K, V> pre = root;
            SBTNode<K, V> cur = root;
            while (cur != null) {
                pre = cur;
                if (key.compareTo(cur.key) == 0) {
                    break;
                } else if (key.compareTo(cur.key) < 0) {
                    cur = cur.l;
                } else {
                    cur = cur.r;
                }
            }
            return pre;
        }

        private SBTNode<K, V> findLastNoSmallIndex(K key) {
            SBTNode<K, V> ans = null;
            SBTNode<K, V> cur = root;
            while (cur != null) {
                if (key.compareTo(cur.key) == 0) {
                    ans = cur;
                    break;
                } else if (key.compareTo(cur.key) < 0) {
                    ans = cur;
                    cur = cur.l;
                } else {
                    cur = cur.r;
                }
            }
            return ans;
        }

        private SBTNode<K, V> findLastNoBigIndex(K key) {
            SBTNode<K, V> ans = null;
            SBTNode<K, V> cur = root;
            while (cur != null) {
                if (key.compareTo(cur.key) == 0) {
                    ans = cur;
                    break;
                } else if (key.compareTo(cur.key) < 0) {
                    cur = cur.l;
                } else {
                    ans = cur;
                    cur = cur.r;
                }
            }
            return ans;
        }

        private SBTNode<K, V> add(SBTNode<K, V> cur, K key, V value) {
            if (cur == null) {
                return new SBTNode<K, V>(key, value);
            } else {
                cur.size++;
                if (key.compareTo(cur.key) < 0) {
                    cur.l = add(cur.l, key, value);
                } else {
                    cur.r = add(cur.r, key, value);
                }
                return matain(cur);
            }
        }

        private SBTNode<K, V> delete(SBTNode<K, V> cur, K key) {
            cur.size--;
            if (key.compareTo(cur.key) > 0) {
                cur.r = delete(cur.r, key);
            } else if (key.compareTo(cur.key) < 0) {
                cur.l = delete(cur.l, key);
            } else {
                if (cur.l == null && cur.r == null) {
                    // free cur memory -> C++
                    cur = null;
                } else if (cur.l == null && cur.r != null) {
                    // free cur memory -> C++
                    cur = cur.r;
                } else if (cur.l != null && cur.r == null) {
                    // free cur memory -> C++
                    cur = cur.l;
                } else {
                    SBTNode<K, V> pre = null;
                    SBTNode<K, V> des = cur.r;
                    des.size--;
                    while (des.l != null) {
                        pre = des;
                        des = des.l;
                        des.size--;
                    }
                    if (pre != null) {
                        pre.l = des.r;
                        des.r = cur.r;
                    }
                    des.l = cur.l;
                    des.size = des.l.size + des.r.size + 1;
                    // free cur memory -> C++
                    cur = des;
                }
            }
            return cur;
        }

        private SBTNode<K, V> getIndex(SBTNode<K, V> cur, int kth) {
            if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
                return cur;
            } else if (kth <= (cur.l != null ? cur.l.size : 0)) {
                return getIndex(cur.l, kth);
            } else {
                return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
            }
        }

        public int size() {
            return root == null ? 0 : root.size;
        }

        public boolean containsKey(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNode = findLastIndex(key);
            return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
        }

        public void put(K key, V value) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNode = findLastIndex(key);
            if (lastNode != null && key.compareTo(lastNode.key) == 0) {
                lastNode.value = value;
            } else {
                root = add(root, key, value);
            }
        }

        public void remove(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            if (containsKey(key)) {
                root = delete(root, key);
            }
        }

        public K getIndexKey(int index) {
            if (index < 0 || index >= this.size()) {
                throw new RuntimeException("invalid parameter.");
            }
            return getIndex(root, index + 1).key;
        }

        public V getIndexValue(int index) {
            if (index < 0 || index >= this.size()) {
                throw new RuntimeException("invalid parameter.");
            }
            return getIndex(root, index + 1).value;
        }

        public V get(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNode = findLastIndex(key);
            if (lastNode != null && key.compareTo(lastNode.key) == 0) {
                return lastNode.value;
            } else {
                return null;
            }
        }

        public K firstKey() {
            if (root == null) {
                return null;
            }
            SBTNode<K, V> cur = root;
            while (cur.l != null) {
                cur = cur.l;
            }
            return cur.key;
        }

        public K lastKey() {
            if (root == null) {
                return null;
            }
            SBTNode<K, V> cur = root;
            while (cur.r != null) {
                cur = cur.r;
            }
            return cur.key;
        }

        public K floorKey(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
            return lastNoBigNode == null ? null : lastNoBigNode.key;
        }

        public K ceilingKey(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
            return lastNoSmallNode == null ? null : lastNoSmallNode.key;
        }

    }

    // for test
    public static void printAll(SBTNode<String, Integer> head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    // for test
    public static void printInOrder(SBTNode<String, Integer> head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.r, height + 1, "v", len);
        String val = to + "(" + head.key + "," + head.value + ")" + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.l, height + 1, "^", len);
    }

    // for test
    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    public static void main(String[] args) {
        SizeBalancedTreeMap<String, Integer> sbt = new SizeBalancedTreeMap<String, Integer>();
        sbt.put("d", 4);
        sbt.put("c", 3);
        sbt.put("a", 1);
        sbt.put("b", 2);
        // sbt.put("e", 5);
        sbt.put("g", 7);
        sbt.put("f", 6);
        sbt.put("h", 8);
        sbt.put("i", 9);
        sbt.put("a", 111);
        System.out.println(sbt.get("a"));
        sbt.put("a", 1);
        System.out.println(sbt.get("a"));
        for (int i = 0; i < sbt.size(); i++) {
            System.out.println(sbt.getIndexKey(i) + " , " + sbt.getIndexValue(i));
        }
        printAll(sbt.root);
        System.out.println(sbt.firstKey());
        System.out.println(sbt.lastKey());
        System.out.println(sbt.floorKey("g"));
        System.out.println(sbt.ceilingKey("g"));
        System.out.println(sbt.floorKey("e"));
        System.out.println(sbt.ceilingKey("e"));
        System.out.println(sbt.floorKey(""));
        System.out.println(sbt.ceilingKey(""));
        System.out.println(sbt.floorKey("j"));
        System.out.println(sbt.ceilingKey("j"));
        sbt.remove("d");
        printAll(sbt.root);
        sbt.remove("f");
        printAll(sbt.root);
    }
}

跳表

image.png

public class SkipListMap {

    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>>();
        }

        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);
        }

    }

    public static class SkipListMap<K extends Comparable<K>, V> {
        private static final double PROBABILITY = 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;
        }

        private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
            if (key == null) {
                return null;
            }
            int level = maxLevel;
            SkipListNode<K, V> cur = head;
            while (level >= 0) {
                cur = mostRightLessNodeInLevel(key, cur, level--);
            }
            return cur;
        }

        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);
        }

        public void put(K key, V value) {
            if (key == null) {
                return;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> find = less.nextNodes.get(0);
            if (find != null && find.isKeyEqual(key)) {
                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<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) {
                    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);
                    if (next != null && next.isKeyEqual(key)) {
                        // free delete node memory -> C++
                        pre.nextNodes.set(level, next.nextNodes.get(level));
                    }
                    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"));
    }
}