标签：二次   ringbuf   main   查询   while   func   abi   移动   ack   

算法 - 第八章 Morris遍历/搜索二叉树/跳表等（完结）

Morris遍历

• Morris遍历实现二叉树的先中后序遍历，时间复杂度O(n)，额外空间复杂度O(1)

  • 如果使用递归/非递归版本都是使用栈来完成二叉树遍历，因为只有指向子指针没有指向父指针，有额外的栈空间。

  • Morris遍历实际上就是一个仿真递归的一个遍历过程，一个二叉树递归实际上会经过自己三次，第一次看左第二次看右第三次返回。哪次打印结点，就是属于哪种遍历方式 - 第一次打印就是先序，第二次打印就是中序

  • 当前节点Cur，一开始Cur指向根节点

    • Cur无左子树，Cur向右移动：Cur=Cur.right
    • Cur有左子树，找左子树上最右节点，mostRight；1）mostRight的右孩子为null，则mostRight.right=Cur，Cur向左移动（左子树移动）。（第一次）2）mostRight的右孩子为当前节点，则mostRight.right=null，Cur向右移动（右子树移动）（第二次）
    • 这样的操作实际上就完成了一个类似于栈的操作，保存了父结点位置信息（mostRight.right=Cur）。
    • Morris遍历就是一个对于任何一个有左子树的结点两次回到自己，对于没有左子树的结点只回到一次，整体符合先中间再左回到中间再右的顺序。
    • 因为Morris遍历没有第三次来到当前的结点时候，所以前中序比较好实现，后序实现需要改动下：当第二次回到当前结点的时候逆序（链表逆序打印再转回来）打印左子树的右边界（printEdge）。

  • 算法实现（java）

	public static class Node {
		public int value;
		Node left;
		Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static void morrisIn(Node head) { // 中序遍历
		if (head == null) {
			return;
		}
		Node cur1 = head;
		Node cur2 = null;
		while (cur1 != null) {
			cur2 = cur1.left;
			if (cur2 != null) { // 有无左子树
				while (cur2.right != null && cur2.right != cur1) {  // 找到左子树最右结点
					cur2 = cur2.right;
				}
				if (cur2.right == null) {	// 第一次找到，向左移动
					cur2.right = cur1;
					cur1 = cur1.left;
					continue;
				} else {
					cur2.right = null; // 第二次找到，向右移动
				}
			}
			System.out.print(cur1.value + " ");
			cur1 = cur1.right; // 向右移动
		}
		System.out.println();
	}

	public static void morrisPre(Node head) { // 先序遍历
		if (head == null) {
			return;
		}
		Node cur1 = head;
		Node cur2 = null;
		while (cur1 != null) {
			cur2 = cur1.left;
			if (cur2 != null) {
				while (cur2.right != null && cur2.right != cur1) {
					cur2 = cur2.right;
				}
				if (cur2.right == null) {
					cur2.right = cur1;
					System.out.print(cur1.value + " ");
					cur1 = cur1.left;
					continue;
				} else {
					cur2.right = null;
				}
			} else {
				System.out.print(cur1.value + " ");
			}
			cur1 = cur1.right;
		}
		System.out.println();
	}

	public static void morrisPos(Node head) { // 后序遍历
		if (head == null) {
			return;
		}
		Node cur1 = head;
		Node cur2 = null;
		while (cur1 != null) {
			cur2 = cur1.left;
			if (cur2 != null) {
				while (cur2.right != null && cur2.right != cur1) {
					cur2 = cur2.right;
				}
				if (cur2.right == null) {
					cur2.right = cur1;
					cur1 = cur1.left;
					continue;
				} else {
					cur2.right = null;
					printEdge(cur1.left);
				}
			}
			cur1 = cur1.right;
		}
		printEdge(head);
		System.out.println();
	}

	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}

	public static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while (from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}

	// for test -- print tree
	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + 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.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i 

搜索二叉树 / AVL / 红黑树 / SB树

• 搜索二叉树：左子树都比该节点小，右节点都比该节点大 - 便于查询，最大代价为树高O(lgn)

  • 搜索、插入、删除（非全子树直接替换，全子树找后继节点替换）
  • 缺乏平衡性，搜索效率失衡
  • 算法实现（java）- 增删查
  • 搜索二叉树的平衡性：都是为了让搜索二叉树不退化成棒状，保持h(logn)高度的设定。
  • 以下三种树（AVL，红黑，SB）都是对搜索二叉树的改良，使其保持一定的平衡性，但是本质上没有太大差别，实现的功能都是搜索二叉树，区别就是调整算法成本差别，但都是O(logn)的调整，相差在常数。
  • 三种树对失衡的调整都是基于两个源动作的组合，只是发生操作的次数和发生操作的节点区别：
    • 左/右旋：根节点跑到调整新节点的哪边，就是那种旋法。eg. 右旋，就是三个节点，我（根节点）变成左孩子的右孩子，原来左孩子的右孩子变成我的左孩子，原来的左孩子变成我的父结点。/ 左旋，我（根节点）变成右孩子的左孩子，原来右孩子的左孩子变成我的右孩子，原来的右孩子变成我的父结点。
    • 算法实现（java） - 左右旋
    • 失衡调整地点：在插入 / 删除节点往上找到的第一个失衡节点时调整他，那么整个树就平衡了。

• AVL树平衡二叉树：

  • 平衡性：左子树与右子树高度相差不超过1。 - 平衡性的严苛导致失衡后的调整比较频繁
  • AVL失衡类型：LL型 / LR型 / RL型 / RR型 - LL(左左失衡)/RR型就直接右旋/左旋即可，LR/RL就是把下面先进行一次调整变成LL/RR型（LR对应先进行RR，RL对应先进行LL），再来右旋/左旋

• 红黑树：

  • 一个节点要么是红色要么是黑色
  • 根节点一定是黑色，叶子节点一定是黑色
  • 每个红色的子结点一定是黑色（不同相邻红）
  • 任何节点的左右子链包含黑色节点数量一样
  • 红黑树的平衡性：任何节点出发的链，长链不能超过短链的两倍
  • 调整相比AVL和SB的coding都要复杂，相比而言没有本质区别。
  • 红黑树的调整情况太多，删除五种插入八种，不管那种操作基本操作都是一样的，只不过是由于定义/平衡性不一样而区别的。

• SB树：

  • SB树的平衡性：任何一个侄子节点的结点个数都不能比叔叔节点的结点个数大（叔叔节点不小于侄子节点子树节点数）

// 二叉搜索树
	public Node root;

	/** Tree size. */
	protected int size;

	/**
	 * Because this is abstract class and various trees have different
	 * additional information on different nodes subclasses uses this abstract
	 * method to create nodes (maybe of class {@link Node} or maybe some
	 * different node sub class).
	 * 
	 * @param value
	 *            Value that node will have.
	 * @param parent
	 *            Node‘s parent.
	 * @param left
	 *            Node‘s left child.
	 * @param right
	 *            Node‘s right child.
	 * @return Created node instance.
	 */
	protected Node createNode(int value, Node parent, Node left, Node right) {
		return new Node(value, parent, left, right);
	}

	/**
	 * Finds a node with concrete value. If it is not found then null is
	 * returned.
	 * 
	 * @param element
	 *            Element value.
	 * @return Node with value provided, or null if not found.
	 */
	public Node search(int element) {	// 搜索数，如果没找到就是null空结点
		Node node = root;
		while (node != null && node.value != null && node.value != element) { 
			if (element  newNode.value) {	// 查看父结点与插入节点的位置比较
			insertParentNode.left = newNode;
		} else {
			insertParentNode.right = newNode;
		}

		size++;
		return newNode;
	}

	/**
	 * Removes element if node with such value exists.
	 * 
	 * @param element
	 *            Element value to remove.
	 * 
	 * @return New node that is in place of deleted node. Or null if element for
	 *         delete was not found.
	 */
	public Node delete(int element) {
		Node deleteNode = search(element);
		if (deleteNode != null) {
			return delete(deleteNode);
		} else {
			return null;
		}
	}

	/**
	 * Delete logic when node is already found.
	 * 
	 * @param deleteNode
	 *            Node that needs to be deleted.
	 * 
	 * @return New node that is in place of deleted node. Or null if element for
	 *         delete was not found.
	 */
	protected Node delete(Node deleteNode) {	// 
		if (deleteNode != null) {
			Node nodeToReturn = null;
			if (deleteNode != null) {
				if (deleteNode.left == null) {	// 如果没有左子树
					nodeToReturn = transplant(deleteNode, deleteNode.right); // 从右子树找个替换该节点
				} else if (deleteNode.right == null) { // 如果没有右子树
					nodeToReturn = transplant(deleteNode, deleteNode.left); // 从左子树找个替换该节点
				} else {	// 如果两个子树都有
					Node successorNode = getMinimum(deleteNode.right); // 找到右子树最小值（该节点的后继节点）
					if (successorNode.parent != deleteNode) {
						transplant(successorNode, successorNode.right);	 // 后继节点是肯定没有左孩子的（否则就不是右子树最小值了）
						successorNode.right = deleteNode.right;
						successorNode.right.parent = successorNode;
					}
					transplant(deleteNode, successorNode);
					successorNode.left = deleteNode.left;
					successorNode.left.parent = successorNode;
					nodeToReturn = successorNode;
				}
				size--;
			}

			return nodeToReturn;
		}
		return null;
	}

	/**
	 * Put one node from tree (newNode) to the place of another (nodeToReplace).
	 * 
	 * @param nodeToReplace
	 *            Node which is replaced by newNode and removed from tree.
	 * @param newNode
	 *            New node.
	 * 
	 * @return New replaced node.
	 */
	private Node transplant(Node nodeToReplace, Node newNode) { // 就是两个节点与其他节点连接环境的替换
		if (nodeToReplace.parent == null) { //根节点
			this.root = newNode;
		} else if (nodeToReplace == nodeToReplace.parent.left) {
			nodeToReplace.parent.left = newNode;
		} else {
			nodeToReplace.parent.right = newNode;
		}
		if (newNode != null) {
			newNode.parent = nodeToReplace.parent;
		}
		return newNode;
	}

	/**
	 * @param element
	 * @return true if tree contains element.
	 */
	public boolean contains(int element) {
		return search(element) != null;
	}

	/**
	 * @return Minimum element in tree.
	 */
	public int getMinimum() {
		return getMinimum(root).value;
	}

	/**
	 * @return Maximum element in tree.
	 */
	public int getMaximum() {
		return getMaximum(root).value;
	}
	
// 左右旋
    /**
     * Rotate to the left.
     * 
     * @param node Node on which to rotate.
     * @return Node that is in place of provided node after rotation.
     */
    protected Node rotateLeft(Node node) {
        Node temp = node.right;
        temp.parent = node.parent;

        node.right = temp.left;
        if (node.right != null) {
            node.right.parent = node;
        }

        temp.left = node;
        node.parent = temp;

        // temp took over node‘s place so now its parent should point to temp
        if (temp.parent != null) {
            if (node == temp.parent.left) {
                temp.parent.left = temp;
            } else {
                temp.parent.right = temp;
            }
        } else {
            root = temp;
        }
        
        return temp;
    }

    /**
     * Rotate to the right.
     * 
     * @param node Node on which to rotate.
     * @return Node that is in place of provided node after rotation.
     */
    protected Node rotateRight(Node node) {
        Node temp = node.left;
        temp.parent = node.parent;

        node.left = temp.right;
        if (node.left != null) {
            node.left.parent = node;
        }

        temp.right = node;
        node.parent = temp;

        // temp took over node‘s place so now its parent should point to temp
        if (temp.parent != null) {
            if (node == temp.parent.left) {
                temp.parent.left = temp;
            } else {
                temp.parent.right = temp;
            }
        } else {
            root = temp;
        }
        
        return temp;
    }
    
// 红黑树
public class RedBlackTree extends AbstractSelfBalancingBinarySearchTree {

    protected enum ColorEnum {
        RED,
        BLACK
    };

    protected static final RedBlackNode nilNode = new RedBlackNode(null, null, null, null, ColorEnum.BLACK);

    /**
     * @see trees.AbstractBinarySearchTree#insert(int)
     */
    @Override
    public Node insert(int element) {
        Node newNode = super.insert(element);
        newNode.left = nilNode;
        newNode.right = nilNode;
        root.parent = nilNode;
        insertRBFixup((RedBlackNode) newNode);
        return newNode;
    }
    
    /**
     * Slightly modified delete routine for red-black tree.
     * 
     * {@inheritDoc}
     */
    @Override
    protected Node delete(Node deleteNode) {
        Node replaceNode = null; // track node that replaces removedOrMovedNode
        if (deleteNode != null && deleteNode != nilNode) {
            Node removedOrMovedNode = deleteNode; // same as deleteNode if it has only one child, and otherwise it replaces deleteNode
            ColorEnum removedOrMovedNodeColor = ((RedBlackNode)removedOrMovedNode).color;
        
            if (deleteNode.left == nilNode) {
                replaceNode = deleteNode.right;
                rbTreeTransplant(deleteNode, deleteNode.right);
            } else if (deleteNode.right == nilNode) {
                replaceNode = deleteNode.left;
                rbTreeTransplant(deleteNode, deleteNode.left);
            } else {
                removedOrMovedNode = getMinimum(deleteNode.right);
                removedOrMovedNodeColor = ((RedBlackNode)removedOrMovedNode).color;
                replaceNode = removedOrMovedNode.right;
                if (removedOrMovedNode.parent == deleteNode) {
                    replaceNode.parent = removedOrMovedNode;
                } else {
                    rbTreeTransplant(removedOrMovedNode, removedOrMovedNode.right);
                    removedOrMovedNode.right = deleteNode.right;
                    removedOrMovedNode.right.parent = removedOrMovedNode;
                }
                rbTreeTransplant(deleteNode, removedOrMovedNode);
                removedOrMovedNode.left = deleteNode.left;
                removedOrMovedNode.left.parent = removedOrMovedNode;
                ((RedBlackNode)removedOrMovedNode).color = ((RedBlackNode)deleteNode).color;
            }
            
            size--;
            if (removedOrMovedNodeColor == ColorEnum.BLACK) {
                deleteRBFixup((RedBlackNode)replaceNode);
            }
        }
        
        return replaceNode;
    }
    
    /**
     * @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 RedBlackNode(value, parent, left, right, ColorEnum.RED);
    }
    
    /**
     * {@inheritDoc}
     */
    @Override
    protected Node getMinimum(Node node) {
        while (node.left != nilNode) {
            node = node.left;
        }
        return node;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    protected Node getMaximum(Node node) {
        while (node.right != nilNode) {
            node = node.right;
        }
        return node;
    }
    
    /**
     * {@inheritDoc}
     */
    @Override
    protected Node rotateLeft(Node node) {
        Node temp = node.right;
        temp.parent = node.parent;
        
        node.right = temp.left;
        if (node.right != nilNode) {
            node.right.parent = node;
        }

        temp.left = node;
        node.parent = temp;

        // temp took over node‘s place so now its parent should point to temp
        if (temp.parent != nilNode) {
            if (node == temp.parent.left) {
                temp.parent.left = temp;
            } else {
                temp.parent.right = temp;
            }
        } else {
            root = temp;
        }
        
        return temp;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    protected Node rotateRight(Node node) {
        Node temp = node.left;
        temp.parent = node.parent;

        node.left = temp.right;
        if (node.left != nilNode) {
            node.left.parent = node;
        }

        temp.right = node;
        node.parent = temp;

        // temp took over node‘s place so now its parent should point to temp
        if (temp.parent != nilNode) {
            if (node == temp.parent.left) {
                temp.parent.left = temp;
            } else {
                temp.parent.right = temp;
            }
        } else {
            root = temp;
        }
        
        return temp;
    }

    
    /**
     * Similar to original transplant() method in BST but uses nilNode instead of null.
     */
    private Node rbTreeTransplant(Node nodeToReplace, Node newNode) {
        if (nodeToReplace.parent == nilNode) {
            this.root = newNode;
        } else if (nodeToReplace == nodeToReplace.parent.left) {
            nodeToReplace.parent.left = newNode;
        } else {
            nodeToReplace.parent.right = newNode;
        }
        newNode.parent = nodeToReplace.parent;
        return newNode;
    }
    
    /**
     * Restores Red-Black tree properties after delete if needed.
     */
    private void deleteRBFixup(RedBlackNode x) {
        while (x != root && isBlack(x)) {
            
            if (x == x.parent.left) {
                RedBlackNode w = (RedBlackNode)x.parent.right;
                if (isRed(w)) { // case 1 - sibling is red
                    w.color = ColorEnum.BLACK;
                    ((RedBlackNode)x.parent).color = ColorEnum.RED;
                    rotateLeft(x.parent);
                    w = (RedBlackNode)x.parent.right; // converted to case 2, 3 or 4
                }
                // case 2 sibling is black and both of its children are black
                if (isBlack(w.left) && isBlack(w.right)) {
                    w.color = ColorEnum.RED;
                    x = (RedBlackNode)x.parent;
                } else if (w != nilNode) {
                    if (isBlack(w.right)) { // case 3 sibling is black and its left child is red and right child is black
                        ((RedBlackNode)w.left).color = ColorEnum.BLACK;
                        w.color = ColorEnum.RED;
                        rotateRight(w);
                        w = (RedBlackNode)x.parent.right;
                    }
                    w.color = ((RedBlackNode)x.parent).color; // case 4 sibling is black and right child is red
                    ((RedBlackNode)x.parent).color = ColorEnum.BLACK;
                    ((RedBlackNode)w.right).color = ColorEnum.BLACK;
                    rotateLeft(x.parent);
                    x = (RedBlackNode)root;
                } else {
                    x.color = ColorEnum.BLACK;
                    x = (RedBlackNode)x.parent;
                }
            } else {
                RedBlackNode w = (RedBlackNode)x.parent.left;
                if (isRed(w)) { // case 1 - sibling is red
                    w.color = ColorEnum.BLACK;
                    ((RedBlackNode)x.parent).color = ColorEnum.RED;
                    rotateRight(x.parent);
                    w = (RedBlackNode)x.parent.left; // converted to case 2, 3 or 4
                }
                // case 2 sibling is black and both of its children are black
                if (isBlack(w.left) && isBlack(w.right)) {
                    w.color = ColorEnum.RED;
                    x = (RedBlackNode)x.parent;
                } else if (w != nilNode) {
                    if (isBlack(w.left)) { // case 3 sibling is black and its right child is red and left child is black
                        ((RedBlackNode)w.right).color = ColorEnum.BLACK;
                        w.color = ColorEnum.RED;
                        rotateLeft(w);
                        w = (RedBlackNode)x.parent.left;
                    }
                    w.color = ((RedBlackNode)x.parent).color; // case 4 sibling is black and left child is red
                    ((RedBlackNode)x.parent).color = ColorEnum.BLACK;
                    ((RedBlackNode)w.left).color = ColorEnum.BLACK;
                    rotateRight(x.parent);
                    x = (RedBlackNode)root;
                } else {
                    x.color = ColorEnum.BLACK;
                    x = (RedBlackNode)x.parent;
                }
            }
            
        }
    }
    
    private boolean isBlack(Node node) {
        return node != null ? ((RedBlackNode)node).color == ColorEnum.BLACK : false;
    }
    
    private boolean isRed(Node node) {
        return node != null ? ((RedBlackNode)node).color == ColorEnum.RED : false;
    }

    /**
     * Restores Red-Black tree properties after insert if needed. Insert can
     * break only 2 properties: root is red or if node is red then children must
     * be black.
     */
    private void insertRBFixup(RedBlackNode currentNode) {
        // current node is always RED, so if its parent is red it breaks
        // Red-Black property, otherwise no fixup needed and loop can terminate
        while (currentNode.parent != root && ((RedBlackNode) currentNode.parent).color == ColorEnum.RED) {
            RedBlackNode parent = (RedBlackNode) currentNode.parent;
            RedBlackNode grandParent = (RedBlackNode) parent.parent;
            if (parent == grandParent.left) {
                RedBlackNode uncle = (RedBlackNode) grandParent.right;
                // case1 - uncle and parent are both red
                // re color both of them to black
                if (((RedBlackNode) uncle).color == ColorEnum.RED) {
                    parent.color = ColorEnum.BLACK;
                    uncle.color = ColorEnum.BLACK;
                    grandParent.color = ColorEnum.RED;
                    // grandparent was recolored to red, so in next iteration we
                    // check if it does not break Red-Black property
                    currentNode = grandParent;
                } 
                // case 2/3 uncle is black - then we perform rotations
                else {
                    if (currentNode == parent.right) { // case 2, first rotate left
                        currentNode = parent;
                        rotateLeft(currentNode);
                    }
                    // do not use parent
                    parent.color = ColorEnum.BLACK; // case 3
                    grandParent.color = ColorEnum.RED;
                    rotateRight(grandParent);
                }
            } else if (parent == grandParent.right) {
                RedBlackNode uncle = (RedBlackNode) grandParent.left;
                // case1 - uncle and parent are both red
                // re color both of them to black
                if (((RedBlackNode) uncle).color == ColorEnum.RED) {
                    parent.color = ColorEnum.BLACK;
                    uncle.color = ColorEnum.BLACK;
                    grandParent.color = ColorEnum.RED;
                    // grandparent was recolored to red, so in next iteration we
                    // check if it does not break Red-Black property
                    currentNode = grandParent;
                }
                // case 2/3 uncle is black - then we perform rotations
                else {
                    if (currentNode == parent.left) { // case 2, first rotate right
                        currentNode = parent;
                        rotateRight(currentNode);
                    }
                    // do not use parent
                    parent.color = ColorEnum.BLACK; // case 3
                    grandParent.color = ColorEnum.RED;
                    rotateLeft(grandParent);
                }
            }

        }
        // ensure root is black in case it was colored red in fixup
        ((RedBlackNode) root).color = ColorEnum.BLACK;
    }

    protected static class RedBlackNode extends Node {
        public ColorEnum color;

        public RedBlackNode(Integer value, Node parent, Node left, Node right, ColorEnum color) {
            super(value, parent, left, right);
            this.color = color;
        }
    }

}

跳表 Skip List

• 跳表：能实现搜索二叉树的功能，但不是树结构，使用的是多级索引的链表，查找效率O(logn)，也是Redis中的一个核心组件。
  • 每新添加一个节点，用概念（P=0.5）决定节点层数（eg. 正正反-第2层，反-第0层）
  • 用一个head列表管理层数，右边就是多个链表指针，按照节点数值大小排序。
  • 查询：从head列最高层表开始，往右边对比走，直至比右边的小就开始往下走，直至找到 / 或者到最底层还没查找到。
  • 插入：先判断是否有；为其掷层数，再从所掷层开始逐层设置左右邻指针
  • 删除：也是同样先判断，然后从所掷层开始逐层断开左右邻指针，并将两边连接。
  • 算法实现（java）

	public static class SkipListNode {	// 跳表headList
		public Integer value;
		public ArrayList nextNodes;

		public SkipListNode(Integer value) {
			this.value = value;
			nextNodes = new ArrayList();
		}
	}

	public static class SkipListIterator implements Iterator {
		SkipList list;
		SkipListNode current;

		public SkipListIterator(SkipList list) {
			this.list = list;
			this.current = list.getHead();
		}

		public boolean hasNext() {
			return current.nextNodes.get(0) != null;
		}

		public Integer next() {
			current = current.nextNodes.get(0);
			return current.value;
		}
	}

	public static class SkipList {
		private SkipListNode head;
		private int maxLevel;
		private int size;
		private static final double PROBABILITY = 0.5;	//概率器

		public SkipList() {
			size = 0;
			maxLevel = 0;
			head = new SkipListNode(null);
			head.nextNodes.add(null);
		}

		public SkipListNode getHead() {
			return head;
		}

		public void add(Integer newValue) {
			if (!contains(newValue)) {	
				size++;
				int level = 0;
				while (Math.random()  maxLevel) {
					head.nextNodes.add(null);
					maxLevel++;
				}
				SkipListNode newNode = new SkipListNode(newValue);
				SkipListNode current = head;
				do {	// 从最上层开始设置左右邻指针
					current = findNext(newValue, current, level);
					newNode.nextNodes.add(0, current.nextNodes.get(level)); // 先加上层数
					current.nextNodes.set(level, newNode); //再设置邻指向
				} while (level-- > 0);
			}
		}

		public void delete(Integer deleteValue) {
			if (contains(deleteValue)) {
				SkipListNode deleteNode = find(deleteValue);
				size--;
				int level = maxLevel;
				SkipListNode current = head;
				do {
					current = findNext(deleteNode.value, current, level);
					if (deleteNode.nextNodes.size() > level) {
						current.nextNodes.set(level, deleteNode.nextNodes.get(level));
					}
				} while (level-- > 0);
			}
		}

		// Returns the skiplist node with greatest value  0);
			return current;
		}

		// Returns the node at a given level with highest value less than e
		private SkipListNode findNext(Integer e, SkipListNode current, int level) {
			SkipListNode next = current.nextNodes.get(level);
			while (next != null) {
				Integer value = next.value;
				if (lessThan(e, value)) { // e  iterator() {
			return new SkipListIterator(this);
		}

		/******************************************************************************
		 * Utility Functions *
		 ******************************************************************************/

		private boolean lessThan(Integer a, Integer b) {
			return a.compareTo(b) 

算法 - 第八章 Morris遍历/搜索二叉树/跳表等（完结）

标签：二次   ringbuf   main   查询   while   func   abi   移动   ack   

原文地址：https://www.cnblogs.com/ymjun/p/12746263.html