23-《进阶》有序表介绍及其原理.md

[TOC]

# 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
```

```Go
package main

import "fmt"

type Node struct {
	Value  int
	Left   *Node // 左孩子指针
	Right  *Node // 右孩子指针
	Parent *Node // 指向父亲的指针
}

// BinarySearchTree 二叉搜索树
type BinarySearchTree struct {
	Root *Node
	Size int
}

// createNode 构建一个树节点
func createNode(value int, parent *Node, left *Node, right *Node) *Node {
	return &Node{
		Value:  value,
		Left:   left,
		Right:  right,
		Parent: parent,
	}
}

// Search 在二叉搜索树中寻找element是否存在，如果不存在返回nil
func (tree *BinarySearchTree) Search(element int) *Node {
	node := tree.Root
	for node != nil && node.Value != element {
		if element < node.Value { // 小于当前节点，找左孩子对比
			node = node.Left
		} else { // 大于当前节点，找右孩子对比
			node = node.Right
		}
	}
	return node
}

// Insert 向二叉搜索树中插入一个节点
func (tree *BinarySearchTree) Insert(element int) *Node {
	// 首先如果这个树是空的，把该节点当成头节点
	if tree.Root == nil {
		tree.Root = createNode(element, nil, nil, nil)
		tree.Size++
		return tree.Root
	}

	// 需要插入在该节点下面。经过上面的base case，这里tree.root一定不为nil
	searchTempNode := tree.Root
	insertParentNode := searchTempNode

	for searchTempNode != nil {
		insertParentNode = searchTempNode
		if element < searchTempNode.Value {
			searchTempNode = searchTempNode.Left
		} else {
			searchTempNode = searchTempNode.Right
		}
	}

	newNode := createNode(element, insertParentNode, nil, nil)
	if insertParentNode.Value > newNode.Value {
		insertParentNode.Left = newNode
	} else {
		insertParentNode.Right = newNode
	}
	tree.Size++
	return newNode
}

// delete 删除二叉搜索树中某个值的对应的节点。删除节点，每个节点由于加入向上的指针，那么旋转的时候会方便些
func (tree *BinarySearchTree) delete(element int) *Node {
	deleteNode := tree.Search(element)
	if deleteNode != nil {
		return tree.deleteByNode(deleteNode)
	} else {
		return nil
	}
}

// deleteNode 删除二叉搜索树中指定的某个节点。注意，删除方法返回的是删除后接管删除节点的位置的节点，返回
func (tree *BinarySearchTree) deleteByNode(deleteNode *Node) *Node {
	var nodeToReturn *Node

	if deleteNode != nil {
		if deleteNode.Left == nil {
			// 左孩子为空，右孩子直接替换该节点，达到删除的效果
			// transplant(a,b)  b去替换a的环境，a断连掉，把b返回
			nodeToReturn = tree.transplant(deleteNode, deleteNode.Right)
		} else if deleteNode.Right == nil {
			// 右孩子为空，左孩子直接替换，达到删除的目的
			nodeToReturn = tree.transplant(deleteNode, deleteNode.Left)
		} else {
			// 否则，要删除的节点既有左孩子，又有右孩子，找右子树的最左的孩子
			successorNode := tree.getMinimumNode(deleteNode.Right)
			// 要删除的节点的右孩子，有左孩子。最左孩子的右孩子要它父亲来接管
			if successorNode.Parent != deleteNode {
				tree.transplant(successorNode, successorNode.Right)
				successorNode.Right = deleteNode.Right
				successorNode.Right.Parent = successorNode
			}
			// 如果要删除的节点的右孩子，没有左孩子。直接用要删除的节点的右孩子进行替换即可
			tree.transplant(deleteNode, successorNode)
			successorNode.Left = deleteNode.Left
			successorNode.Left.Parent = successorNode
			nodeToReturn = successorNode
		}
		tree.Size--
	}
	return nodeToReturn
}

// transplant 将树上的一个节点（newNode）放到另一个节点（nodeToReplace）的位置。
func (tree *BinarySearchTree) transplant(nodeToReplace *Node, newNode *Node) *Node {
	if nodeToReplace.Parent == nil {
		tree.Root = newNode
	} else if nodeToReplace == nodeToReplace.Parent.Left { // nodeToReplace是其父亲的左孩子
		nodeToReplace.Parent.Left = newNode
	} else {
		nodeToReplace.Parent.Right = newNode
	}

	if newNode != nil {
		newNode.Parent = nodeToReplace.Parent
	}
	return newNode
}

// getMinimumValue 查找二叉搜索树中最小的值
func (tree *BinarySearchTree) getMinimumValue() int {
	return tree.getMinimumNode(tree.Root).Value
}

// getMinimumNode 查找二叉搜索树中最小值所在的节点
func (tree *BinarySearchTree) getMinimumNode(node *Node) *Node {
	for node.Left != nil {
		node = node.Left
	}
	return node
}

func (tree *BinarySearchTree) getMaximumValue() int {
	return tree.getMaximumNode(tree.Root).Value
}

func (tree *BinarySearchTree) getMaximumNode(node *Node) *Node {
	for node.Right != nil {
		node = node.Right
	}
	return node
}

// contains 判断二叉搜索树中存不存在element
func (tree *BinarySearchTree) contains(element int) bool {
	return tree.Search(element) != nil
}

// getSuccessor 获取下一个比提供的元素大的元素值。
func (tree *BinarySearchTree) getSuccessorValue(element int) int {
	return tree.getSuccessorNode(tree.Search(element)).Value
}
// getSuccessorNode 获取下一个比提供的元素大的元素节点。
func (tree *BinarySearchTree) getSuccessorNode(node *Node) *Node {
	// if there is right branch, then successor is leftmost node of that
	// subtree
	if node.Right != nil {
		return tree.getMinimumNode(node.Right)
	} else { // otherwise it is a lowest ancestor whose left child is also
		// ancestor of node
		curNode := node
		parentNode := node.Parent
		for parentNode != nil && curNode == parentNode.Right {
			// go up until we find parent that currentNode is not in right
			// subtree.
			curNode = parentNode
			parentNode = parentNode.Parent
		}
		return parentNode
	}
}

// printTreeInOrder 中序遍历
func (tree *BinarySearchTree) printTreeInOrder() {
	printInOrder(tree.Root)
}

// printTreePreOrder 先序遍历
func (tree *BinarySearchTree) printTreePreOrder() {
	printPreOrder(tree.Root)
}

// printTreePostOrder 后序遍历
func (tree *BinarySearchTree) printTreePostOrder() {
	printPostOrder(tree.Root)
}

func printInOrder(head *Node) {
	if head != nil {
		printInOrder(head.Left)
		fmt.Println(head.Value)
		printInOrder(head.Right)
	}
}

func printPreOrder(head *Node) {
	if head != nil {
		fmt.Println(head.Value)
		printInOrder(head.Left)
		printInOrder(head.Right)
	}
}

func printPostOrder(head *Node) {
	if head != nil {
		printInOrder(head.Left)
		printInOrder(head.Right)
		fmt.Println(head.Value)
	}
}
```


## 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

```


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

```Go
package main

// BalancingBinarySearchTree 平衡二叉搜索树，继承二叉搜索树
type BalancingBinarySearchTree struct {
	*BinarySearchTree
}

// rotateLeft 平衡二叉搜索树的左旋操作
func (tree *BalancingBinarySearchTree) rotateLeft(node *Node) *Node {
	temp := node.Right
	temp.Parent = node.Parent

	node.Right = temp.Left
	if node.Right != nil {
		node.Right.Parent = node
	}

	temp.Left = node
	node.Parent = temp

	if temp.Parent != nil {
		if node == temp.Parent.Left {
			temp.Parent.Left = temp
		} else {
			temp.Parent.Right = temp
		}
	} else {
		tree.Root = temp
	}
	return temp
}

// rotateRight 平衡二叉树的右旋操作
func (tree *BalancingBinarySearchTree) rotateRight(node *Node) *Node {
	temp := node.Left
	temp.Parent = node.Parent

	node.Left = temp.Right
	if node.Left != nil {
		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 != nil {
		if node == temp.Parent.Left {
			temp.Parent.Left = temp
		} else {
			temp.Parent.Right = temp
		}
	} else {
		tree.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树继承自带左右旋的平衡搜索二叉树，在此基础上做的扩展，重写继承的抽象类平衡二叉搜索树的相应方法实现即可。

Avl树的一种实现方式参考：https://github.com/emirpasic/gods/blob/master/trees/avltree/avltree.go


### 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树的树结构版本

```Go
package main

import "fmt"

// SBTNode SBT树的节点类型
type SBTNode struct {
	// 该节点的Key
	key string
	// 该节点的V
	value int
	// 节点的左孩子
	l *SBTNode
	// 节点的右孩子
	r *SBTNode
	// 不同的key的数量
	size int
}

type Comparator func(a, b interface{}) int

// StringComparator 字符串字典序比较器。参考标准库实现，返回0，1，-1。
func StringComparator(a, b interface{}) int {
	s1 := a.(string)
	s2 := b.(string)
	if s1 == s2 {
		return 0
	}
	if s1 < s2 {
		return -1
	}
	return +1
}

type SBTree struct {
	Root       *SBTNode
	Comparator Comparator
}

// InitSBTTree 构建一个SBT树，返回头节点
func InitSBTTree(key string, value int) *SBTree {
	root := &SBTNode{
		key:   key,
		value: value,
		size:  1,
	}

	sbTree := &SBTree{
		Root:       root,
		Comparator: StringComparator,
	}
	return sbTree
}

// rightRotate 右旋交换节点时，size要互换，维护正确的size信息。返回右旋之后的新头部
func (tree *SBTree) rightRotate(cur *SBTNode) *SBTNode {
	// 由于右旋，要维护好左子树
	leftNode := cur.l
	// 左孩子的右，给当前节点的左
	cur.l = leftNode.r
	// 左孩子的右，指向当前节点，画图可以清晰看到就是右旋操作
	leftNode.r = cur
	// 维护size
	leftNode.size = cur.size

	lSize := 0
	rSize := 0
	if cur.l != nil {
		lSize = cur.l.size
	} else {
		lSize = 0
	}

	if cur.r != nil {
		rSize = cur.r.size
	} else {
		rSize = 0
	}

	cur.size = lSize + rSize + 1
	return leftNode
}

// leftRotate 左旋操作和右旋操作同理
func (tree *SBTree) leftRotate(cur *SBTNode) *SBTNode {
	rightNode := cur.r
	cur.r = rightNode.l
	rightNode.l = cur
	rightNode.size = cur.size
	lSize := 0
	rSize := 0
	if cur.l != nil {
		lSize = cur.l.size
	} else {
		lSize = 0
	}

	if cur.r != nil {
		rSize = cur.r.size
	} else {
		rSize = 0
	}

	cur.size = lSize + rSize + 1
	return rightNode
}

// maintain 对传入的cur节点，做平衡性调整。包含四种不平衡的调整策略：LL, LR， RL, RR
func (tree *SBTree) maintain(cur *SBTNode) *SBTNode {
	if cur == nil {
		return nil
	}

	if cur.l != nil && cur.l.l != nil && cur.r != nil && cur.l.l.size > cur.r.size { // LL形不平衡调整策略
		// 当前节点右旋
		cur = tree.rightRotate(cur)
		// 递归调整个右孩子
		cur.r = tree.maintain(cur.r)
		// 递归调用调整当前节点
		cur = tree.maintain(cur)
	} else if cur.l != nil && cur.l.r != nil && cur.r != nil && cur.l.r.size > cur.r.size { // LR形不平衡调整策略
		// 当前节点左孩子左旋
		cur.l = tree.leftRotate(cur.l)
		// 当前节点右旋
		cur = tree.rightRotate(cur)
		// 递归调用调整节点左孩子
		cur.l = tree.maintain(cur.l)
		// 递归调用调整节点右孩子
		cur.r = tree.maintain(cur.r)
		// 递归调用调整当前节点
		cur = tree.maintain(cur)
	} else if cur.r != nil && cur.r.r != nil && cur.l != nil && cur.r.r.size > cur.l.size { // RR形不平衡调整策略
		// 当前节点左旋
		cur = tree.leftRotate(cur)
		// 递归调整当前节点左孩子
		cur.l = tree.maintain(cur.l)
		// 递归调整当前节点右孩子
		cur = tree.maintain(cur)
	} else if cur.r != nil && cur.r.l != nil && cur.l != nil && cur.r.l.size > cur.l.size { // RL形不平衡调整策略
		// 当前节点右孩子右旋
		cur.r = tree.rightRotate(cur.r)
		// 当前节点左旋
		cur = tree.leftRotate(cur)
		// 递归调整当前节点左孩子
		cur.l = tree.maintain(cur.l)
		// 递归调整当前节点右孩子
		cur.r = tree.maintain(cur.r)
		// 递归调用调整当前节点
		cur = tree.maintain(cur)
	}
	return cur
}

// findLastIndex 查找以key为节点key的节点是否存在
func (tree *SBTree) findLastIndex(key string) *SBTNode {
	pre := tree.Root
	cur := tree.Root
	for cur != nil {
		pre = cur
		if tree.Comparator(key, cur.key) == 0 {
			break
		} else if tree.Comparator(key, cur.key) < 0 {
			cur = cur.l
		} else {
			cur = cur.r
		}
	}
	return pre
}

// findLastNoSmallIndex 找到第一个不比key小的节点，返回。即搜索树中字典序大于key的第一个节点
func (tree *SBTree) findLastNoSmallIndex(key string) *SBTNode {
	var ans *SBTNode
	cur := tree.Root
	for cur != nil {
		if tree.Comparator(key, cur.key) == 0 {
			ans = cur
			break
		} else if tree.Comparator(key, cur.key) < 0 {
			ans = cur
			cur = cur.l
		} else {
			cur = cur.r
		}
	}
	return ans
}

// findLastNoBigIndex 在搜索树上查找不大于key的第一个数，即小于等于key的第一个节点返回
func (tree *SBTree) findLastNoBigIndex(key string) *SBTNode {
	var ans *SBTNode
	cur := tree.Root
	for cur != nil {
		if tree.Comparator(key, cur.key) == 0 {
			ans = cur
			break
		} else if tree.Comparator(key, cur.key) < 0 {
			cur = cur.l
		} else {
			ans = cur
			cur = cur.r
		}
	}
	return ans
}

// add tree树上，加(key, value)这样的一条记录。cur传入tree的头节点
// 加完之后，会对tree做检查，该调整调整
// 返回，调整完之后，整棵树的新头部, 被替换掉了。把新树头节点返回
func (tree *SBTree) add(cur *SBTNode, key string, value int) *SBTNode {
	if cur == nil {
		return InitSBTTree(key, value).Root
	} else {
		cur.size++
		if tree.Comparator(key, cur.key) < 0 {
			cur.l = tree.add(cur.l, key, value)
		} else {
			cur.r = tree.add(cur.r, key, value)
		}
		return tree.maintain(cur)
	}
}

// 在cur这棵树上，删掉key所代表的节点。cur为tree的头节点
// 返回cur这棵树的新头部
func (tree *SBTree) delete(cur *SBTNode, key string) *SBTNode {
	cur.size--
	if tree.Comparator(key, cur.key) > 0 {
		cur.r = tree.delete(cur.r, key)
	} else if tree.Comparator(key, cur.key) < 0 {
		cur.l = tree.delete(cur.l, key)
	} else { // 当前要删掉cur
		if cur.l == nil && cur.r == nil {
			cur = nil // free cur memory
		} else if cur.l == nil && cur.r != nil {
			cur = cur.r // free cur memory
		} else if cur.l != nil && cur.r == nil {
			cur = cur.l // free cur memory
		} else { // 有左右右的情况
			var pre *SBTNode
			des := cur.r
			des.size--

			for des.l != nil {
				pre = des
				des = des.l
				des.size--
			}
			if pre != nil {
				pre.l = des.r
				des.r = cur.r
			}

			des.l = cur.l
			desRSize := 0
			if des.r == nil {
				desRSize = 0
			} else {
				desRSize = des.r.size
			}

			des.size = des.l.size + desRSize + 1
			// free cur memory
			cur = des
		}
	}
	return cur
}

func (tree *SBTree) getIndex(cur *SBTNode, kth int) *SBTNode {
	lSize := 0
	if cur.l != nil {
		lSize = cur.l.size
	} else {
		lSize = 0
	}

	if kth == lSize+1 {
		return cur
	} else if kth <= lSize {
		return tree.getIndex(cur.l, kth)
	} else {
		return tree.getIndex(cur.r, kth-lSize-1)
	}
}

func (tree *SBTree) size() int {
	if tree.Root == nil {
		return 0
	} else {
		return tree.Root.size
	}
}

func (tree *SBTree) containsKey(key string) (bool, error) {
	if len(key) == 0 {
		return false, fmt.Errorf("invalid parameter")
	}

	lastNode := tree.findLastIndex(key)
	isEqual := false
	if tree.Comparator(key, lastNode.key) == 0 {
		isEqual = true
	} else {
		isEqual = false
	}

	return lastNode != nil && isEqual, nil
}

// put 方法，有可能是新增有可能是覆盖更新
func (tree *SBTree) put(key string, value int) error {
	if len(key) == 0 {
		return fmt.Errorf("invalid parameter")
	}

	lastNode := tree.findLastIndex(key)
	if lastNode != nil && tree.Comparator(key, lastNode.key) == 0 {
		lastNode.value = value
	} else {
		// 不存在的话，从根节点调用递归，加入到合适的位置。sb树由于没有向上指针，这里需要从头结点开始调用递归
		// 添加进去后，有可能需要调整，头部有可能会变，返回新的头部
		tree.Root = tree.add(tree.Root, key, value)
	}
	return nil
}

func (tree *SBTree) remove(key string) error {
	if len(key) == 0 {
		return fmt.Errorf("invalid parameter")
	}

	if b, e := tree.containsKey(key); e == nil && b {
		tree.Root = tree.delete(tree.Root, key)
	}
	return nil
}

func (tree *SBTree) getIndexKey(index int) (string, error) {
	if index < 0 || index > tree.Root.size {
		return "",  fmt.Errorf("invalid parameter")
	}

	return tree.getIndex(tree.Root, index + 1).key, nil
}

func (tree *SBTree) getIndexValue(index int) (int, error) {
	if index < 0 || index > tree.Root.size {
		return -1,  fmt.Errorf("invalid parameter")
	}

	return tree.getIndex(tree.Root, index + 1).value, nil
}

func (tree *SBTree) get(key string) (int, error) {
	if len(key) == 0 {
		return -1, fmt.Errorf("invalid parameter")
	}

	lastNode := tree.findLastIndex(key)
	if lastNode != nil && tree.Comparator(key, lastNode.key) == 0 {
		return lastNode.value, nil
	} else {
		return -1, fmt.Errorf("not find")
	}
}

func (tree *SBTree) firstKey() (string, error) {
	if tree.Root == nil {
		return "", fmt.Errorf("not find because root is nil")
	}

	cur := tree.Root
	for cur.l != nil {
		cur = cur.l
	}

	return cur.key, nil
}

func (tree *SBTree) lastKey() (string, error) {
	if tree.Root == nil {
		return "", fmt.Errorf("not find because root is nil")
	}

	cur := tree.Root
	for cur.r != nil {
		cur = cur.r
	}
	return cur.key, nil
}

func (tree *SBTree) floorKey(key string) (string, error) {
	if len(key) == 0 {
		return "", fmt.Errorf("invalid parameter")
	}

	lastNoBigNode := tree.findLastNoBigIndex(key)
	if lastNoBigNode == nil {
		return "", fmt.Errorf("not find")
	} else {
		return lastNoBigNode.key, nil
	}
}

func (tree *SBTree) ceilingKey(key string) (string, error) {
	if len(key) == 0 {
		return "", fmt.Errorf("invalid parameter")
	}
	lastNoSmallNode := tree.findLastNoSmallIndex(key)
	if lastNoSmallNode == nil {
		return "", fmt.Errorf("not find")
	} else {
		return lastNoSmallNode.key, nil
	}
}

func main() {
	sbt := InitSBTTree("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)
	fmt.Println(sbt.get("a"))
	sbt.put("a", 1)
	fmt.Println(sbt.get("a"))
	for i := 0; i<sbt.size(); i++ {
		key, _ := sbt.getIndexKey(i)
		v, _ := sbt.getIndexValue(i)
		fmt.Println(fmt.Sprintf("%s : %d", key, v))
	}

	sbt.printAll(sbt.Root)

	fmt.Println(sbt.firstKey())
	fmt.Println(sbt.lastKey())
	fmt.Println(sbt.floorKey("g"))
	fmt.Println(sbt.ceilingKey("g"))
	fmt.Println(sbt.floorKey("e"))
	fmt.Println(sbt.ceilingKey("e"))
	fmt.Println(sbt.floorKey(""))
	fmt.Println(sbt.ceilingKey(""))
	fmt.Println(sbt.floorKey("j"))
	fmt.Println(sbt.ceilingKey("j"))

	sbt.remove("d")
	sbt.printAll(sbt.Root)
	sbt.remove("f")
	sbt.printAll(sbt.Root)
}

func (tree *SBTree) printAll(head *SBTNode) {
	fmt.Println("Binary Tree:")
	tree.printInOrder(head, 0, "H", 17)
	fmt.Println()
}

func (tree *SBTree) printInOrder(head *SBTNode, height int, to string, length int) {
	if head == nil {
		return
	}

	tree.printInOrder(head.r, height + 1, "v", length)
	val := fmt.Sprintf("%s(%s,%d)%s", to, head.key, head.value, to)
	lenM := len(val)
	lenL := (length - lenM) / 2
	lenR := length - lenM - lenL
	val = fmt.Sprintf("%s%s%s", getSpace(lenL) , val, getSpace(lenR) )
	fmt.Println(fmt.Sprintf("%s%s", getSpace(height * length), val))
	tree.printInOrder(head.l, height + 1, "^", length)
}

func getSpace(num int) string {
	space := byte(' ')
	var buffer []byte
	for i := 0; i < num; i++ {
		buffer = append(buffer, space)
	}

	return string(buffer)
}
```

- SB树也可以使用数组进行实现：TODO


### 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+）树之间达到平衡。各有取舍

> 红黑树的实现，可以参考：https://github.com/emirpasic/gods/blob/master/trees/redblacktree/redblacktree.go


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

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


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

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

**最烧脑的结构**

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

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

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

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

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

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


```Go
package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

const (
	UP_LEVELS_ABILITY = 500
	UP_LEVELS_TOTAL = 1000
)

type skipListNode struct {
	score int64
	val   interface{}
	next  *skipListNode
	pre   *skipListNode
	up    *skipListNode
	down  *skipListNode
}

type skipList struct {
	head   *skipListNode
	tail   *skipListNode
	size   int
	levels int
}

func NewSkipList() *skipList {
	sl := new(skipList)
	sl.head = new(skipListNode)
	sl.tail = new(skipListNode)
	sl.head.score = math.MinInt64
	sl.tail.score = math.MaxInt64

	sl.head.next = sl.tail
	sl.tail.pre = sl.head

	sl.size = 0
	sl.levels = 1

	return sl
}

func (sl *skipList) Size() int {
	return sl.size
}

func (sl *skipList) Levels() int {
	return sl.levels
}

func (sl *skipList) Get(score int64) interface{} {
	node := sl.findNode(score)
	if node.score == score {
		return node.val
	} else {
		return nil
	}
}

func (sl *skipList) Insert(score int64, val interface{}) {
	f := sl.findNode(score)
	if f.score == score {
		f.val = val
		return
	}
	curNode := new(skipListNode)
	curNode.score = score
	curNode.val = val

	sl.insertAfter(f, curNode)

	rander := rand.New(rand.NewSource(time.Now().UnixNano()))

	curlevels := 1
	for rander.Intn(UP_LEVELS_TOTAL) < UP_LEVELS_ABILITY {
		curlevels++
		if curlevels > sl.levels {
			sl.newlevels()
		}

		for f.up == nil {
			f = f.pre
		}
		f = f.up
		tmpNode := &skipListNode{score: score}

		curNode.up = tmpNode
		tmpNode.down = curNode
		sl.insertAfter(f, tmpNode)

		curNode = tmpNode
	}

	sl.size++
}

func (sl *skipList) Remove(score int64) interface{} {
	f := sl.findNode(score)
	if f.score != score {
		return nil
	}
	v := f.val

	for f != nil {
		f.pre.next = f.next
		f.next.pre = f.pre
		f = f.up
	}
	return v
}

func (sl *skipList) newlevels() {
	nhead := &skipListNode{score: math.MinInt64}
	ntail := &skipListNode{score: math.MaxInt64}
	nhead.next = ntail
	ntail.pre = nhead

	sl.head.up = nhead
	nhead.down = sl.head
	sl.tail.up = ntail
	ntail.down = sl.tail

	sl.head = nhead
	sl.tail = ntail
	sl.levels++
}

func (sl *skipList) insertAfter(pNode *skipListNode, curNode *skipListNode) {
	curNode.next = pNode.next
	curNode.pre = pNode
	pNode.next.pre = curNode
	pNode.next = curNode
}

func (sl *skipList) findNode(score int64) *skipListNode {
	p := sl.head

	for p != nil {
		if p.score == score {
			if p.down == nil {
				return p
			}
			p = p.down
		} else if p.score < score {
			if p.next.score > score {
				if p.down == nil {
					return p
				}
				p = p.down
			} else {
				p = p.next
			}
		}
	}
	return p
}

func (sl *skipList) Print() {

	mapScore := make(map[int64]int)

	p := sl.head
	for p.down != nil {
		p = p.down
	}
	index := 0
	for p != nil {
		mapScore[p.score] = index
		p = p.next
		index++
	}
	p = sl.head
	for i := 0; i < sl.levels; i++ {
		q := p
		preIndex := 0
		for q != nil {
			s := q.score
			if s == math.MinInt64 {
				fmt.Printf("%s", "BEGIN")
				q = q.next
				continue
			}
			index := mapScore[s]
			c := (index - preIndex - 1) * 6
			for m := 0; m < c; m++ {
				fmt.Print("-")
			}
			if s == math.MaxInt64 {
				fmt.Printf("-->%s\n", "END")
			} else {
				fmt.Printf("-->%3d", s)
				preIndex = index
			}
			q = q.next
		}
		p = p.down
	}
}

func main() {
	sk := NewSkipList()

	sk.Insert(100, "lala")
	sk.Insert(11, "sx")
	sk.Insert(22, "11")
	sk.Insert(3, "dd")
	sk.Insert(80, "bb")
	sk.Insert(77, "bb")
	sk.Insert(6, "bb")
	sk.Insert(88, "bb")
	sk.Insert(33, "bb")
	sk.Insert(44, "bb")

	//fmt.Println(sk.Get(22))
	//fmt.Println(sk.Get(55))
	//fmt.Println(sk.Remove(22))
	//fmt.Println(sk.Get(22))
	//fmt.Println(sk.Size())
	//fmt.Println(sk.Layout())
	sk.Print()
}
```



## 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个

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