数据结构与算法转载

原文地址

1 有序表原理及扩展

1.1 搜索二叉树

经典的搜索二叉树，是没有重复值的，任何节点为头的数，左孩子都比自己小，右孩子都比自己大

允许重复值的改进的搜索二叉树，可以在每个节点上增加一个统计词频的数据项。表示出现了几次；但是不可相等的放到左右孩子上，搜索二叉树变平衡时，会影响后续的旋转

1、搜索二叉树一定要说明以什么标准来排序

2、经典的搜索二叉树，树上没有重复的用来排序的key值

3、如果有重复节点的需求，可以在一个节点内部增加数据项

1.2 搜索二叉树的增删改查

1.2.1 搜索二叉树的查找和添加

• 查找

搜索二叉树查询key（查询某个key存在还是不存在），当前节点比自己小，到右子树上去找，当前节点比自己大，到其左孩子上去找，越界，说明不存在

1、如果当前节点的value==key，返回true

2、如果当前节点的value<key，当前节点向左移动

3、如果当前节点的value>key，当前节点向右移动

4、如果当前节点变成null，返回false

• 添加

和查询过程一样，但当前节点滑到空的时候，就插入在这里

• 删除

1、先找到key所在的节点

2、如果该节点没有左孩子、没有右孩子，直接删除即可（好理解）

3、如果该节点有左孩子、没有右孩子，直接用左孩子顶替该节点（好理解）

4、如果该节点没有左孩子、有右孩子，直接用右孩子顶替该节点（好理解）

5、如果该节点有左孩子、有右孩子，用该节点后继节点顶替该节点（需要旋转调整，没法有左右孩子去替换，原因是左右孩子也有左右孩子）

==一个节点的后继节点，就是该节点右孩子的最左的那个节点。==

graph TD
2-->1
2-->5
5-->3
5-->10
10-->8
10-->13
8-->6
6-->7

比如我要删除5节点，那么5节点的后继节点就是其右子树的最左的孩子，也就是6。把6替换掉5，6的右孩子给它父亲作为左孩子，得到

graph TD
2-->1
2-->6
6-->3
6-->10
10-->8
10-->13
8-->7

package class05;

/**
 * Not implemented by zuochengyun
 * 
 * Abstract binary search tree implementation. Its basically fully implemented
 * binary search tree, just template method is provided for creating Node (other
 * trees can have slightly different nodes with more info). This way some code
 * from standart binary search tree can be reused for other kinds of binary
 * trees.
 * 
 * @author Ignas Lelys
 * @created Jun 29, 2011
 * 
 */
public class AbstractBinarySearchTree {

	/** Root node where whole tree starts. */
	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) {
		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;
	}

	/**
	 * Insert new element to tree.
	 * 插入一个节点
	 * 
	 * @param element
	 *            Element to insert.
	 */
	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;
	}

	/**
	 * 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) {
				        // 左孩子为空，右孩子直接替换该节点，达到删除的效果
					// 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;
	}

	/**
	 * 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;
	}

	/**
	 * Get next element element who is bigger than provided element.
	 * 
	 * @param element
	 *            Element for whom descendand element is searched
	 * @return Successor value.
	 */
	// TODO Predecessor
	public int getSuccessor(int element) {
		return getSuccessor(search(element)).value;
	}

	/**
	 * @return Number of elements in the tree.
	 */
	public int getSize() {
		return size;
	}

	/**
	 * Tree traversal with printing element values. In order method.
	 */
	public void printTreeInOrder() {
		printTreeInOrder(root);
	}

	/**
	 * Tree traversal with printing element values. Pre order method.
	 */
	public void printTreePreOrder() {
		printTreePreOrder(root);
	}

	/**
	 * Tree traversal with printing element values. Post order method.
	 */
	public void printTreePostOrder() {
		printTreePostOrder(root);
	}

	/*-------------------PRIVATE HELPER METHODS-------------------*/

	private void printTreeInOrder(Node entry) {
		if (entry != null) {
			printTreeInOrder(entry.left);
			if (entry.value != null) {
				System.out.println(entry.value);
			}
			printTreeInOrder(entry.right);
		}
	}

	private void printTreePreOrder(Node entry) {
		if (entry != null) {
			if (entry.value != null) {
				System.out.println(entry.value);
			}
			printTreeInOrder(entry.left);
			printTreeInOrder(entry.right);
		}
	}

	private void printTreePostOrder(Node entry) {
		if (entry != null) {
			printTreeInOrder(entry.left);
			printTreeInOrder(entry.right);
			if (entry.value != null) {
				System.out.println(entry.value);
			}
		}
	}

	protected Node getMinimum(Node node) {
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

	protected Node getMaximum(Node node) {
		while (node.right != null) {
			node = node.right;
		}
		return node;
	}

	protected Node getSuccessor(Node node) {
		// if there is right branch, then successor is leftmost node of that
		// subtree
		if (node.right != null) {
			return getMinimum(node.right);
		} else { // otherwise it is a lowest ancestor whose left child is also
			// ancestor of node
			Node currentNode = node;
			Node parentNode = node.parent;
			while (parentNode != null && currentNode == parentNode.right) {
				// go up until we find parent that currentNode is not in right
				// subtree.
				currentNode = parentNode;
				parentNode = parentNode.parent;
			}
			return parentNode;
		}
	}

	// -------------------------------- TREE PRINTING
	// ------------------------------------

	public void printTree() {
		printSubtree(root);
	}

	public void printSubtree(Node node) {
		if (node.right != null) {
			printTree(node.right, true, "");
		}
		printNodeValue(node);
		if (node.left != null) {
			printTree(node.left, false, "");
		}
	}

	private void printNodeValue(Node node) {
		if (node.value == null) {
			System.out.print("<null>");
		} else {
			System.out.print(node.value.toString());
		}
		System.out.println();
	}

	private void printTree(Node node, boolean isRight, String indent) {
		if (node.right != null) {
			printTree(node.right, true, indent + (isRight ? "        " : " |      "));
		}
		System.out.print(indent);
		if (isRight) {
			System.out.print(" /");
		} else {
			System.out.print(" \\");
		}
		System.out.print("----- ");
		printNodeValue(node);
		if (node.left != null) {
			printTree(node.left, false, indent + (isRight ? " |      " : "        "));
		}
	}

	public static class Node {
		public Node(Integer value, Node parent, Node left, Node right) {
			super();
			this.value = value;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}

		public Integer value;
		public Node parent;
		public Node left;
		public Node right;

		public boolean isLeaf() {
			return left == null && right == null;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((value == null) ? 0 : value.hashCode());
			return result;
		}

		@Override
		public 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;
		}

	}
}

1.3 传统搜索二叉树存在的问题

1）基础的搜索二叉树，添加、删除时候不照顾平衡性

2）数据状况很差时，性能就很差

==给搜索二叉树引入两个动作：左旋、右旋==

输入状况，决定性能。比如输入状况构建出来的树，严重不平衡。极端情况是只有一条通往底部的路径，高度为n;

平衡二叉树的定义，任何子树，左子树的高度和右子树的高度差，不大于1。所以对于n个节点，平衡二叉树的高度，就是logN

1.3.1 平衡搜索二叉树

平衡搜索二叉树，就是在插入和删除的过程中，动态的保持平衡性。保持平衡的代价保持在logN。平衡搜索二叉树的实现由很多，红黑树只是其中一种

1.3.2 左旋和右旋

左旋和右旋针对头结点而言的，即对哪个头结点进行左旋还是右旋；顾名思义如果对头结点为a的子树右旋，那么a倒到右边，a的左孩子顶上来，到a原来的位置上去。a原来左孩子的右孩子，现在当做a的左孩子，如下图

graph TD
a-->b
a-->c
c-->d
c-->e
b-->f
b-->g

a右旋，得到：

graph TD
b-->f
b-->a
a-->g
a-->c
c-->d
c-->e

同理，a左旋，得到：

graph TD
c-->a
c-->e
a-->b
a-->d
b-->f
b-->g

带左旋和右旋的搜索二叉树，在经典搜索二叉树上做的扩展，继承经典搜索二叉树。

package class05;

/**
 * Not implemented by zuochengyun
 * 
 * Abstract class for self balancing binary search trees. Contains some methods
 * that is used for self balancing trees.
 * 
 * @author Ignas Lelys
 * @created Jul 24, 2011
 * 
 */
public abstract class AbstractSelfBalancingBinarySearchTree 
extends AbstractBinarySearchTree {

    /**
     * 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;
    }

}

1.4 有序表

在Java中，就是TreeMap，有序表和Hash表（HashMap）的操作类似，但是有序表中自动把我们的key排好了顺序，我们也可以传入比较器，自定义对比和排序的规则；我们可以通过TreeMap直接得到最大节点和最小节点，也可以获取大于某个值的第一个Key是什么等等

为什么TreeMap可以做到有序，原因是TreeMap的底层是一个平衡搜索二叉树

• Hash表和有序表对比

1、HashMap的所有操作是O(1)的，TreeMap的所有操作是O(logN)

2、使用有序表的Key必须是可以比较的，没法自然比较的需要传入自定义比较器

1.5 有序表的实现（AVL树，SB树，红黑树）

在有序表中，有序表是一种规范，类似于接口名。规范为key要按序组织，所有操作要是O(logN)等。各种树结构可以实现有序表的功能。其中红黑树只是有序表的一个实现

==AVL树，SB树，红黑树，都是有序表的一种实现。都是平衡搜索二叉树，这三种树在功能和时间复杂度上几乎无差别，在实现细节上也就是在常数时间上，会有差别。三种树调整检查哪些节点的平衡性相同，下文进行说明。每种树针对每个节点的平衡性调整不同，但是都是使用左旋和右旋两个动作==

• AVL树，SB树，红黑树的共性

1）都是搜索二叉树

2）插入、删除、查询（一切查询）搜索二叉树怎么做，这些结构都这么做

3）使用调整的基本动作都只有左旋、右旋

4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查

5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)

• AVL树，SB树，红黑树不同之处

1）平衡性的约束不同

AVL树最严格、SB树稍宽松、红黑树最宽松

2）插入、删除和搜索二叉树一样，但是额外，做各自的平衡性调整。各自的平衡性调整所使用的动作都是左旋或者右旋

1.5.1 AVL树

是这三个平衡搜索二叉树中，平衡性最严格的，左树高度和右树高度的绝对值，严格小于2

AVL树在插入节点的时候，只会向上检查节点的平衡性有没有被破坏。删除节点也一样，只会检查删除的那个节点向上的那条链上的节点有没被破坏。删除的时候，如果被删除的节点没有左右孩子那么直接检查，如果有右孩子，是去检查后继节点原来所在的位置的向上节点的平衡性

==实质上三种树删除和插入节点，检查哪些节点需要调整平衡都是这样的查找规则，对于删除来说，只有左树和只有右树没影响，如果左右树都存在，是去检查后继节点原来所在的位置向上的平衡性。只是具体到某个节点平衡性的处理上，三种树不一样==

1.5.1.1 AVL树针对某个节点的平衡性处理

1、该节点左树高度和右树高度差的绝对值|L-R|，小于2。不违规，无须调整

2、|L-R|大于1，说明要不然左树高度大了，要不然右树高度大了。而且之前的每一步都进行了调整，所以高度差不会超过2。高度不平衡对应四种情况，被称为RR形违规，RL形违规，LL形违规，LR形违规。首字母表示左树变高了还是右树变高了，比如RR和RL都表示经过插入或者删除，右树的高度变大了

RR表示，右子节点的右树过长，RL表示右子节点的左树过长。同理LL表示左子节点的左子树高度过长导致，LR表示左子节点的右树高度过长导致的不平衡

• LL形违规，对该节点进行一次右旋即可

graph TD
x-->y
x-->p
y-->z
y-->t
z-->k

右旋后得到：

graph TD
y-->z
y-->x
z-->k
x-->t
x-->p

• 同理RR形违规，对该节点进行一次左旋即可

• LR形,让底部的孙子节点，来到顶部来。

下面例子，想办法让x的孙子节点t节点来到顶部，先对y节点进行一次左旋,再对x节点做一次右旋

graph TD
x-->y
x-->p
y-->z
y-->t
t-->k

先对y节点进行一次左旋

graph TD
x-->t
x-->p
y-->z
t-->y
t-->k

再对x节点做一次右旋

graph TD
t-->y
t-->x
x-->k
x-->p
y-->z

原x的孙子节点t此时，调整到的顶部

• 同理RL形,也是让超过长度的那一侧底部的孙子节点，来到顶部来。

==LL形和RR形旋转一次O(1)，LR和RL形旋转两次，也是O(1)。那么即使删除或者添加的节点影响的整个向上的链路，整体复杂度也是O(logN)==

AVL树继承自带左右旋的平衡搜索二叉树，在此基础上做的扩展，code如下：

package class05;

/**
 * Not implemented by zuochengyun
 * 
 * AVL tree implementation.
 * 
 * In computer science, an AVL tree is a self-balancing binary search tree, and
 * it was the first such data structure to be invented.[1] In an AVL tree, the
 * heights of the two child subtrees of any node differ by at most one. Lookup,
 * insertion, and deletion all take O(log n) time in both the average and worst
 * cases, where n is the number of nodes in the tree prior to the operation.
 * Insertions and deletions may require the tree to be rebalanced by one or more
 * tree rotations.
 * 
 * @author Ignas Lelys
 * @created Jun 28, 2011
 * 
 */
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);
		// 对有影响的节点，顺着parent指针向上做平衡性检查调整
		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);
			// 接管的节点不为空，检查是哪一种替换的方式，左孩子接管or右孩子接管，or后继节点接管，or既没有左孩子有没有右孩子直接删除
			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) {
			        // 判断是RR形还是RL形，确定进行一次还是两次旋转
				if (node.right.right != null) {
				        // 旋转，旋转的过程中，一定维护好高度信息
					node = (AVLNode) avlRotateLeft(node);
					break;
				} else {
					node = (AVLNode) doubleRotateRightLeft(node);
					break;
				}
			// 左树过高
			} else if (nodeBalance == -2) {
			        // 同理，判断是LL还是LR
				if (node.left.left != null) {
					node = (AVLNode) avlRotateRight(node);
					break;
				} else {
					node = (AVLNode) doubleRotateLeftRight(node);
					break;
				}
			} else {
				updateHeight(node);
			}

                        // 把当前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
	 * AVLNode继承自搜索二叉树的node，额外补充一个高度信息，用这个高度信息做平衡，一个节点的高度，是以该节点做头节点的树的高度
	 */
	protected static class AVLNode extends Node {
		public int height;

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

}

1.5.2 SB树

对于平衡性而言，任何叔叔节点的子节点格式，不少于该节点的任何一个侄子节点子节点的个数

graph TD
c-->a
c-->e
a-->b
a-->d
e-->f
e-->g

即a是一个叔叔节点，一定不少于f和g的子节点个数

对于这种约束，也可保证任何节点的左右节点的个数不会有很大悬殊，即使高度不满足严格相减的绝对值小于2，也无伤大雅。整体仍然是O(logN)

1.5.2.1 SB树针对某个节点的平衡性处理

2007年，读高中的时候，承志峰研究出来的；常被用作比赛时，AVL树反而在ACM比赛中使用的相对少点

也分为LL,LR，RR，RL四种类型。

当删除和插入某个节点，影响的节点的左孩子，不如其右孩子的左孩子节点个数多，RL形

当删除和插入某个节点，影响的节点的左孩子，不如其右孩子的右孩子节点个数多，RR形

当删除和插入某个节点，影响的节点的右孩子，不如其左孩子的左孩子节点个数多，LL形

当删除和插入某个节点，影响的节点的右孩子，不如其左孩子的右孩子节点个数多，LR形

1、 对于LL形违规，对头结点x进行一次右旋，结束后，递归调用所以节点孩子个数发生变化的节点。右旋的时候，头结点x,和原x左孩子现在变成了头节点的b。这两个节点孩子个数发生了变化，要递归调用这两个节点。原因是原来不违规的节点，调整了位置后，pk的对象变了，要基于现在的结构再检查平衡性。这里虽然套了两个递归，整体仍然是O(1)，证明略

2、 RR形违规，和LL形违规类似处理；

==SB树平衡性相对于AVL树要模糊，所以平衡性调整比AVL的调整粒度要粗，也意味着SB树比AVL树速度要快，比赛常用。而且SB树可以设计成删除节点的时候，不进行平衡性调整，只有在添加节点的时候再进行平衡性调整，添加节点的时候有可能积压了很多的不平衡，但是我们有递归行为，仍然可以调整回平衡的状态；可能为棒状，有可能该次递归行为时间复杂度比较高，但是均摊下来仍然O(logN)水平；该结构比较重要==

==如果是违规的加点的左树高度超了，且左孩子的左右子节点个数相同，必须做LL形的调整，反之RR形同理==

• SB树的树结构版本

package class06;

public class Code01_SizeBalancedTreeMap {

        // k继承Comparable，可比较的泛型
	public static class SBTNode<K extends Comparable<K>, V> {
	        // 该节点的Key
		public K key;
		// 该节点的V
		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;

                // 右旋交换节点时，size要互换，维护正确的size信息。返回右旋之后的新头部
		private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
		        // 由于右旋，要维护好左子树
			SBTNode<K, V> leftNode = cur.l;
			// 左孩子的右，给当前节点的左
			cur.l = leftNode.r;
			// 左孩子的右指向当前节点，画图可以清晰看到就是右旋操作
			leftNode.r = cur;
			// 维护size
			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;
			}
			// LL形
			if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
			        // 当前节点右旋
				cur = rightRotate(cur);
				// 递归调整右孩子
				cur.r = maintain(cur.r);
				// 递归调用调整当前节点
				cur = maintain(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 = maintain(cur.l);
				cur.r = maintain(cur.r);
				cur = maintain(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 = maintain(cur.l);
				cur = maintain(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 = 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;
				}
			}
			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;
		}

                // put方法，有可能是新增有可能是覆盖更新
		public void put(K key, V value) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			// 先查找该key是不是已经存在
			SBTNode<K, V> lastNode = findLastIndex(key);
			if (lastNode != null && key.compareTo(lastNode.key) == 0) {
				lastNode.value = value;
			} else {
			        // 不存在的话，从根节点调用递归，加入到合适的位置。sb树由于没有向上指针，这里需要从头结点开始调用递归
			        // 添加进去后，有可能需要调整，头部有可能会变，返回新的头部
				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);

	}

}

• SB树的数组版本

package class06;

import java.util.ArrayList;

public class Code02_SizeBalancedTreeMap {

	public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
		private int root;
		private int len;
		private int[] left;
		private int[] right;
		private int[] size;
		private ArrayList<K> keys;
		private ArrayList<V> values;

		public SizeBalancedTreeMap(int init) {
			left = new int[init + 1];
			right = new int[init + 1];
			size = new int[init + 1];
			keys = new ArrayList<K>();
			values = new ArrayList<V>();
			keys.add(null);
			values.add(null);
			root = 0;
			len = 0;
		}

		private int rightRotate(int index) {
			int iLeft = left[index];
			left[index] = right[iLeft];
			right[iLeft] = index;
			size[iLeft] = size[index];
			size[index] = size[left[index]] + size[right[index]] + 1;
			return iLeft;
		}

		private int leftRotate(int index) {
			int iRight = right[index];
			right[index] = left[iRight];
			left[iRight] = index;
			size[iRight] = size[index];
			size[index] = size[left[index]] + size[right[index]] + 1;
			return iRight;
		}

		private int matain(int index) {
			if (size[left[left[index]]] > size[right[index]]) {
				index = rightRotate(index);
				right[index] = matain(right[index]);
				index = matain(index);
			} else if (size[right[left[index]]] > size[right[index]]) {
				left[index] = leftRotate(left[index]);
				index = rightRotate(index);
				left[index] = matain(left[index]);
				right[index] = matain(right[index]);
				index = matain(index);
			} else if (size[right[right[index]]] > size[left[index]]) {
				index = leftRotate(index);
				left[index] = matain(left[index]);
				index = matain(index);
			} else if (size[left[right[index]]] > size[left[index]]) {
				right[index] = rightRotate(right[index]);
				index = leftRotate(index);
				left[index] = matain(left[index]);
				right[index] = matain(right[index]);
				index = matain(index);
			}
			return index;
		}

		private int findLastIndex(K key) {
			int pre = root;
			int cur = root;
			while (cur != 0) {
				pre = cur;
				if (key.compareTo(keys.get(cur)) == 0) {
					break;
				} else if (key.compareTo(keys.get(cur)) < 0) {
					cur = left[cur];
				} else {
					cur = right[cur];
				}
			}
			return pre;
		}

		private int findLastNoSmallIndex(K key) {
			int ans = 0;
			int cur = root;
			while (cur != 0) {
				if (key.compareTo(keys.get(cur)) == 0) {
					ans = cur;
					break;
				} else if (key.compareTo(keys.get(cur)) < 0) {
					ans = cur;
					cur = left[cur];
				} else {
					cur = right[cur];
				}
			}
			return ans;
		}

		private int findLastNoBigIndex(K key) {
			int ans = 0;
			int cur = root;
			while (cur != 0) {
				if (key.compareTo(keys.get(cur)) == 0) {
					ans = cur;
					break;
				} else if (key.compareTo(keys.get(cur)) < 0) {
					cur = left[cur];
				} else {
					ans = cur;
					cur = right[cur];
				}
			}
			return ans;
		}

		private int add(int index, K key, V value) {
			if (index == 0) {
				index = ++len;
				keys.add(key);
				values.add(value);
				size[index] = 1;
				left[index] = 0;
				right[index] = 0;
				return index;
			} else {
				size[index]++;
				if (key.compareTo(keys.get(index)) < 0) {
					left[index] = add(left[index], key, value);
				} else {
					right[index] = add(right[index], key, value);
				}
				return matain(index);
			}
		}

		private int getIndex(int index, int kth) {
			if (kth == size[left[index]] + 1) {
				return index;
			} else if (kth <= size[left[index]]) {
				return getIndex(left[index], kth);
			} else {
				return getIndex(right[index], kth - size[left[index]] - 1);
			}
		}

		public int size() {
			return len;
		}

		public boolean containsKey(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			int lastIndex = findLastIndex(key);
			return lastIndex != 0 && key.compareTo(keys.get(lastIndex)) == 0 ? true : false;
		}

		public void put(K key, V value) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			if (len == size.length - 1) {
				throw new RuntimeException("size balanced tree is full.");
			}
			int lastIndex = findLastIndex(key);
			if (lastIndex != 0 && key.compareTo(keys.get(lastIndex)) == 0) {
				values.set(lastIndex, value);
			} else {
				root = add(root, key, value);
			}
		}

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

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

		public V get(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			int lastIndex = findLastIndex(key);
			if (lastIndex != 0 && key.compareTo(keys.get(lastIndex)) == 0) {
				return values.get(lastIndex);
			} else {
				return null;
			}
		}

		public K firstKey() {
			int cur = root;
			while (left[cur] != 0) {
				cur = left[cur];
			}
			return cur == 0 ? null : keys.get(cur);
		}

		public K lastKey() {
			int cur = root;
			while (right[cur] != 0) {
				cur = right[cur];
			}
			return cur == 0 ? null : keys.get(cur);
		}

		public K floorKey(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			int lastNoBigIndex = findLastNoBigIndex(key);
			return lastNoBigIndex == 0 ? null : keys.get(lastNoBigIndex);
		}

		public K ceilingKey(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			int lastNoSmallIndex = findLastNoSmallIndex(key);
			return lastNoSmallIndex == 0 ? null : keys.get(lastNoSmallIndex);
		}
	}

	public static void main(String[] args) {
		SizeBalancedTreeMap<String, Integer> sbt = new SizeBalancedTreeMap<String, Integer>(10000);

		sbt.put("pos", 512);
		sbt.put("zyp", 7123);
		sbt.put("unz", 542);
		sbt.put("abc", 5113);
		sbt.put("yzk", 665);
		sbt.put("fgi", 38776);
		sbt.put("bke", 2500540);
		sbt.put("lmn", 44334);
		sbt.put("abc", 11);
		sbt.put("abc", 111);

		for (int i = 0; i < sbt.size(); i++) {
			System.out.println(sbt.getIndexKey(i) + " , " + sbt.getIndexValue(i));
		}
		System.out.println(sbt.get("abc"));
		System.out.println(sbt.firstKey());
		System.out.println(sbt.lastKey());
		System.out.println(sbt.floorKey("bke"));
		System.out.println(sbt.ceilingKey("bke"));
		System.out.println(sbt.floorKey("ooo"));
		System.out.println(sbt.ceilingKey("ooo"));
		System.out.println(sbt.floorKey("aaa"));
		System.out.println(sbt.ceilingKey("aaa"));
		System.out.println(sbt.floorKey("zzz"));
		System.out.println(sbt.ceilingKey("zzz"));

	}

}

1.5.3 红黑树

1、 节点有红有黑

2、头节点和叶子节点是黑

3、红节点的子，一定要是黑节点

4、从任何节点到他的子节点，所有的路径中黑节点都是一样多的

从第三点和第四点可以推出，任何长链（黑红交替）和任何段链（都为黑）保证黑一样多，那么长链的长度一定不会比短链长度的二倍还要大。实质上上面条件的目的也是保证最长的链不要比最短的链2倍还多，一定程度上保证了平衡性

1.5.3.1 红黑树针对某个节点的平衡性处理

红黑树本质上也是搜索二叉树，搜索二叉树怎么增加和删除节点，红黑树相同；同样的加完节点，删除完节点，之后从受影响的节点往上都进行平衡性检查，几种有序表的实现只有检查平衡性的评估指标不同

红黑树平衡性检查，插入的情况下，违规的情况有5种，删除的情况下违规的情况有8种。红黑树自身的这些规定，会引出来13种违规情况下的节点调整。发明红黑树的人把13种情况都研究明白了，现在让我们学，哈哈

==面试场上看到问红黑树相关的内容，可以回答本质上也是搜索二叉树，不平衡性较多有13种，AVL和SB树都只有四种LL,LR，RR，RL。比红黑树简单。如果面试官一定要问哪5种，哪8种，那么这个面试官有问题，这种不平衡性可以查文档来获取。这种就属于面试官就是不想让你过，纠结哪8种，哪5种，纯粹是磨工夫==

红黑树这么麻烦，好处在哪，为什么这么著名，原因在于红黑树的扰动小。AVL由于平衡性特别清晰，增加和删除节点特别灵敏，扰动大。SB和红黑树的平衡性相对模糊，而且SB在删除的节点的时候，可以不进行平衡性调整，扰动小

有些场景，就是需要扰动小的调整，比如硬盘io的时候，每个树的节点，就是一块硬盘区域。硬盘删除，更新，插入等，如果时间复杂度评估指标相等，还是要选择扰动小的结构。内存中无所谓，扰动大小都可

如果每次插入和删除，行为代价都非常的高，红黑树都不考虑用，而是选择用底层硬盘结构的树，不如B树，和B+树，234树。这些树是多叉树。B树和B+树牺牲了一定的查询效率，虽然也是O(logN)，常数项很大，但是没有AVL，SB,和红黑树的效率高。比如数据库组织的一些树，就是考虑到少读写硬盘，就是用的B+树

红黑树，在（AVL，SB） 和 硬盘的树（B，B+）树之间达到平衡。各有取舍

1.5.3.1.1 Redis为什么选择跳表的结构？

Redis为什么选择跳表的结构,而不是AVL和SB树呢，实质上可以选择，但是考虑到redis可能需要对有序表进行序列化的要求，SkipList就是多层的线性结构，比较好序列化。AVL和SB是个结构化的东西，不好序列化；一种技术的选型，需要根据自己的生存状态去选择的

==三种树的平衡性保证策略不同，各自实现各自的平衡性，但是三个树都只有左旋和右旋两种调整策略==

1.6 跳表SkipList（也可实现有序表功能）

==最烧脑的结构==

跳表也可实现有序表的功能，但是跳表不是搜索二叉树，实现机制跟二叉树也没关系

==跳表实现有序表，比较好实现，思想也相对更先进O(logN)==

跳表节点有多条往外指的指针，Node里面有一个List变量，类似于多叉树；跳表节点上也有可以比较的key，定义最小的key是null

每个节点有多少个向下指针，随机指定，高层一定和所有节点最多的向下指针的条目数保持一致

跳表的最低层一定含有所有记录节点，概率上第二层有N/2个节点，概率上第三层会有N/4个节点...

高层向底层寻找，实际上跳跃了很多的节点。这种机制跟输入的数据状况没关系，每一个节点随机层数，最后查找O(logN)

package class06;

import java.util.ArrayList;

public class Code03_SkipListMap {

	// 跳表的节点定义,key是可以比较的
	public static class SkipListNode<K extends Comparable<K>, V> {
		public K key;
		public V val;
		// 0  nextNodes.get(0)
		// 1  nextNodes.get(1)
		// i  nextNodes.get(i)
		// nextNodes.size()
		// 多条指向其他节点的指针
		public ArrayList<SkipListNode<K, V>> nextNodes;

		public SkipListNode(K k, V v) {
			key = k;
			val = v;
			// node  7层指针
			// nextNodes.add(null)
			// nextNodes.add(null)
			// nextNodes.add(null)
			// nextNodes.add(null)
			// nextNodes.add(null)
			// nextNodes.add(null)
			// nextNodes.add(null)
			nextNodes = new ArrayList<SkipListNode<K, V>>();
		}

		// 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束
		// 头(null), 头节点的null，认为最小
		// node  -> 头，node(null, "")  node.isKeyLess(!null)  true
		// node里面的key是否比otherKey小，true，不是false
		// 当前node里面的key是否比传进来的key要小。小返回true，不小返回false
		public boolean isKeyLess(K otherKey) {
			//  otherKey == null -> false 
			return otherKey != null && (key == null || key.compareTo(otherKey) < 0);
		}

                // 判断当前node的key可传入的key是否相等
		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);
			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) { // 从上层跳下层，直到跳到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);
		}

                // put进来一个节点
		public void put(K key, V value) {
			if (key == null) {
				return;
			}
			// 找到小于key的最右的节点。从上层往下层跳的方式找最底层对应的节点，最底层数据是全的，直接遍历最底层就编程O(N)复杂度了
			SkipListNode<K, V> less = mostRightLessNodeInTree(key);
			SkipListNode<K, V> find = less.nextNodes.get(0);
			// 找到的不是null，那么就是重复key，更新key对应的值
			if (find != null && find.isKeyEqual(key)) {
				find.val = value;
			} else { // 否则没找到，新增一个key，size++
				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) {
				        // 在level层找到最右的小于key的节点，赋值给pre
					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 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"));

	}

}

1.7 有序表例题实战

• 例题1

给定一些数组，长度不一。每个数组里面是有序的，可理解为二维数组，每一行有序，现在需要找一个a到b的区间，要求每一行都至少有一个数命中在该区间中。求满足这个这样条件的区间的最窄区间，如果存在多个最窄区间，返回区间位置起始最小的那个

解题流程：准备一个有序表，第一步，把每个数组中第0个树加入有序表，得到一个区间就是有序表中的最小值和最大值构成的区间，该区间已经可以包含每个数组中至少一个数在该区间内，但不一定是最小区间；第二步，找到有序表中最小的数在哪个数组中，弹出最小值，把该数组的下一个树加入有序表，看是否更新了最小区间，更小才更新，同样大不更新。重复。。。

最后全局最小区间，就是我们要找的区间；

解题思路：实质上解题流程，是在尝试每一个数字开头的情况下，哪个区间是最小的。以每一个数字去尝试，实质上是一种贪心思想，不去考虑数字不以数组中出现的区间，该区间一定不是最小的

整个流程，只需要运用有序表的基本功能，原始的有序表已经能够满足需求，无需改写有序表，用系统实现的即可；

1.7.1 哪些情况下需要改写系统的有序表？

• 例题-leetcode原题

给定一个数组arr，和两个整数a和b（a<=b） 求arr中有多少个子数组，累加和在[a,b]这个范围上 返回达标的子数组数量

例如a等于10，b等于30，在arr上，求0到i范围有多少子数组在10和30范围上，假设0带i和为100，反过来就是求0到i-1范围上有多少前缀和有多少落在70到90范围上；

所以，我们求0到p，p在0到i中间，前缀和在70到90上，我们可以得到p+1到i的累加和在10到30范围上。所以这题就是求0到p的前缀和有多少在我们根据a到b和0到i的累加和推出的新的范围上[sum-a, sum-b]，就等于我们要求的个数

我们把0到0的和，0到1的和，0到i的和。。。加入到我们的结构中去，求0到i结尾的子数组有多少个达标，就是求该结构上，有多少个前缀和落在了[sum-a, sum-b]的范围上；这个结构可以加入一个数字，且允许有重复值，给定一个范围[sum-a,sum-b]可以通过该结构返回加入的节点有多少个在这个范围上。例如加入到结构中的数字，有1，1，1，4，5，给定范围[1,5]，返回6

要实现这样的功能，系统实现的有序表，无法实现，一方面原始有序表无法加入重复数字，第二方面没有这样的方法返回个数。这样的方法，可以实现为，小于a的数有多少个，小于b的数有多少个，那么最终我们需要的个数就是a-b个

在SB树上改造：

package class07;

import java.util.HashSet;

public class Code01_CountofRangeSum {

	public static int countRangeSum1(int[] nums, int lower, int upper) {
		int n = nums.length;
		long[] sums = new long[n + 1];
		for (int i = 0; i < n; ++i)
			sums[i + 1] = sums[i] + nums[i];
		return countWhileMergeSort(sums, 0, n + 1, lower, upper);
	}

        // leetcode不太好理解的版本
	private static int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
		if (end - start <= 1)
			return 0;
		int mid = (start + end) / 2;
		int count = countWhileMergeSort(sums, start, mid, lower, upper)
				+ countWhileMergeSort(sums, mid, end, lower, upper);
		int j = mid, k = mid, t = mid;
		long[] cache = new long[end - start];
		for (int i = start, r = 0; i < mid; ++i, ++r) {
			while (k < end && sums[k] - sums[i] < lower)
				k++;
			while (j < end && sums[j] - sums[i] <= upper)
				j++;
			while (t < end && sums[t] < sums[i])
				cache[r++] = sums[t++];
			cache[r] = sums[i];
			count += j - k;
		}
		System.arraycopy(cache, 0, sums, start, t - start);
		return count;
	}

        // 节点改造为，有自己的key，有左右孩子，有size,有词频数量all。all要和size同样维护起来
	public static class SBTNode {
		public long key;
		public SBTNode l;
		public SBTNode r;
		public long size; // 不同key的size，sb树的平衡指标
		public long all; // 总的size

		public SBTNode(long k) {
			key = k;
			size = 1;
			all = 1;
		}
	}

	public static class SizeBalancedTreeSet {
		private SBTNode root;
		private HashSet<Long> set = new HashSet<>();

		private SBTNode rightRotate(SBTNode cur) {
			long same = cur.all - (cur.l != null ? cur.l.all : 0) - (cur.r != null ? cur.r.all : 0);
			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;
			// all modify
			leftNode.all = cur.all;
			cur.all = (cur.l != null ? cur.l.all : 0) + (cur.r != null ? cur.r.all : 0) + same;
			return leftNode;
		}

		private SBTNode leftRotate(SBTNode cur) {
			long same = cur.all - (cur.l != null ? cur.l.all : 0) - (cur.r != null ? cur.r.all : 0);
			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;
			// all modify
			rightNode.all = cur.all;
			cur.all = (cur.l != null ? cur.l.all : 0) + (cur.r != null ? cur.r.all : 0) + same;
			return rightNode;
		}

		private SBTNode matain(SBTNode 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;
		}

                // add方法时，all要跟着增加
		private SBTNode add(SBTNode cur, long key, boolean contains) {
			if (cur == null) {
				return new 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 matain(cur);
				}
			}
		}

		public void add(long sum) {
			boolean contains = set.contains(sum);
			root = add(root, sum, contains);
			set.add(sum);
		}

                // 本题在原始有序表上增加的方法，小于一个key的个数有多少个
		public long lessKeySize(long key) {
			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;
		}

		// > 7 8...
		// <8 ...<=7
		public long moreKeySize(long key) {
			return root != null ? (root.all - lessKeySize(key + 1)) : 0;
		}

	}

        // 好理解的版本，求[a,b]上满足数量的个数
	public static int countRangeSum2(int[] nums, int lower, int upper) {
		SizeBalancedTreeSet treeSet = new SizeBalancedTreeSet();
		long sum = 0;
		int ans = 0;
		// 一个数都没有的时候词频是0
		treeSet.add(0);
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
			// sum = x [a,b] start > x-a -start < -x+a x-start < a
			// [a,b]
			// < a > b
			// i + 1 <a - <b
			long lessLowers = treeSet.moreKeySize(sum - lower);
			// sum = x [a,b] start < x-b -start > -x+b x-start > b
			long moreUppers = treeSet.lessKeySize(sum - upper);
			ans += i + 1 - lessLowers - moreUppers;
			treeSet.add(sum);
		}
		return ans;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static int[] generateArray(int len, int varible) {
		int[] arr = new int[len];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (Math.random() * varible);
		}
		return arr;
	}

	public static void main(String[] args) {
		int len = 200;
		int varible = 50;
		for (int i = 0; i < 10000; i++) {
			int[] test = generateArray(len, varible);
			int lower = (int) (Math.random() * varible) - (int) (Math.random() * varible);
			int upper = lower + (int) (Math.random() * varible);
			int ans1 = countRangeSum1(test, lower, upper);
			int ans2 = countRangeSum2(test, lower, upper);
			if (ans1 != ans2) {
				printArray(test);
				System.out.println(lower);
				System.out.println(upper);
				System.out.println(ans1);
				System.out.println(ans2);
			}
		}

	}

}

有序表结构本身比较重要，我们也经常使用系统实现的有序表，但是涉及到手动改有序表的实现，本身就已经比较难，而且面试出现的概率不是很高

Java的TreeMap底层是红黑树，但是SB树完全可以替换，没任何差别

本站文章除注明转载/出处外，均为作者原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/11/02 00:43