1.排序

1.1 冒泡排序

1.1.1 冒泡排序优化版

检测是否已提前有序

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func BubbleSort(arr []int) []int {
	n := len(arr)
	// 遍历所有元素
	var isSorted bool
	for i := 0; i < n-1; i++ {
		isSorted = true
		for j := 0; j < n-i-1; j++ {
			// 左元素 > 右元素
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				// 发生交换则还未排序完毕
				isSorted = false
			}
			fmt.Println("[DEBUG]:\t", arr)
		}
		// 没有发生交换则说明排序完成
		if isSorted {
			break
		}
	}
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = BubbleSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

缩短扫描距离

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func BubbleSort(arr []int) []int {
	n := len(arr)
	end := n - 1
	for end > 0 {
		cur := 0
		for j := 0; j < end; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
            // 记录每趟最后发生交换的位置，此位置之后均已有序，下一趟只需遍历到此位置即可
			cur = j
		}
		fmt.Println("[DEBUG]:\t", arr)
		end = cur
	}
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = BubbleSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.1.2 双向冒泡排序(鸡尾酒排序)

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func BubbleSort(arr []int) []int {
	n := len(arr)
	left := 0
	right := n - 1

	// left  以左已有序
	// right 以右已有序
	// 两个区间游标相遇则集合有序
	for left < right {
		// 从左到右，选出最大值
		for i := left; i < right; i++ {
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
			}
		}
		right--
		fmt.Println("[DEBUG right]:\t", arr)
		// 从右到左，选出最小值
		for i := right; i > left; i-- {
			if arr[i-1] > arr[i] {
				arr[i-1], arr[i] = arr[i], arr[i-1]
			}
		}
		left++
		fmt.Println("[DEBUG left]:\t", arr)
	}
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = BubbleSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.2 选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func SelectSort (arr []int) []int {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		// 假设无序区间第一个值为最小值
		min := i
		for next := min + 1; next < n; next++ {
			// 找到更小值，记录其位置
			if arr[min] > arr[next] {
				min = next
			}
		}
		// 将无序区间的最小值追加到有序区间
		fmt.Println("[DEBUG min]:\t", arr[min])
		arr[i], arr[min] = arr[min], arr[i]
	}
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = SelectSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.3 插入排序

平均时间复杂度 O(n2)

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func InsertSort (arr []int) []int {
	n := len(arr)
	if n <= 1 {
		fmt.Println("[ALREADY SORTED]:\t", arr)
		return []int{}
	}
	// 遍历所有元素
	for i := 1; i < n; i++ {
		// 向前找位置
		for j := i; j > 0; j-- {
			// 合适位置插入
			if arr[j-1] > arr[j] {
				arr[j-1], arr[j] = arr[j], arr[j-1]
			}
		}
		fmt.Println("[DEBUG]:\t", arr)
	}
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = InsertSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.4 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

一般来说时间复杂度为：O(Nlog2N)

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func ShellSort (arr []int) []int {
	n := len(arr)
	if n <= 1 {
		fmt.Println("[ALREADY SORTED]:\t", arr)
		return []int{}
	}

	step := n / 2

	// 步长减少到 0 则排序完毕
	for step > 0 {
		fmt.Println("[DEBUG step]:\t", step)

		// 遍历第一个步长区间之后的所有元素
		for i := step; i < n; i++ {
			j := i
			// 前一个元素更大则交换值
			// j >= step	// 避免向下越界
			for j >= step && arr[j-step] > arr[j] {
				arr[j-step], arr[j] = arr[j], arr[j-step]
				j -= step
			}
			fmt.Println("[DEBUG]:\t", arr)
		}
		step /= 2
	}
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = ShellSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.5 快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。快速排序是冒泡排序的优化版，同属于交换类排序。它使用了 “分治法” 的思想，将集合分割为相似子集，再对子集进行递归排序，最后将子集的排序结果组合即可。

分治法

先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。

平均时间复杂度：O(N*logN)

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func QuickSort (arr []int) []int {
	n := len(arr)
	// 递归结束条件
	if n <= 1 {
		temp := make([]int, n)
		copy(temp, arr)
		return temp
	}

	// 使用第一个元素作为基准值
	pivot := arr[0]

	// 小元素 和 大元素各成一个数组
	low := make([]int, 0, n)
	high := make([]int, 0, n)

	// 更小的元素放 low[]
	// 更大的元素放 high[]
	for i := 1; i < n; i++ {
		if arr[i] < pivot {
			low = append(low, arr[i])
		} else {
			high = append(high, arr[i])
		}
	}
	// 子区间递归快排，分治排序
	low, high = QuickSort(low), QuickSort(high)
	fmt.Println("[DEBUG low]:\t", low)
	fmt.Println("[DEBUG high]:\t", high)
	return append(append(low, arr[0]), high...)
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = QuickSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.6 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。归并排序与快速排序类似，也采用了“分治法”的思想。

快速排序：选取基准后，将集合分割为左右子集合再进行递归分组，最后合并排序好的各子集合.

归并排序：将集合均分为左右子集合，各自在内部进行递归排序，最后合并排序好的各子集合

平均时间复杂度：O(NlogN)

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func merge(left, right []int) []int {
	// 遍历比较后合并两个数组
	res := make([]int, 0, len(left)+len(right))
	for len(left) > 0 || len(right) > 0 {
		// 数组提前排序完毕
		if len(left) == 0 {
			return append(res, right...)
		}
		if len(right) == 0 {
			return append(res, left...)
		}
		// 比较更小的值追加到 res[] 中
		if left[0] < right[0] {
			res = append(res, left[0])
			left = left[1:]
		} else {
			res = append(res, right[0])
			right = right[1:]
		}
	}
	return res
}

func MergeSort (arr []int) []int {
	// 递归结束条件
	if len(arr) <= 1 {
		return arr
	}
	mid := len(arr) / 2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])
	arr = merge(left, right)
	fmt.Println("[DEBUG merged]:\t", arr)
	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = MergeSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.7 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法（一般升序采用大顶堆，降序采用小顶堆)：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func HeapSort(arr []int) []int {
	arrLen := len(arr)
	buildMaxHeap(arr, arrLen)
	for i := arrLen - 1; i >= 0; i-- {
		swap(arr, 0, i)
		arrLen -= 1
		heapify(arr, 0, arrLen)
	}
	return arr
}

func buildMaxHeap(arr []int, arrLen int) {
	for i := arrLen / 2; i >= 0; i-- {
		heapify(arr, i, arrLen)
	}
}

func heapify(arr []int, i, arrLen int) {
	left := 2*i + 1
	right := 2*i + 2
	largest := i
	if left < arrLen && arr[left] > arr[largest] {
		largest = left
	}
	if right < arrLen && arr[right] > arr[largest] {
		largest = right
	}
	if largest != i {
		swap(arr, i, largest)
		heapify(arr, largest, arrLen)
	}
}

func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = HeapSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.8 计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

时间复杂度为：O(N + max + 1)

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func getMax(arr []int) (max int) {
	max = arr[0]
	for _, v := range arr {
		if max < v {
			max = v
		}
	}
	return
}

func CountSort(arr []int) []int {
	max := getMax(arr)
	sortedArr := make([]int, len(arr))
	countsArr := make([]int, max+1) // max+1 是为了防止 countsArr[] 计数时溢出

	// 元素计数
	for _, v := range arr {
		countsArr[v]++
	}

	// 统计独特数字个数并累加
	for i := 1; i <= max; i++ {
		countsArr[i] += countsArr[i-1]
	}

	fmt.Println("[DEBUG countsArr]:\t", countsArr)

	// 让 arr 中每个元素找到其位置
	for _, v := range arr {
		sortedArr[countsArr[v]-1] = v
		//fmt.Print(countsArr[v]-1, " ")
		// 保证稳定性
		countsArr[v]--
	}
	return sortedArr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = CountSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.9 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}

func RadixSort(arr []int) []int {
	max := getMax(arr)
	// 数组中最大值决定了循环次数，101 循环三次
	for bit := 1; max/bit > 0; bit *= 10 {
		arr = bitSort(arr, bit)
		fmt.Println("[DEBUG bit]\t", bit)
		fmt.Println("[DEBUG arr]\t", arr)
	}
	return arr
}

//
// 对指定的位进行排序
// bit 可取 1，10，100 等值
//
func bitSort(arr []int, bit int) []int {
	n := len(arr)
	// 各个位的相同的数统计到 bitCounts[] 中
	bitCounts := make([]int, 10)
	for i := 0; i < n; i++ {
		num := (arr[i] / bit) % 10
		bitCounts[num]++
	}
	for i := 1; i < 10; i++ {
		bitCounts[i] += bitCounts[i-1]
	}

	tmp := make([]int, 10)
	for i := n - 1; i >= 0; i-- {
		num := (arr[i] / bit) % 10
		tmp[bitCounts[num]-1] = arr[i]
		bitCounts[num]--
	}
	for i := 0; i < n; i++ {
		arr[i] = tmp[i]
	}
	return arr
}

// 获取数组中最大的值
func getMax(arr []int) (max int) {
	max = arr[0]
	for _, v := range arr {
		if max < v {
			max = v
		}
	}
	return
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = RadixSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

1.10 桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

package main

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

// 获取 n 个 [0, max] 元素组成的数组
func GetArr(n, max int) []int {
	rand.Seed(time.Now().UnixNano())
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(max + 1)
	}
	return arr
}
func sortInBucket(bucket []int) {//此处实现插入排序方式，其实可以用任意其他排序方式
	length := len(bucket)
	if length == 1 {return}

	for i := 1; i < length; i++ {
		backup := bucket[i]
		j := i -1;
		//将选出的被排数比较后插入左边有序区
		for  j >= 0 && backup < bucket[j] {//注意j >= 0必须在前边，否则会数组越界
			bucket[j+1] = bucket[j]//移动有序数组
			j -- //反向移动下标
		}
		bucket[j + 1] = backup //插队插入移动后的空位
	}
}
/*
获取数组最大值
*/
func getMaxInArr(arr []int) int{
	max := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] > max{ max = arr[i]}
	}
	return max
}
/*
桶排序
*/
func BucketSort(arr []int) []int {
	//桶数
	num := len(arr)
	//k（数组最大值）
	max := getMaxInArr(arr)
	//二维切片
	buckets := make([][]int, num)

	//分配入桶
	index := 0
	for i := 0; i < num; i++ {
		index = arr[i] * (num-1) /max//分配桶index = value * (n-1) /k

		buckets[index] = append(buckets[index], arr[i])
	}
	//桶内排序
	tmpPos := 0
	for i := 0; i < num; i++ {
		bucketLen := len(buckets[i])
		if bucketLen > 0{
			sortInBucket(buckets[i])

			copy(arr[tmpPos:], buckets[i])

			tmpPos += bucketLen
		}
	}

	return arr
}

func main()  {
	arr := GetArr(5, 20)
	fmt.Println("[UNSORTED]:\t", arr)
	arr = BucketSort(arr)
	fmt.Println("[SORTED]:\t", arr)
}

2.查找

2.1 顺序查找

package main

import "fmt"

func main() {
	items := []int{95, 78, 46, 58, 45, 86, 99, 251, 320}
	if index := linearSearch(items, 45); index == nil {
		fmt.Println("not exist")
	} else {
		fmt.Printf("exist, index is %d\n", *index)
	}

}

func linearSearch(a []int, key int) (index *int) {
	for i, item := range a {
		if item == key {
			index = &i
			return
		}
	}
	return nil
}

2.2 插值查找

package main

import (
	"fmt"
	"sort"
)

func main() {
	items := []int{1, 5, 2, 4, 3, 7, 9, 6}

	sort.Ints(items)

	fmt.Println(interpolationSearch(5, items))
}

func interpolationSearch(key int, a []int) bool {

	low := 0
	high := len(a) - 1

	for low <= high {
		var guess int
		if high == low {
			guess = high
		} else {
			size := high - low
			offset := size * (key - a[low]) / (a[high] - a[low])
			guess = low + offset
		}

		if a[guess] < key {
			low = guess + 1
		} else if a[guess] > key {
			high = guess - 1
		} else {
			return true
		}

	}

	return false
}

2.3 二分查找

二分查找前提是有序

package main

import (
	"fmt"
	"sort"
)

func main() {
	items := []int{1, 5, 3, 7, 8, 2, 6, 8}

	// sort
	sort.Ints(items) // {1, 2, 3, 5, 6, 7, 8, 9}

	// 非递归
	fmt.Println(BinarySearch(8, items))  		// -1: 查找不到你
	// 递归
	fmt.Println(BinarySearchRecursive(8, items)) // -1: 查找不到你
	// 查找第一个等于给定值的元素
	fmt.Println(BinarySearchFirst(8, items)) // -1: 查找不到你
	// 查找最后一个值等于给定值的元素
	fmt.Println(BinarySearchLast(8, items)) // -1: 查找不到你
	// 查找第一个大于等于给定值的元素
	fmt.Println(BinarySearchFirstGT(8, items)) // -1: 查找不到你
	// 查找最后一个小于等于给定值的元素
	fmt.Println(BinarySearchLastLT(8, items)) // -1: 查找不到你

}

// 非递归
func BinarySearch(key int, a []int) int {

	low := 0
	high := len(a) - 1

	for low <= high {
		mid := low + (high-low)/2

		if a[mid] < key {
			low = mid + 1
		} else if a[mid] > key {
			high = mid - 1
		} else {
			return mid
		}
	}

	return -1
}

//递归
func BinarySearchRecursive(v int,a []int) int {
	n := len(a)
	if n == 0 {
		return -1
	}

	return bs(a, v, 0, n-1)
}

func bs(a []int, v int, low, high int) int {
	if low > high {
		return -1
	}

	mid := (low + high) >> 1
	if a[mid] == v {
		return mid
	} else if a[mid] > v {
		return bs(a, v, low, mid-1)
	} else {
		return bs(a, v, mid+1, high)
	}
}

//查找第一个等于给定值的元素
func BinarySearchFirst(v int,a []int) int {
	n := len(a)
	if n == 0 {
		return -1
	}

	low := 0
	high := n - 1
	for low <= high {
		mid := (low + high) >> 1
		if a[mid] > v {
			high = mid - 1
		} else if a[mid] < v {
			low = mid + 1
		} else {
			if mid == 0 || a[mid-1] != v {
				return mid
			} else {
				high = mid - 1
			}
		}
	}

	return -1
}

//查找最后一个值等于给定值的元素
func BinarySearchLast(v int,a []int) int {
	n := len(a)
	if n == 0 {
		return -1
	}

	low := 0
	high := n - 1
	for low <= high {
		mid := (low + high) >> 1
		if a[mid] > v {
			high = mid - 1
		} else if a[mid] < v {
			low = mid + 1
		} else {
			if mid == n-1 || a[mid+1] != v {
				return mid
			} else {
				low = mid + 1
			}
		}
	}

	return -1
}

//查找第一个大于等于给定值的元素
func BinarySearchFirstGT(v int,a []int) int {
	n := len(a)
	if n == 0 {
		return -1
	}

	low := 0
	high := n - 1
	for low <= high {
		//避免溢出
		mid := low + (high-low)>>1
		if a[mid] >= v {
			if mid == 0 || a[mid-1] < v {
				return mid
			} else {
				high = mid - 1
			}
		} else {
			low = mid + 1
		}
	}

	return -1
}

//查找最后一个小于等于给定值的元素
func BinarySearchLastLT( v int,a []int) int {
	n := len(a)
	if n == 0 {
		return -1
	}

	low := 0
	high := n - 1
	for low <= high {
		mid := low + (high-low)>>1
		if a[mid] > v {
			high = mid - 1
		} else {
			if mid == n-1 || a[mid+1] > v {
				return mid
			} else {
				low = mid + 1
			}
		}
	}

	return -1
}

3.链表

3.1 单链表

package main
import (
	"fmt"
	"sync"
)

// Item the type of the linked list
type Item interface {}

// Node a single node that composes the list
type Node struct {
	data Item
	next *Node
}

// ItemLinkedList the linked list of Items
type ItemLinkedList struct {
	head *Node
	size int
	lock sync.RWMutex
}

// Append adds an Item to the end of the linked list
func (ll *ItemLinkedList) Append(t Item) {
	ll.lock.Lock()
	defer ll.lock.Unlock()
	node := Node{t, nil}
	if ll.head == nil {
		ll.head = &node
	} else {
		last := ll.head
		for {
			if last.next == nil {
				break
			}
			last = last.next
		}
		last.next = &node
	}
	ll.size++
}

// Insert adds an Item at position i
func (ll *ItemLinkedList) Insert(i int, t Item) error {
	ll.lock.Lock()
	defer ll.lock.Unlock()
	if i < 0 || i > ll.size {
		return fmt.Errorf("Index out of bounds")
	}
	addNode := Node{t, nil}
	if i == 0 {
		addNode.next = ll.head
		ll.head = &addNode
		return nil
	}
	node := ll.head
	for j := 0; j < i-2; j++ {
		node = node.next
	}
	addNode.next = node.next
	node.next = &addNode
	ll.size++
	return nil
}

// RemoveAt removes a node at position i
func (ll *ItemLinkedList) RemoveAt(i int) (*Item, error) {
	ll.lock.Lock()
	defer ll.lock.Unlock()
	if i < 0 || i > ll.size {
		return nil, fmt.Errorf("Index out of bounds")
	}
	node := ll.head
	j := 0
	for j < i-1 {
		j++
		node = node.next
	}
	remove := node.next
	node.next = remove.next
	ll.size--
	return &remove.data, nil
}

// IndexOf returns the position of the Item t
func (ll *ItemLinkedList) IndexOf(t Item) int {
	ll.lock.RLock()
	defer ll.lock.RUnlock()
	node := ll.head
	i := 0
	for {
		if node.data == t {
			return i
		}
		if node.next == nil {
			return -1
		}
		node = node.next
		i++
	}
}

// IsEmpty returns true if the list is empty
func (ll *ItemLinkedList) IsEmpty() bool {
	ll.lock.RLock()
	defer ll.lock.RUnlock()
	if ll.head == nil {
		return true
	}
	return false
}

// Size returns the linked list size
func (ll *ItemLinkedList) Size() int {
	ll.lock.RLock()
	defer ll.lock.RUnlock()
	last := ll.head
	if last == nil {
		return 0
	}

	size := 1
	for {
		if last.next == nil {
			break
		}
		last = last.next
		size++
	}
	return size
}

// Insert adds an Item at position i
func (ll *ItemLinkedList) String() {
	ll.lock.RLock()
	defer ll.lock.RUnlock()
	node := ll.head
	for i := 0; node != nil; i++ {
		fmt.Print(node.data)
		fmt.Print(" ")
		node = node.next
	}
	fmt.Println()
}

// Head returns a pointer to the first node of the list
func (ll *ItemLinkedList) Head() *Node {
	ll.lock.RLock()
	defer ll.lock.RUnlock()
	return ll.head
}

func main()  {
	list := ItemLinkedList{}
	list.Append("1")
	list.Append("2")
	list.Append("3")
	list.Append("4")
	list.Append("a")
	list.Append("b")
	list.Append("c")
	list.Append("d")
	list.String() // 1 2 3 4 a b c d

	fmt.Println(fmt.Sprintf("list length: %v",list.Size()))

	_ = list.Insert(1,"x")
	list.String() // 1 x 2 3 4 a b c d

	index := list.IndexOf("a")
	fmt.Println(fmt.Sprintf("index: %d",index))

}

3.2 双链表

package main

import "fmt"

type  LinkList interface {
	Clear() //清空
	Len()//求长度
	Front()*Element //第一个
	Back()*Element //最后一个
	Remove(e *Element) * Element
	Setdata(old,new interface{})
	Insert(e,mark *Element)*Element
	InsertValue(v interface{},mark *Element)*Element
	PushFront(data  interface{})*Element
	PushBack(data  interface{})*Element
	InsertBefore(data  interface{},mark *Element)*Element
	InsertAfter(data  interface{},mark *Element)*Element
	MoveBrfore(e,mark *Element)
	MoveAfter(e,mark *Element)
	Show()
}

type Element struct{
	prev,next *Element //前一个指针，后一个指针
	value  interface{}  //数据
	list * List
}

type List struct{
	root Element  //根元素，长度
	len int
}


func  New() *List{
	list:=new(List)
	list.Clear() //清空
	return list
}
func (list *List) Clear(){
	if firstelem:=list.root.next;firstelem!=nil && firstelem.list==list{
		firstelem.prev=nil
	}
	if lastelem:=list.root.prev;lastelem!=nil && lastelem.list==list{
		lastelem.prev=nil
	}
	list.root.next=&list.root
	list.root.prev=&list.root
	list.len=0
}
func (list *List) Len()int {
	return list.len
}
func (list *List)Front() *Element{
	if  list.len==0{
		return nil
	}
	return list.root.next//第一个节点
}

func (list *List) Back()*Element{
	if  list.len==0{
		return nil
	}
	return list.root.prev//最后一个节点
}
func (list *List) Insert(e,mark *Element)*Element{
	nbak :=mark.next  //备份
	mark.next =e
	e.prev=mark
	e.next=nbak
	nbak.prev=e
	e.list=list //保存链表的都指针
	list.len++ //长度+1
	return e

}
func (list *List) InsertValue(v interface{},mark *Element)*Element{
	return list.Insert(&Element{value:v},mark) //插入
}

func (list *List) PushFront(data  interface{})*Element{
	return list.InsertValue(data,&list.root) //前面插入
}
func (list *List) PushBack(data  interface{})*Element{
	return list.InsertValue(data,list.root.prev) //后面插入
}
//删除
func (list *List)Remove(e* Element)* Element{
	e.prev.next=e.next
	e.next.prev=e.prev
	e.next=nil
	e.prev=nil
	e.list=nil
	list.len--
	return e
}
//删除指定数据
func (list *List)Removedata(data interface{}) interface{}{
	for phead:=list.root.next;phead!=&list.root;phead=phead.next{
		if phead.value==data{
			list.Remove(phead)  //查找并删除
			return phead.value

		}

	}
	return nil
}
func (list *List) Show(){
	fmt.Println("链表开始")
	for phead:=list.root.next;phead!=&list.root;phead=phead.next{
		fmt.Println(phead.value)
	}
	fmt.Println("链表结束")
}
func (list *List)InsertBefore(data  interface{},mark *Element)*Element{
	if mark.list!=list{  //没有前置
		return nil
	}
	return list.InsertValue(data,mark.prev)
}
func (list *List)InsertAfter(data  interface{},mark *Element)*Element{
	if mark.list!=list{  //没有前置
		return nil
	}
	return list.InsertValue(data,mark)
}
func (list *List)MoveBrfore(e,mark *Element){
	if e.list!=list || list.root.next==e{
		return
	}

	list.Insert(list.Remove(e),mark.prev)
}
func (list *List)ReMoveAfter(e,mark *Element){
	if e.list!=list || list.root.prev==e{
		return
	}
	list.Insert(list.Remove(e),&list.root)
}
func (list *List) Setdata(old,new interface{}){
	for phead:=list.root.next;phead!=&list.root;phead=phead.next{
		if phead.value==old{
			phead.value=new  //更新
		}
		//fmt.Println(phead.value)
	}
}

func main(){
	mylist:=New()
	mylist.PushFront(1)
	mylist.PushFront(2)
	mylist.PushFront(3)
	mylist.PushFront(4)
	mylist.PushBack(5)
	mylist.Show()
}

4.队列

4.1 链式队列

package main

import "fmt"

//链表单节点
type  QNode struct{
	data  interface{} //数据
	next * QNode //地址
}


type QueueLink struct{  //队列的头部，尾部
	rear *QNode
	front *QNode
}


type  SQueue interface {
	length() int
	Enqueue(value  interface{})
	Dequeue()(  interface{},error)
}


func NewLinkQueue() * QueueLink{
	return &QueueLink{}
}

func (qlk *QueueLink)length() int{
	length := 0
	pnode := qlk.front //备份
	for pnode != qlk.rear{ //一直到循环到重合为zhi
		pnode = pnode.next  //循环链表尾部
		length++
	}
	return length
}
func ( qlk *QueueLink) Enqueue(value  interface{}){
	newnode :=&QNode{data:value} //构造一个节点，返回地址
	if qlk.front == nil{  //只有一个节点
		qlk.front = newnode
		qlk.rear = newnode

	}else{
		qlk.rear.next = newnode
		qlk.rear = qlk.rear.next
	}
}

func (qlk *QueueLink ) Dequeue()( value interface{},err error){
	if qlk.front == nil{
		return nil,nil
	}
	newnode := qlk.front
	if qlk.front == qlk.rear{
		qlk.front = nil
		qlk.rear = nil
	}else{
		qlk.front = qlk.front.next //删除一个元素
	}
	return newnode.data,nil
}

func main() {
	myq := NewLinkQueue()
	for i:=0;i<10;i++{
		myq.Enqueue(i)
	}
	fmt.Println("length",myq.length())
	for i:=0;i<10;i++{
		fmt.Println(myq.Dequeue())
	}
}

4.2 数组队列

package main

import "fmt"

type QueueInter interface {
	Size()int   		//大小
	Front()interface{} 	//第一个元素
	End()interface{} 	//最后一个元素
	IsEmpty() bool 		//是否为空
	Enqueue(data interface{}) 	//入队
	Dequeue() interface{} 		//出对
	Clear()				//清空
}

type  Queue struct{
	datastore []interface{}
	theSize int
}

func(myqueue *Queue) Clear(){
	myqueue.datastore = make([]interface{},0)  //开辟内存
	myqueue.theSize = 0
}

func NewQueue() *Queue{
	myqueue := new(Queue)
	myqueue.Clear()
	return myqueue

}
func(myqueue *Queue) Size()int   {
	return  myqueue.theSize //大小
}
func(myqueue *Queue) Front()interface{} {
	if myqueue.Size() == 0{ //判断是否为空
		return nil
	}
	return myqueue.datastore[0]
}
func(myqueue *Queue) End()interface{} {
	if myqueue.Size() == 0{ //判断是否为空
		return nil
	}
	return myqueue.datastore[myqueue.theSize-1]
}
func(myqueue *Queue) IsEmpty() bool{
	return  myqueue.theSize == 0
}
func(myqueue *Queue) Enqueue(data interface{}) {
	myqueue.datastore = append( myqueue.datastore,data) //入队
	myqueue.theSize++
}
func(myqueue *Queue) Dequeue() interface{} {
	if myqueue.Size() == 0{ //判断是否为空
		return nil
	}
	data := myqueue.datastore[0]
	if  myqueue.Size()>1 {
		myqueue.datastore = myqueue.datastore[1:myqueue.theSize] //截取
	}
	myqueue.theSize--
	return  data
}

func main(){
	myq := NewQueue()
	myq.Enqueue(1)
	myq.Enqueue(2)
	myq.Enqueue(3)
	myq.Enqueue(4)
	fmt.Println(myq.Size())
	fmt.Println(myq.Dequeue())
	fmt.Println(myq.Dequeue())
	fmt.Println(myq.Dequeue())
	fmt.Println(myq.Dequeue())
	fmt.Println(myq.Size())
	myq.Enqueue(1)
	myq.Enqueue(2)
	myq.Enqueue(3)
	myq.Enqueue(4)
	myq.Clear()
	fmt.Println(myq.Size())
}

4.3 优先队列

基于二叉堆

5.栈

5.1 数组栈

package main

import (
	"errors"
	"fmt"
)

type StackArray interface{
	Clear()
	Size()int
	Pop() interface{}
	Push(data interface{})
	isEmpty() bool
	isFull() bool
}

type ArrayList struct{
	dataStore [] interface{}
	theSize int
}

func New() *ArrayList{
	list := new(ArrayList)
	list.dataStore = make([]interface{},0,10) //分配内存10个数组元素

	list.theSize = 0  //0
	//fmt.Println("new",list.theSize,cap(list.dataStore))
	return list
}

func(list *ArrayList) Append (newval  interface{}){
	//list.checkmemisfull()
	list.dataStore=append(list.dataStore,newval) //数据叠加
	//fmt.Println(list.theSize,cap(list.dataStore))
	//list.dataStore[list.theSize]=newval  //赋值
	list.theSize++ //索引移动
}

func (list *ArrayList )Remove(index int)error {
	if index < 0 || index >= list.theSize{
		return errors.New("索引越界")
	}

	list.dataStore = append(list.dataStore[:index],list.dataStore[index+1:]...) //删除
	list.theSize--
	return  nil
}

func (list *ArrayList )Clear() {
	list.dataStore = make([]interface{},0,10) //清空
	list.theSize = 0
}

type  Stack struct{
	myarray *ArrayList
	capsize int
}

func NewStack()*Stack{
	mystack := new(Stack)
	mystack.myarray = New()
	mystack.capsize = 10  //0
	return mystack
}

func (mystack *Stack) Clear(){
	mystack.myarray.Clear()
	mystack.myarray.theSize = 0
}

func (mystack *Stack) Size()int {
	return mystack.myarray.theSize
}

func (mystack *Stack) isEmpty() bool{
	if mystack.myarray.theSize == 0{
		return true
	}else{
		return false
	}
}

func (mystack *Stack) isFull() bool{
	if mystack.capsize == mystack.myarray.theSize{
		return true
	}else{
		return false
	}
}

func (mystack *Stack) Pop() interface{}{
	if !mystack.isEmpty(){
		last := mystack.myarray.dataStore[mystack.myarray.theSize-1]
		mystack.myarray.Remove(mystack.myarray.theSize-1)
		return last
	}
	return nil
}

func (mystack *Stack) Push(data interface{}){
	if !mystack.isFull(){
		mystack.myarray.Append(data)
	}
}

func main(){
	mystack :=NewStack()
	mystack.Push(1)
	mystack.Push(2)
	mystack.Push(3)
	mystack.Push(4)
	fmt.Println(mystack.Pop())
	fmt.Println(mystack.Pop())
	fmt.Println(mystack.Pop())
	fmt.Println(mystack.Pop())
}

5.2 链式栈

package main

import (
	"errors"
	"fmt"
)

type Node struct{
	data interface{}
	next *Node
}

type LinkStack interface {
	IsEmpty() bool
	Push(value interface{})
	Pop()(interface{},error)
	Length() int
}

func NewStack() *Node {
	return &Node{}
}

func (n *Node)IsEmpty() bool {  //判断是否为空
	return n.next == nil
}
func (n *Node)Push(value interface{}) {
	newnode := &Node{data:value} //初始化
	newnode.next = n.next
	n.next = newnode
}
func (n *Node)Pop() (interface{},error) {
	if n.IsEmpty() == true{
		return  nil,errors.New("bug")
	}
	value := n.next.data
	n.next = n.next.next
	return value,nil
}
func (n *Node)Length() int {
	pnext := n
	length := 0
	for pnext.next != nil{//返回长度
		pnext = pnext.next
		length++
	}
	return length
}
func main(){
	mystack := NewStack()
	for i := 0;i < 10;i++{
		mystack.Push(i)
	}

	for data,err := mystack.Pop();err == nil;data,err = mystack.Pop(){
		fmt.Println(data)
	}
}

6.堆

6.1 二叉堆

package main

import "fmt"

type IBinaryHeap interface {
	Add(data int)
	AddSlice(data []int)
	Length() int
	BuildMax(dataLen int)
	BuildMin(dataLen int)
	SortAsc()
	SortDesc()
	Show()
}

type BinaryHeap struct {
	data []int
}

func (b *BinaryHeap) Add(data int) {
	if b.Length() == 0 {
		b.data = append(b.data, 1)
	}
	b.data = append(b.data, data)
	b.data[0]++
}

func (b *BinaryHeap) AddSlice(data []int) {
	for _, item := range data {
		b.Add(item)
	}
}

func (b *BinaryHeap) Length() int {
	return len(b.data)
}

// BuildMax : 构建大根堆
func (b *BinaryHeap) BuildMax(dataLen int) {
	// 循环所有的父节点(从后向前循环)
	for i := (dataLen - 1) / 2; i >= 1; i-- {
		// 找出最大的儿子节点
		var maxIndex = i * 2 // 假设最大的就是左儿子(因为是父节点,必定存在左儿子)
		// 如果有右儿子, 并且右儿子更大,则记录
		if (maxIndex+1) < dataLen && b.data[maxIndex+1] > b.data[maxIndex] {
			maxIndex = i*2 + 1
		}
		// 与父节点比较, 如果更大就交换
		for b.data[maxIndex] > b.data[i] {
			b.data[maxIndex], b.data[i] = b.data[i], b.data[maxIndex]
		}
	}
}

// BuildMin : 构建小根堆
func (b *BinaryHeap) BuildMin(dataLen int) {
	// 循环所有的父节点(从后向前循环)
	for i := (dataLen - 1) / 2; i >= 1; i-- {
		// 找出最大的儿子节点
		var minIndex = i * 2 // 假设最大的就是左儿子(因为是父节点,必定存在左儿子)
		// 如果有右儿子, 并且右儿子更大,则记录
		if (minIndex+1) < dataLen && b.data[minIndex+1] < b.data[minIndex] {
			minIndex++
		}
		// 与父节点比较, 如果更小就交换
		for b.data[minIndex] < b.data[i] {
			b.data[minIndex], b.data[i] = b.data[i], b.data[minIndex]
		}
	}
}

// SortRise : 对堆做升序排列
// 1. 组合大顶堆
// 2. 根节点与最后一个叶子节点互换
// 3. 在除最后一个叶子节点的堆中继续执行1和2步骤, 到堆中剩余1个节点为止
func (b *BinaryHeap) SortAsc() {
	var dataLen = len(b.data)
	for dataLen > 2 {
		b.BuildMax(dataLen)

		b.data[1], b.data[dataLen-1] = b.data[dataLen-1], b.data[1]

		dataLen--
	}
}

// SortRise : 对堆做降序排列
func (b *BinaryHeap) SortDesc() {
	var dataLen = len(b.data)
	for dataLen > 2 {
		b.BuildMin(dataLen)

		b.data[1], b.data[dataLen-1] = b.data[dataLen-1], b.data[1]

		dataLen--
	}
}

func (b *BinaryHeap) Show() {
	for k, item := range b.data {
		if k > 0 {
			fmt.Printf("%v,", item)
		}
	}
	fmt.Println("")
}
func main() {

	var data = &BinaryHeap{data: []int{6, 9, 2, 22, 44, 8, 12}}

	data.Show()
	data.Add(88)
	data.AddSlice([]int{3, 28})
	data.Show()

	fmt.Println("\n----------max")
	data.BuildMax(data.Length())
	data.Show()

	fmt.Println("\n----------min")
	data.BuildMin(data.Length())
	data.Show()

	fmt.Println("\n----------asc")
	data.SortAsc()
	data.Show()

	fmt.Println("\n----------desc")
	data.SortDesc()
	data.Show()
}

7.集合

package main

import (
	"bytes"
	"fmt"
)

type HashSet struct {
	m map[interface{}]bool
}

func NewHashSet() *HashSet {
	return &HashSet{m: make(map[interface{}]bool)}
}

func (self *HashSet) Add(e interface{}) bool {
	if self.m[e] {
		return false
	}
	self.m[e] = true
	return true
}

func (self *HashSet) Remove(e interface{}) bool {
	delete(self.m, e)
	return true
}

func (self *HashSet) Clear() bool {
	self.m = make(map[interface{}]bool)
	return true
}

func (self *HashSet) Contains(e interface{}) bool {
	return self.m[e]
}

func (self *HashSet) Len() int {
	return len(self.m)
}

func (self *HashSet) Same(other *HashSet) bool {
	if other == nil {
		return false
	}

	if self.Len() != other.Len() {
		return false
	}

	for k, _ := range other.m {
		if !self.Contains(k) {
			return false
		}
	}
	return true
}

func (self *HashSet) Elements() interface{} {
	// for k := range self.m{
	//    snapshot = snapshot(snapshot, k)
	// }
	initialLen := self.Len()
	actualLen := 0
	snapshot := make([]interface{}, initialLen)
	for k := range self.m {
		if actualLen < initialLen {
			snapshot[actualLen] = k
		} else {
			snapshot = append(snapshot, k)
		}
		actualLen++
	}
	if actualLen < initialLen {
		snapshot = snapshot[:actualLen]
	}
	return snapshot
}

func (self *HashSet) String() string {
	var buf bytes.Buffer
	buf.WriteString("Set{")
	flag := true
	for k := range self.m {
		if flag {
			flag = false
		} else {
			buf.WriteString(" ")
		}
		buf.WriteString(fmt.Sprintf("%v", k))
	}
	buf.WriteString("}")

	return buf.String()
}

func (self *HashSet) IsSuperSet(other *HashSet) bool {
	if other == nil {
		return false
	}
	selfLen := self.Len()
	otherLen := other.Len()
	if otherLen == 0 || selfLen == otherLen {
		return false
	}
	if selfLen > 0 && otherLen == 0 {
		return true
	}
	for v := range other.m {
		if !self.Contains(v) {
			return false
		}
	}
	return true
}

//属于A或属于B的元素
func (self *HashSet) Union(other *HashSet) *HashSet {
	// if other == nil || other.Len() == 0{
	//    return self
	// }
	//
	// for v := range other.m{
	//    self.Add(v)
	// }
	// return self
	//不能改变集合A的范围
	union := NewHashSet()
	for v := range self.m {
		union.Add(v)
	}
	for v := range other.m {
		union.Add(v)
	}
	return union
}

//属于A且属于B的元素
func (self *HashSet) Intersect(other *HashSet) *HashSet {
	if other == nil || other.Len() == 0 {
		return NewHashSet()
	}
	intsSet := NewHashSet()
	for v, _ := range other.m {
		if self.Contains(v) {
			intsSet.Add(v)
		}
	}
	return intsSet
}

//属于A且不属于B的元素
func (self *HashSet) Difference(other *HashSet) *HashSet {
	diffSet := NewHashSet()
	if other == nil || other.Len() == 0 {
		diffSet.Union(self)
	} else {
		for v := range self.m {
			if !other.Contains(v) {
				diffSet.Add(v)
			}
		}
	}

	return diffSet
}

//集合A与集合B中所有不属于A∩B的元素的集合
func (self *HashSet) SymmetricDifference(other *HashSet) *HashSet {
	//此时A∩B=∅，A中所有元素均不属于空集
	// if other == nil || other.Len() == 0{
	//    return self
	// }
	// ints := self.Intersect(other)
	// //此时A∩B=∅，A为空或B为空,B为空前面已经判断，此时B不能为空，即A为空
	// if ints == nil || ints.Len() == 0 {
	//    return other
	// }
	//
	// unionSet := self.Union(other)
	// result := NewHashSet()
	// for v := range unionSet.m{
	//    if !ints.Contains(v){
	//       result.Add(v)
	//    }
	// }
	ints := self.Difference(other)
	union := self.Union(other)
	return union.Difference(ints)
}

func main() {
	set1 := NewHashSet()
	set1.Add(1)
	set1.Add("e2")
	set1.Add(3)
	set1.Add("e4")
	fmt.Println("set1:", set1)
	fmt.Printf("set1 Elements:%v\n", set1.Elements())

	set2 := NewHashSet()
	set2.Add(3)
	set2.Add("e2")
	set2.Add(5)
	set2.Add("e6")

	fmt.Println("set2:", set1)
	fmt.Printf("set1 union set2:%v\n", set1.Union(set2))
	fmt.Printf("set1 intersect set2:%v\n", set1.Intersect(set2))
	fmt.Println(set1, set2)
	fmt.Printf("set1 difference set2:%v\n", set1.Difference(set2))
	fmt.Printf("set1 SymmetricDifference set2:%v\n", set1.SymmetricDifference(set2))
	set1.Clear()
	fmt.Println(set1)
}

8.列表

package main

import (
	"errors"
	"fmt"
)

var ListLength  =10  //定义列表全局长度

//interface  实例化int，int., string ,string
type  List interface {
	Size() int  //函数大小，返回大小
	Get(index int)(interface{},error) //根据索引抓取数据
	Set(index int,newval interface{})error //设置
	Insert(index int,newval interface{})error //插入
	Append(newval interface{}) error//追加
	Remove(index int)error   //删除
	Clear() //清空
	String() string //返回字符串
}

// 结构体
type ArrayList struct{
	dataStore []  interface{}
	theSize  int
}
// 创建新的链表
func  New() *ArrayList{
	list:=new(ArrayList)
	list.dataStore = make([]interface{},0,ListLength) //分配内存10个数组元素

	list.theSize=0  //0
	//fmt.Println("new",list.theSize,cap(list.dataStore))
	return list
}

// 获取链表长度
func (list *ArrayList) Size() int{
	return list.theSize  //返回大小

}

// 追加数据
func(list *ArrayList)  Append (newval  interface{}){

	list.dataStore=append(list.dataStore,newval) //数据叠加
	list.theSize++ //索引移动
}
// 获取索引所在数据
func (list *ArrayList)  Get(index int)(interface{},error){
	if index <0 || index >=list.theSize{
		return nil,errors.New("索引越界")
	}
	return list.dataStore[index],nil
}

// 根据索引更改数据
func (list *ArrayList)  Set(index int,newval interface{})(error){
	if index <0 || index >=list.theSize{
		return errors.New("索引越界")
	}
	list.dataStore[index]=newval //赋值新的值
	return nil
}
// 检查切片是否已满
func (list *ArrayList ) checkmemisfull(){
	if list.Size()==cap(list.dataStore){
		newDataStore:=make([]interface{},0,2*list.Size())//开辟更大内存
		copy(newDataStore,list.dataStore) //拷贝
		list.dataStore=newDataStore //赋值
	}
}

// 插入数据
func (list *ArrayList )Insert(index int,newval interface{})error {
	if index <0 || index >=list.theSize{
		return errors.New("索引越界")
	}
	list.checkmemisfull()
	list.dataStore=list.dataStore[:list.Size()+1]//开辟内存,延展使用的内存
	for i:=list.Size();i>index;i--{
		list.dataStore[i]=list.dataStore[i-1] //从后往前赋值
	}
	list.dataStore[index]=newval  //插入数据
	list.theSize++ //索引加1

	return nil
}
// 根据索引移出数据
func (list *ArrayList )Remove(index int)error {
	if index <0 || index >=list.theSize{
		return errors.New("索引越界")
	}

	list.dataStore=append(list.dataStore[:index],list.dataStore[index+1:]...) //删除
	list.theSize--
	return  nil
}
// 清空数据
func (list *ArrayList )Clear() {
	list.dataStore=make([]interface{},0,10) //清空
	list.theSize=0
}
// 返回字符串
func (list *ArrayList ) String() string {
	return  fmt.Sprint(list.dataStore)
}

func main(){
	list :=New()
	for i:=0;i<10 ;i++  {
		list.Append(i)
	}
	fmt.Printf("列表长度：%d\n输出列表\n%d\n",list.theSize,list.dataStore)

	list.Remove(3)
	fmt.Println("输出列表")
	fmt.Println(list.dataStore)


	list.Insert(3,100)
	fmt.Println("输出列表")
	fmt.Println(list.dataStore)

	fmt.Println("输出列表")
	fmt.Println(list.String())
}

迭代器

package main

import (
	"errors"
)

//迭代器
type Iterator interface {
	HasNext() bool//判断是否有下一个
	Next()(interface{},error) //获取下一个
	Remove()//删除
	getindex()int
}
type Iterable interface {
	Iterator () Iterator //构造迭代器
}
type ArrayListIterator struct{
	list * ArrayList  //数组指针
	currentindex  int //当前的索引
}
func (list * ArrayList ) Iterator() Iterator{
	iterator:=new(ArrayListIterator) //创造迭代器
	iterator.currentindex=0
	iterator.list=list //指针传递
	return iterator  //返回迭代器，驾驭数组
}

func  (it *ArrayListIterator)getindex() int {
	return it.currentindex
}

func  (it *ArrayListIterator)HasNext() bool{
	return it.currentindex <it.list.Size()  //存在下一个
}
func  (it *ArrayListIterator)Next()(interface{},error){
	if !it.HasNext(){
		return nil,errors.New("没有数据")
	}
	value,err:=it.list.Get(it.currentindex)//提取上一个
	it.currentindex++
	return value,err
}
func  (it *ArrayListIterator)	Remove(){
	it.currentindex--
	it.list.Remove(it.currentindex) //删除
}

func main() {
	list :=New()
	list.Append(1)
	fmt.Println(list)
	list.Append(2)
	fmt.Println(list)
	list.Append(3)
	fmt.Println(list)
	list.Append(4)
	fmt.Println(list)
	for it:=list.Iterator();it.HasNext();{
		item,_:=it.Next()
		if item==3{
			it.Remove()
		}
		fmt.Println(item)
	}
	fmt.Println(list)
}

9.哈希表

package main

import "fmt"

// hash 表, key, v 组成
type Key interface {

}

type Value interface {

}

// 生成一个hash表
type HashTable struct {
	Items map[int] Value
}

// 给hash表中添加元素
func (ht *HashTable) Put(key Key, value Value)  {
	index := customeHash(key)
	if ht.Items == nil{
		ht.Items = make(map[int]Value)
	}
	ht.Items[index] = value
}

func customeHash(k Key) int  {
	// 自定义hash算法
	key := fmt.Sprintf("%s", k)
	h := 0
	for i:=0; i<len(key); i++{
		h = 31 * h + int(key[i])
	}
	return h
}

func (ht *HashTable) Get(key Key) Value  {
	index := customeHash(key)
	return ht.Items[index]
}

func (ht *HashTable) Remove(key Key)  {
	index := customeHash(key)
	delete(ht.Items, index)
}

func (ht *HashTable) Size() int  {
	return len(ht.Items)
}

func (ht *HashTable)String() {
	// map遍历无序
	for k,v := range ht.Items {
		fmt.Println(fmt.Sprintf("k: %v\tv: %v",k,v))
	}
}

func populateHashTable(count int, start int) *HashTable {
	dict := HashTable{}
	for i := start; i < (start + count); i++ {
		dict.Put(fmt.Sprintf("key%d", i), fmt.Sprintf("value%d", i))
	}
	return &dict
}

func main() {
	dict := populateHashTable(3, 0)
	size := dict.Size()
	fmt.Println(fmt.Sprintf("Test failed, expected 3 and got %d", size))
	dict.String()
}

9.树

9.1 二叉树

package main

import "fmt"

type BinaryTreeNode struct {
	Data  interface{}     //数据
	Left  *BinaryTreeNode //左子树
	Right *BinaryTreeNode //右子树
}

func NewTree(data interface{}) *BinaryTreeNode {
	return &BinaryTreeNode{
		Data: data,
	}
}

func CreateNode(data interface{}) *BinaryTreeNode {
	return &BinaryTreeNode{
		Data: data,
	}
}

func (tree *BinaryTreeNode) String() string {
	return fmt.Sprintf(" %v", tree.Data)
}

//前序遍历:以当前节点为根节点，根——>左——>右
func (tree *BinaryTreeNode) PreTraverseRecursion(print bool) (treeString string) {

	if tree == nil {
		return
	}

	treeString += tree.String()

	if tree.Left != nil {
		treeString += tree.Left.PreTraverseRecursion(false)
	}

	if tree.Right != nil {
		treeString += tree.Right.PreTraverseRecursion(false)
	}

	if print {
		fmt.Println(fmt.Sprintf("前序遍历:[%v]", treeString))
	}

	return
}

//中序遍历:以当前节点为根节点，左——>根——>右
func (tree *BinaryTreeNode) MidTraverseRecursion(print bool) (treeString string) {
	if tree == nil {
		return
	}

	if tree.Left != nil {
		treeString += tree.Left.MidTraverseRecursion(false)
	}

	treeString += tree.String()

	if tree.Right != nil {
		treeString += tree.Right.MidTraverseRecursion(false)
	}
	if print {
		fmt.Println(fmt.Sprintf("中序遍历:[%v]", treeString))
	}

	return
}

//后续遍历：以当前节点为根节点，左——>右——>根
func (tree *BinaryTreeNode) PostTraverseRecursion(print bool) (treeString string) {
	if tree == nil {
		return
	}
	if tree.Left != nil {
		treeString += tree.Left.PostTraverseRecursion(false)
	}
	if tree.Right != nil {
		treeString += tree.Right.PostTraverseRecursion(false)
	}
	treeString += tree.String()
	if print {
		fmt.Println(fmt.Sprintf("后序遍历:[%v]", treeString))
	}
	return
}

//层次遍历(广度优先遍历)
func (tree *BinaryTreeNode) BreadthFirstSearch(print bool) {
	if tree == nil {
		return
	}
	var result []interface{}
	nodes := []*BinaryTreeNode{tree}
	for len(nodes) > 0 {
		curNode := nodes[0]
		nodes = nodes[1:]
		result = append(result, curNode.Data)
		if curNode.Left != nil {
			nodes = append(nodes, curNode.Left)
		}
		if curNode.Right != nil {
			nodes = append(nodes, curNode.Right)
		}
	}

	if print {
		fmt.Print(fmt.Sprintf("层次遍历:["))
		for _, v := range result {
			fmt.Print(" ")
			fmt.Print(v)
		}
		fmt.Println("]")
	}

}

//层数(递归实现)
//对任意一个子树的根节点来说，它的深度=左右子树深度的最大值+1
func (tree *BinaryTreeNode) Layers() int {
	if tree == nil {
		return 0
	}
	leftLayers := tree.Left.Layers()
	rightLayers := tree.Right.Layers()
	if leftLayers > rightLayers {
		return leftLayers + 1
	} else {
		return rightLayers + 1
	}
}

//层数(非递归实现)
//借助队列，在进行按层遍历时，记录遍历的层数即可
func (tree *BinaryTreeNode) LayersByQueue() int {
	if tree == nil {
		return 0
	}
	layers := 0
	nodes := []*BinaryTreeNode{tree}
	for len(nodes) > 0 {
		layers++
		size := len(nodes) //每层的节点数
		count := 0
		for count < size {
			count++
			curNode := nodes[0]
			nodes = nodes[1:]
			if curNode.Left != nil {
				nodes = append(nodes, curNode.Left)
			}
			if curNode.Right != nil {
				nodes = append(nodes, curNode.Right)
			}
		}
	}
	return layers
}

func main() {
	tree := NewTree(3)
	tree.Left = CreateNode(0)
	tree.Left.Right = CreateNode(2)
	tree.Right = CreateNode(5)
	tree.Right.Left = CreateNode(4)

	// 前序
	tree.PreTraverseRecursion(true)
	// 中序
	tree.MidTraverseRecursion(true)
	// 后续
	tree.PostTraverseRecursion(true)
	//
	tree.BreadthFirstSearch(true)

	fmt.Println("层数: ", tree.Layers())
	fmt.Println("层数: ", tree.LayersByQueue())
}

9.2 二分搜索树

package main
import (
	"fmt"
	"strings"
)

type Node struct {
	E int
	Left *Node
	Right *Node
}

// 约定在此样例代码中我们的二分搜索树中没有重复元素
// 如果想包涵重复元素的话，只需要以下定义：
// 左子树小于等于此节点，或右子树大于等于节点
type Tree struct {
	root *Node
	size int
}

func (t Tree) Size() int {
	return t.size
}

func (t Tree) Root() *Node {
	return t.root
}
// 判断二叉树是否为空
func (this *Tree) IsEmpty() bool {
	if this.size == 0 {
		return true
	}
	return false
}

func InitNode(E int) *Node {
	return &Node{
		E:E,
		Left:nil,
		Right:nil,
	}
}

func (this *Tree) AddE(e int) {
	this.root = this.add(this.root,e)
}

// 向以node为根的二分搜索树中插入元素E，递归算法
func (this *Tree) add(node *Node,e int) *Node{
	// 不管是递归还是回溯，首先我们都应该先写出递归的结束条件是什么
	if node == nil {
		this.size++
		return InitNode(e)
	}

	if e > node.E {
		node.Right = this.add(node.Right, e)
	} else if e < node.E {
		node.Left = this.add(node.Left, e)
	}
	return node
}

// 查找二分搜索中是否含有元素E
func (this *Tree)Contains(e int) bool {
	return this.contains(this.root, e)
}

// 递归的方式查找元素是否存在
func (this *Tree)contains (node *Node, e int) bool {
	if node == nil {
		return false
	}
	if e == node.E {
		return true
	} else if e > node.E {
		return this.contains(node.Right,e)
	} else {
		return this.contains(node.Left, e)
	}
}

// 遍历算法
// 1.前序遍历
func(this *Tree)PreOrder(){
	PreOrder(this.root)
	fmt.Println()
}

func PreOrder(node *Node)  {
	if node == nil {
		return
	}
	fmt.Printf("%d ",node.E)
	PreOrder(node.Left)
	PreOrder(node.Right)
}

// 非递归的前序遍历
func (this *Tree) PreOrderNR() {
	stack := make([]*Node, 0)
	stack = append(stack, this.root)
	for len(stack) > 0 {
		curNode := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		fmt.Printf("%d ",curNode.E)
		if curNode.Right != nil {
			stack = append(stack, curNode.Right)
		}
		if curNode.Left != nil {
			stack = append(stack, curNode.Left)
		}
	}
	fmt.Println()
}

// 2.中序遍历
func(this *Tree)MidOrder(){
	MidOrder(this.root)
	fmt.Println()
}

func MidOrder(node *Node)  {
	if node == nil {
		return
	}
	MidOrder(node.Left)
	fmt.Printf("%d ",node.E)
	MidOrder(node.Right)
}

// 3.后序遍历
func (this *Tree) BackOrder(){
	BackOrder(this.root)
	println()
}

func BackOrder(node *Node)  {
	if node == nil {
		return
	}
	BackOrder(node.Left)
	BackOrder(node.Right)
	fmt.Printf("%d ",node.E)
}
// 二分搜索树的层序遍历
func (this *Tree)LevelOrder(){
	queue := make([]*Node,0)
	queue = append(queue, this.root)
	for len(queue) > 0 {
		curNode := queue[0]
		queue = queue[1:]
		fmt.Printf("%d ",curNode.E)
		if curNode.Left != nil {
			queue = append(queue,curNode.Left)
		}
		if curNode.Right != nil {
			queue = append(queue,curNode.Right)
		}
	}
}
// 二分搜索树中搜索最小值
func (this *Tree) FindMin() int{
	if this.IsEmpty() {
		panic("二叉树为空，无法删除任何节点")
	}
	return minimum(this.root).E
}
func minimum(node *Node) *Node {
	if node.Left == nil {
		return node
	}
	return minimum(node.Left)
}
// 二分搜索树中搜索最大值
func (this *Tree) FindMax() int{
	if this.IsEmpty() {
		panic("二叉树为空，无法删除任何节点")
	}
	return maximum(this.root).E
}
func maximum(node *Node) *Node {
	if node.Right == nil {
		return node
}
return maximum(node.Right)
}
// 从二分搜索树中删除最小值
func (this *Tree) DelMin() int {
	var ret int = this.FindMin()
	this.root = this.rmMin(this.root)
	return ret
}
// 删除掉以node为根的二分搜索树的最小节点
// 返回删除节点后新的二分搜索树的根
func (this *Tree) rmMin(node *Node) *Node {
	if node.Left == nil {
		nodeRight := node.Right
		node.Right = nil
		this.size--
		return nodeRight
	}
	node.Left = this.rmMin(node.Left)
	return node
}
// 从二分搜索树种删除最大值
func (this *Tree) DelMax() int {
	var ret int = this.FindMax()
	this.root = this.rmMax(this.root)
	return ret
}
// 删除掉以node为根的二分搜索树的最小节点
// 返回删除节点后新的二分搜索树的根
func (this *Tree) rmMax(node *Node) *Node {
	if node.Right == nil {
		nodeLeft := node.Left
		node.Left = nil
		this.size--
		return nodeLeft
	}
	node.Right = this.rmMax(node.Right)
	return node
}
// 在二分搜索树中删除值为e的方法
func (this *Tree) Remove (e int){
	this.root = this.remove(this.root,e)
}
func (this *Tree) remove(node *Node,e int) *Node {
	if node == nil {
		return nil
	}
	if e > node.E {
		node.Right = this.remove(node.Right,e)
		return node
	} else if e < node.E {
		node.Left = this.remove(node.Left,e)
		return node
	} else {
		// 如果左子树为空的时候
		if node.Left == nil {
			nodeRight := node.Right
			node.Right = nil
			this.size--
			return nodeRight
		}
		// 如果右子树为空
		if node.Right == nil {
			nodeLeft := node.Left
			node.Left = nil
			this.size--
			return nodeLeft
		}
		// 如果左右子树都不为空，那么我们需要找到node的后继
		// 就是所有比node值大的节点中值最小的那个，显然它在node的右子树中
		nodeNext := minimum(node.Right)
		nodeNext.Right = this.rmMin(node.Right)
		nodeNext.Left = node.Left
		node.Left = nil
		node.Right = nil
		return nodeNext
	}
}

// 二叉树的打印方法
func (this *Tree) String() string{
	var (
		builder strings.Builder
	)
	generateBSTString(this.root,0,&builder)
	return builder.String()
}

func generateBSTString(node *Node,depth int,builder *strings.Builder){
	if node == nil {
		fmt.Fprintln(builder,generateDepthString(depth) + "null")
		return
	}
	fmt.Fprintln(builder,generateDepthString(depth),node.E)
	generateBSTString(node.Left,depth+1,builder)
	generateBSTString(node.Right,depth+1,builder)
}
func generateDepthString(depth int) string{
	var builder strings.Builder
	for i:=0;i<depth;i++ {
		fmt.Fprintf(&builder,"--")
	}
	return builder.String()
}

func main()  {
	tree := Tree{}
	tree.AddE(3)
	tree.Root().Left = InitNode(0)
	tree.Root().Left.Right = InitNode(2)
	tree.Root().Right = InitNode(5)
	tree.Root().Right.Left = InitNode(4)

	fmt.Println(tree.String())

	tree.PreOrder()
	tree.MidOrder()
	tree.BackOrder()

}

9.3 红黑树

红黑树（Red Black Tree）是一种自平衡二叉查找树。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

// Copyright 2015, Hu Keping . All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package rbtree implements operations on Red-Black tree.
package main

import "fmt"

//
// Red-Black tree properties:  http://en.wikipedia.org/wiki/Rbtree
//
//  1) A node is either red or black
//  2) The root is black
//  3) All leaves (NULL) are black
//  4) Both children of every red node are black
//  5) Every simple path from root to leaves contains the same number
//     of black nodes.
//
type Node struct {
	Left   *Node
	Right  *Node
	Parent *Node
	Color  uint

	// for use by client.
	Item
}

const (
	RED   = 0
	BLACK = 1
)

type Item interface {
	Less(than Item) bool
}

// Rbtree represents a Red-Black tree.
type Rbtree struct {
	NIL   *Node
	root  *Node
	count uint
}

func less(x, y Item) bool {
	return x.Less(y)
}

// New returns an initialized Red-Black tree
func New() *Rbtree { return new(Rbtree).Init() }

func (t *Rbtree) Init() *Rbtree {
	node := &Node{nil, nil, nil, BLACK, nil}
	return &Rbtree{
		NIL:   node,
		root:  node,
		count: 0,
	}
}

func (t *Rbtree) leftRotate(x *Node) {
	// Since we are doing the left rotation, the right child should *NOT* nil.
	if x.Right == t.NIL {
		return
	}

	//
	// The illation of left rotation
	//
	//          |                                  |
	//          X                                  Y
	//         / \         left rotate            / \
	//        α  Y       ------------->         X   γ
	//           / \                            / \
	//          β  γ                         α  β
	//
	// It should be note that during the rotating we do not change
	// the Nodes' color.
	//
	y := x.Right
	x.Right = y.Left
	if y.Left != t.NIL {
		y.Left.Parent = x
	}
	y.Parent = x.Parent

	if x.Parent == t.NIL {
		t.root = y
	} else if x == x.Parent.Left {
		x.Parent.Left = y
	} else {
		x.Parent.Right = y
	}

	y.Left = x
	x.Parent = y
}

func (t *Rbtree) rightRotate(x *Node) {
	// Since we are doing the right rotation, the left child should *NOT* nil.
	if x.Left == t.NIL {
		return
	}

	//
	// The illation of right rotation
	//
	//          |                                  |
	//          X                                  Y
	//         / \         right rotate           / \
	//        Y   γ      ------------->         α  X
	//       / \                                    / \
	//      α  β                                 β  γ
	//
	// It should be note that during the rotating we do not change
	// the Nodes' color.
	//
	y := x.Left
	x.Left = y.Right
	if y.Right != t.NIL {
		y.Right.Parent = x
	}
	y.Parent = x.Parent

	if x.Parent == t.NIL {
		t.root = y
	} else if x == x.Parent.Left {
		x.Parent.Left = y
	} else {
		x.Parent.Right = y
	}

	y.Right = x
	x.Parent = y
}

func (t *Rbtree) insert(z *Node) *Node {
	x := t.root
	y := t.NIL

	for x != t.NIL {
		y = x
		if less(z.Item, x.Item) {
			x = x.Left
		} else if less(x.Item, z.Item) {
			x = x.Right
		} else {
			return x
		}
	}

	z.Parent = y
	if y == t.NIL {
		t.root = z
	} else if less(z.Item, y.Item) {
		y.Left = z
	} else {
		y.Right = z
	}

	t.count++
	t.insertFixup(z)
	return z
}

func (t *Rbtree) insertFixup(z *Node) {
	for z.Parent.Color == RED {
		//
		// Howerver, we do not need the assertion of non-nil grandparent
		// because
		//
		//  2) The root is black
		//
		// Since the color of the parent is RED, so the parent is not root
		// and the grandparent must be exist.
		//
		if z.Parent == z.Parent.Parent.Left {
			// Take y as the uncle, although it can be NIL, in that case
			// its color is BLACK
			y := z.Parent.Parent.Right
			if y.Color == RED {
				//
				// Case 1:
				// Parent and uncle are both RED, the grandparent must be BLACK
				// due to
				//
				//  4) Both children of every red node are black
				//
				// Since the current node and its parent are all RED, we still
				// in violation of 4), So repaint both the parent and the uncle
				// to BLACK and grandparent to RED(to maintain 5)
				//
				//  5) Every simple path from root to leaves contains the same
				//     number of black nodes.
				//
				z.Parent.Color = BLACK
				y.Color = BLACK
				z.Parent.Parent.Color = RED
				z = z.Parent.Parent
			} else {
				if z == z.Parent.Right {
					//
					// Case 2:
					// Parent is RED and uncle is BLACK and the current node
					// is right child
					//
					// A left rotation on the parent of the current node will
					// switch the roles of each other. This still leaves us in
					// violation of 4).
					// The continuation into Case 3 will fix that.
					//
					z = z.Parent
					t.leftRotate(z)
				}
				//
				// Case 3:
				// Parent is RED and uncle is BLACK and the current node is
				// left child
				//
				// At the very beginning of Case 3, current node and parent are
				// both RED, thus we violate 4).
				// Repaint parent to BLACK will fix it, but 5) does not allow
				// this because all paths that go through the parent will get
				// 1 more black node. Then repaint grandparent to RED (as we
				// discussed before, the grandparent is BLACK) and do a right
				// rotation will fix that.
				//
				z.Parent.Color = BLACK
				z.Parent.Parent.Color = RED
				t.rightRotate(z.Parent.Parent)
			}
		} else { // same as then clause with "right" and "left" exchanged
			y := z.Parent.Parent.Left
			if y.Color == RED {
				z.Parent.Color = BLACK
				y.Color = BLACK
				z.Parent.Parent.Color = RED
				z = z.Parent.Parent
			} else {
				if z == z.Parent.Left {
					z = z.Parent
					t.rightRotate(z)
				}
				z.Parent.Color = BLACK
				z.Parent.Parent.Color = RED
				t.leftRotate(z.Parent.Parent)
			}
		}
	}
	t.root.Color = BLACK
}

// Just traverse the node from root to left recursively until left is NIL.
// The node whose left is NIL is the node with minimum value.
func (t *Rbtree) min(x *Node) *Node {
	if x == t.NIL {
		return t.NIL
	}

	for x.Left != t.NIL {
		x = x.Left
	}

	return x
}

// Just traverse the node from root to right recursively until right is NIL.
// The node whose right is NIL is the node with maximum value.
func (t *Rbtree) max(x *Node) *Node {
	if x == t.NIL {
		return t.NIL
	}

	for x.Right != t.NIL {
		x = x.Right
	}

	return x
}

func (t *Rbtree) search(x *Node) *Node {
	p := t.root

	for p != t.NIL {
		if less(p.Item, x.Item) {
			p = p.Right
		} else if less(x.Item, p.Item) {
			p = p.Left
		} else {
			break
		}
	}

	return p
}

//TODO: Need Document
func (t *Rbtree) successor(x *Node) *Node {
	if x == t.NIL {
		return t.NIL
	}

	// Get the minimum from the right sub-tree if it existed.
	if x.Right != t.NIL {
		return t.min(x.Right)
	}

	y := x.Parent
	for y != t.NIL && x == y.Right {
		x = y
		y = y.Parent
	}
	return y
}

//TODO: Need Document
func (t *Rbtree) delete(key *Node) *Node {
	z := t.search(key)

	if z == t.NIL {
		return t.NIL
	}
	ret := &Node{t.NIL, t.NIL, t.NIL, z.Color, z.Item}

	var y *Node
	var x *Node

	if z.Left == t.NIL || z.Right == t.NIL {
		y = z
	} else {
		y = t.successor(z)
	}

	if y.Left != t.NIL {
		x = y.Left
	} else {
		x = y.Right
	}

	// Even if x is NIL, we do the assign. In that case all the NIL nodes will
	// change from {nil, nil, nil, BLACK, nil} to {nil, nil, ADDR, BLACK, nil},
	// but do not worry about that because it will not affect the compare
	// between Node-X with Node-NIL
	x.Parent = y.Parent

	if y.Parent == t.NIL {
		t.root = x
	} else if y == y.Parent.Left {
		y.Parent.Left = x
	} else {
		y.Parent.Right = x
	}

	if y != z {
		z.Item = y.Item
	}

	if y.Color == BLACK {
		t.deleteFixup(x)
	}

	t.count--

	return ret
}

func (t *Rbtree) deleteFixup(x *Node) {
	for x != t.root && x.Color == BLACK {
		if x == x.Parent.Left {
			w := x.Parent.Right
			if w.Color == RED {
				w.Color = BLACK
				x.Parent.Color = RED
				t.leftRotate(x.Parent)
				w = x.Parent.Right
			}
			if w.Left.Color == BLACK && w.Right.Color == BLACK {
				w.Color = RED
				x = x.Parent
			} else {
				if w.Right.Color == BLACK {
					w.Left.Color = BLACK
					w.Color = RED
					t.rightRotate(w)
					w = x.Parent.Right
				}
				w.Color = x.Parent.Color
				x.Parent.Color = BLACK
				w.Right.Color = BLACK
				t.leftRotate(x.Parent)
				// this is to exit while loop
				x = t.root
			}
		} else { // the code below is has left and right switched from above
			w := x.Parent.Left
			if w.Color == RED {
				w.Color = BLACK
				x.Parent.Color = RED
				t.rightRotate(x.Parent)
				w = x.Parent.Left
			}
			if w.Left.Color == BLACK && w.Right.Color == BLACK {
				w.Color = RED
				x = x.Parent
			} else {
				if w.Left.Color == BLACK {
					w.Right.Color = BLACK
					w.Color = RED
					t.leftRotate(w)
					w = x.Parent.Left
				}
				w.Color = x.Parent.Color
				x.Parent.Color = BLACK
				w.Left.Color = BLACK
				t.rightRotate(x.Parent)
				x = t.root
			}
		}
	}
	x.Color = BLACK
}

// This file contains most of the methods that can be used
// by the user. Anyone who wants to look for some API about
// the rbtree, this is the right place.

// Number of nodes in the tree.
func (t *Rbtree) Len() uint { return t.count }

func (t *Rbtree) Insert(item Item) {
	if item == nil {
		return
	}

	// Always insert a RED node
	t.insert(&Node{t.NIL, t.NIL, t.NIL, RED, item})
}

//InsertOrGet inserts or retrieves the item in the tree. If the
//item is already in the tree then the return value will be that.
//If the item is not in the tree the return value will be the item
//you put in.
func (t *Rbtree) InsertOrGet(item Item) Item {
	if item == nil {
		return nil
	}

	return t.insert(&Node{t.NIL, t.NIL, t.NIL, RED, item}).Item
}

func (t *Rbtree) Delete(item Item) Item {
	if item == nil {
		return nil
	}

	// The `color` field here is nobody
	return t.delete(&Node{t.NIL, t.NIL, t.NIL, RED, item}).Item
}

func (t *Rbtree) Get(item Item) Item {
	if item == nil {
		return nil
	}

	// The `color` field here is nobody
	ret := t.search(&Node{t.NIL, t.NIL, t.NIL, RED, item})
	if ret == nil {
		return nil
	}

	return ret.Item
}

//TODO: This is for debug, delete it in the future
func (t *Rbtree) Search(item Item) *Node {

	return t.search(&Node{t.NIL, t.NIL, t.NIL, RED, item})
}

func (t *Rbtree) Min() Item {
	x := t.min(t.root)

	if x == t.NIL {
		return nil
	}

	return x.Item
}

func (t *Rbtree) Max() Item {
	x := t.max(t.root)

	if x == t.NIL {
		return nil
	}

	return x.Item
}
type Iterator func(i Item) bool

// Ascend will call iterator once for each element greater or equal than pivot
// in ascending order. It will stop whenever the iterator returns false.
func (t *Rbtree) Ascend(pivot Item, iterator Iterator) {
	t.ascend(t.root, pivot, iterator)
}

func (t *Rbtree) ascend(x *Node, pivot Item, iterator Iterator) bool {
	if x == t.NIL {
		return true
	}

	if !less(x.Item, pivot) {
		if !t.ascend(x.Left, pivot, iterator) {
			return false
		}
		if !iterator(x.Item) {
			return false
		}
	}

	return t.ascend(x.Right, pivot, iterator)
}

// Descend will call iterator once for each element less or equal than pivot
// in descending order. It will stop whenever the iterator returns false.
func (t *Rbtree) Descend(pivot Item, iterator Iterator) {
	t.descend(t.root, pivot, iterator)
}

func (t *Rbtree) descend(x *Node, pivot Item, iterator Iterator) bool {
	if x == t.NIL {
		return true
	}

	if !less(pivot, x.Item) {
		if !t.descend(x.Right, pivot, iterator) {
			return false
		}
		if !iterator(x.Item) {
			return false
		}
	}

	return t.descend(x.Left, pivot, iterator)
}

// AscendRange will call iterator once for elements greater or equal than @ge
// and less than @lt, which means the range would be [ge, lt).
// It will stop whenever the iterator returns false.
func (t *Rbtree) AscendRange(ge, lt Item, iterator Iterator) {
	t.ascendRange(t.root, ge, lt, iterator)
}

func (t *Rbtree) ascendRange(x *Node, inf, sup Item, iterator Iterator) bool {
	if x == t.NIL {
		return true
	}

	if !less(x.Item, sup) {
		return t.ascendRange(x.Left, inf, sup, iterator)
	}
	if less(x.Item, inf) {
		return t.ascendRange(x.Right, inf, sup, iterator)
	}

	if !t.ascendRange(x.Left, inf, sup, iterator) {
		return false
	}
	if !iterator(x.Item) {
		return false
	}
	return t.ascendRange(x.Right, inf, sup, iterator)
}

type testStruct struct {
	id   int
	text string
}

func (ts *testStruct) Less(than Item) bool {
	return ts.id < than.(*testStruct).id
}

// Int implements the Item interface for integers.
type Int int

// Less returns true if int(a) < int(b).
func (a Int) Less(b Item) bool {
	return a < b.(Int)
}

func main() {
	rbTree := New()
	items := []*testStruct{
		{1, "this"},
		{2, "is"},
		{3, "a"},
		{4, "test"},
	}

	for i := range items {
		rbTree.Insert(items[i])
	}

	rbTree.Descend(items[2], func(i Item) bool {
		fmt.Println(i)
		return true
	})

	newItem := &testStruct{items[0].id, "not"}
	newItem = rbTree.InsertOrGet(newItem).(*testStruct)

	if newItem.text != items[0].text {
		fmt.Println(fmt.Errorf("tree.InsertOrGet = {id: %d, text: %s}, expect {id %d, text %s}", newItem.id, newItem.text, items[0].id, items[0].text))
	}

	newItem = &testStruct{5, "new"}
	newItem = rbTree.InsertOrGet(newItem).(*testStruct)

	if newItem.text != "new" {
		fmt.Println(fmt.Errorf("tree.InsertOrGet = {id: %d, text: %s}, expect {id %d, text %s}", newItem.id, newItem.text, 5, "new"))
	}
}

9.4 Trie字典树

字典树（Trie）是一种很特别的树状信息检索数据结构，如同其名，它的构成就像一本字典，可以让你快速的进行字符插入、字符串搜索等。

字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但它利用了字符串的共同前缀（Common Prefix）作为存储依据，以此来节省存储空间，并加速搜索时间。Trie 的字符串搜索时间复杂度为 **O(m)**，m 为最长的字符串的长度，其查询性能与集合中的字符串的数量无关。其在搜索字符串时表现出的高效，使得特别适用于构建文本搜索和词频统计等应用。

map实现

package main

import (
	"fmt"
)

// 字典树(前缀树)
type trieNode struct {
	isWord bool  // 是否是单词结尾
	next   map[interface{}]*trieNode
}

type trie struct {
	size int  // 节点数量
	root *trieNode
}

func NewTrie() *trie {
	return &trie{
		0,
		&trieNode{false, make(map[interface{}]*trieNode)},
	}
}

func (this *trie) GetSize() int {
	return this.size
}

// 非递归算法
func (this *trie) Add(word string) {
	if len(word) == 0 {
		return
	}

	cur := this.root
	for _, v := range word {
		_, ok := cur.next[v] // 在NewTrie中已经初始化，能直接用
		if !ok {
			cur.next[v] = &trieNode{false, map[interface{}]*trieNode{}}
		}
		cur = cur.next[v]
	}
	// 判断该单词之前是否已经添加到tree中了
	if !cur.isWord {
		cur.isWord = true
		this.size++
	}
}

// 递归算法
func (this *trie) Add2(word string) {
	if len(word) == 0 {
		return
	}
	cur := this.root
	this.size = this.size + cur.insert(word)
}

// 辅助完成递归函数:在node节点中插入word,如果是已经存在的单词,返回0,如果不存在返回1
func (node *trieNode) insert(word string) int {
	_, ok := node.next[rune(word[0])]
	if !ok {
		node.next[rune(word[0])] = &trieNode{false,
			map[interface{}]*trieNode{}}
	}
	node = node.next[rune(word[0])]

	if len(word) == 1 {
		if !node.isWord {
			node.isWord = true
			return 1
		}
		return 0
	}

	return node.insert(word[1:])
}

// 查询是否包含某个单词
func (this *trie) Contains(word string) bool {
	if len(word) == 0 {
		return false
	}

	cur := this.root
	for _, v := range word {
		t1, ok := cur.next[v]
		if !ok {
			return false
		}
		cur = t1
	}
	return cur.isWord
}

// 前缀是否有以prefix为前缀的单词
func (this *trie) IsPrefix(word string) bool {
	if len(word) == 0 {
		return false
	}

	cur := this.root
	for _, v := range word {
		t1, ok := cur.next[v]
		if !ok {
			return false
		}
		cur = t1
	}
	return true
}


func main() {
	trie := NewTrie()
	trie.Add("a傲慢")
	trie.Add("傲慢")
	trie.Add2("ff")
	fmt.Println("一共",trie.GetSize(),"个单词")

	fmt.Println(trie.Contains("a傲慢"))
	fmt.Println(trie.Contains("傲慢"))
	fmt.Println(trie.Contains("ff"))

	fmt.Println(trie.IsPrefix("傲"))
	fmt.Println(trie.IsPrefix("a"))
	fmt.Println(trie.IsPrefix("f"))
}

9.5 线段树

线段树（segment tree），顾名思义，是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。

对应于树状数组，线段树进行更新（update）的操作为O(logn)，进行区间查询（range query）的操作也为O(logn)。

注意：

线段树不是完全二叉树
线段树是平衡二叉树
堆（完全二叉树）也是平衡二叉树
二分搜索树不一定是平衡二叉树

package main
import (
	"errors"
	"fmt"
	"sort"
)

const (
	// Inf is defined as the max value of an integer, used as +∞
	Inf = int(^uint(0) >> 1)
	// NegInf is defined as the min value of an integer, used as -∞
	NegInf = -Inf - 1
)

type interval struct {
	segment
	element interface{}
}

type segment struct {
	from int
	to   int
}

type node struct {
	segment     segment
	left, right *node
	intervals   []*interval
}

type Tree struct {
	base     []interval
	elements map[interface{}]struct{}
	root     *node
}

// Push pushes an interval to the interval stack
func (t *Tree) Push(from, to int, element interface{}) {
	if to < from {
		from, to = to, from
	}
	if t.elements == nil {
		t.elements = make(map[interface{}]struct{})
	}
	t.elements[element] = struct{}{}
	t.base = append(t.base, interval{segment{from, to}, element})
}

// Clear clears the interval stack
func (t *Tree) Clear() {
	t.root = nil
	t.base = nil
}

// BuildTree builds the segment tree from the interval stack
func (t *Tree) BuildTree() error {
	if len(t.base) == 0 {
		return errors.New("No intervals in stack. Push intervals on the stack of the tree first.")
	}

	leaves := elementaryIntervals(t.endpoints())
	t.root = t.insertNodes(leaves)

	for i := range t.base {
		t.root.insertInterval(&t.base[i])
	}

	return nil
}

// Print prints a binary tree recursively to sdout
func (t *Tree) Print() {
	endpoints := len(t.base)*2 + 2
	leaves := endpoints*2 - 3
	height := 1 + log2(leaves)

	fmt.Println("Height:", height, ", leaves:", leaves)
	levels := make([][]*node, height+1)

	traverse(t.root, 0, func(n *node, depth int) {
		levels[depth] = append(levels[depth], n)
	}, nil)

	for i, level := range levels {
		for j, n := range level {
			space(12 * (len(levels) - 1 - i))
			n.print()
			space(1 * (height - i))

			if j-1%2 == 0 {
				space(2)
			}
		}
		fmt.Println()
	}
}
// Removes duplicate entries from a sorted slice
func removedups(sorted []int) (unique []int) {
	unique = make([]int, 0, len(sorted))
	unique = append(unique, sorted[0])
	prev := sorted[0]
	for _, val := range sorted[1:] {
		if val != prev {
			unique = append(unique, val)
			prev = val
		}
	}
	return
}

// Creates a sorted slice of unique endpoints from a tree's base
func (t *Tree) endpoints() []int {
	baseLen := len(t.base)
	endpoints := make([]int, baseLen*2)

	// When there are a lot of intervals, there is a big chance of big overlaps
	// Try to have the endpoints sorted as much as possible when putting them
	// in the slice to reduce the final sort time.
	// endpoints[0] = NegInf
	for i, interval := range t.base {
		endpoints[i] = interval.from
		endpoints[i+baseLen] = interval.to
	}
	// endpoints[baseLen*2+1] = Inf

	sort.Sort(sort.IntSlice(endpoints))

	return removedups(endpoints)
}

// Creates a slice of elementary intervals from a slice of (sorted) endpoints
// Input: [p1, p2, ..., pn]
// Output: [{p1 : p1}, {p1 : p2}, {p2 : p2},... , {pn : pn}
func elementaryIntervals(endpoints []int) []segment {
	if len(endpoints) == 1 {
		return []segment{segment{endpoints[0], endpoints[0]}}
	}

	intervals := make([]segment, len(endpoints)*2-1)

	for i := 0; i < len(endpoints); i++ {
		intervals[i*2] = segment{endpoints[i], endpoints[i]}
		if i < len(endpoints)-1 {
			intervals[i*2+1] = segment{endpoints[i], endpoints[i+1]}
		}
	}
	return intervals
}

// insertNodes builds the tree structure from the elementary intervals
func (t *Tree) insertNodes(leaves []segment) *node {
	var n *node
	if len(leaves) == 1 {
		n = &node{segment: leaves[0]}
		n.left = nil
		n.right = nil
	} else {
		n = &node{segment: segment{leaves[0].from, leaves[len(leaves)-1].to}}
		center := len(leaves) / 2
		n.left = t.insertNodes(leaves[:center])
		n.right = t.insertNodes(leaves[center:])
	}

	return n
}

func (s *segment) subsetOf(other *segment) bool {
	return other.from <= s.from && other.to >= s.to
}

func (s *segment) intersectsWith(other *segment) bool {
	return other.from <= s.to && s.from <= other.to ||
		s.from <= other.to && other.from <= s.to
}

// Inserts interval into given tree structure
func (n *node) insertInterval(i *interval) {
	if n.segment.subsetOf(&i.segment) {
		if n.intervals == nil {
			n.intervals = make([]*interval, 0, 1)
		}
		n.intervals = append(n.intervals, i)
	} else {
		if n.left != nil && n.left.segment.intersectsWith(&i.segment) {
			n.left.insertInterval(i)
		}
		if n.right != nil && n.right.segment.intersectsWith(&i.segment) {
			n.right.insertInterval(i)
		}
	}
}

func (n *node) print() {
	from := fmt.Sprintf("%d", n.segment.from)
	switch n.segment.from {
	case Inf:
		from = "+∞"
	case NegInf:
		from = "-∞"
	}
	to := fmt.Sprintf("%d", n.segment.to)
	switch n.segment.to {
	case Inf:
		to = "Inf"
	case NegInf:
		to = "NegInf"
	}
	fmt.Printf("(%s,%s)", from, to)
	if n.intervals != nil {
		fmt.Print("->[")
		for _, intrvl := range n.intervals {
			fmt.Printf("(%v,%v)=[%v]", intrvl.from, intrvl.to, intrvl.element)
		}
		fmt.Print("]")
	}

}
// QueryIndex looks for all segments in the interval tree that contain
// a given index. The elements associated with the segments will be sent
// on the returned channel. No element will be sent twice.
// The elements will not be sent in any specific order.
func (t *Tree) QueryIndex(index int) (<-chan interface{}, error) {
	if t.root == nil {
		return nil, errors.New("Tree is empty. Build the tree first")
	}

	intervals := make(chan *interval)

	go func(t *Tree, index int, intervals chan *interval) {
		query(t.root, index, intervals)
		close(intervals)
	}(t, index, intervals)

	elements := make(chan interface{})

	go func(intervals chan *interval, elements chan interface{}) {
		defer close(elements)
		results := make(map[interface{}]struct{})
		for interval := range intervals {
			_, alreadyFound := results[interval.element]
			if !alreadyFound {
				// Store an empty struct in the map to minimize memory footprint
				results[interval.element] = struct{}{}
				elements <- interval.element
				if len(results) >= len(t.elements) {
					// found all elements that can be found
					return
				}
			}

		}
	}(intervals, elements)

	return elements, nil
}

func (s segment) contains(index int) bool {
	return s.from <= index && index <= s.to
}

func query(node *node, index int, results chan<- *interval) {
	if node.segment.contains(index) {
		for _, interval := range node.intervals {
			results <- interval
		}
		if node.left != nil {
			query(node.left, index, results)
		}
		if node.right != nil {
			query(node.right, index, results)
		}
	}
}


// Traverse tree recursively call enter when entering node, resp. leave
func traverse(node *node, depth int, enter, leave func(*node, int)) {
	if node == nil {
		return
	}
	if enter != nil {
		enter(node, depth)
	}
	traverse(node.left, depth+1, enter, leave)
	traverse(node.right, depth+1, enter, leave)
	if leave != nil {
		leave(node, depth)
	}
}

// Returs log with base 2 of an int.
func log2(num int) int {
	if num == 0 {
		return NegInf
	}
	i := -1
	for num > 0 {
		num = num >> 1
		i++
	}
	return i
}

func space(n int) {
	for i := 0; i < n; i++ {
		fmt.Print(" ")
	}
}


func main() {
	tree := new(Tree)
	tree.Push(1, 10, "hello, world")
	tree.Push(5, 6, "how are you today?")
	tree.Push(6, 45, "test")
	tree.BuildTree()


	results,err := tree.QueryIndex(6)
	if err != nil {
		fmt.Println(err)
	}
	result := <-results
	fmt.Println(result)

	tree.Print()

	FindingSingleElement()
	FindingElementSizeZeroRange()
	FindingElementPseudoEndlessRange()
	FindingMultipleElements()
	FindingOverlappingElements()
	OutOfRangeNotFound()
	AddingReverseDirection()
	FindingSameElementTwice()
}
func FindingSingleElement() {
	tree := new(Tree)
	test := "hello, world"
	tree.Push(1, 10, test)
	tree.BuildTree()

	results, err := tree.QueryIndex(4)
	if err != nil {
		fmt.Println("queryFailed")
	}

	result := <-results

	if result != test {
		fmt.Println("wrongElement",result,test)
	}

	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}
}

func FindingElementSizeZeroRange() {
	tree := new(Tree)
	test := "hello, world"
	tree.Push(1, 1, test)
	tree.BuildTree()

	results, err := tree.QueryIndex(1)
	if err != nil {
		fmt.Println("queryFailed")
	}

	result := <-results

	if result != test {
		fmt.Println("wrongElement",result,test)
	}

	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}
}

func FindingElementPseudoEndlessRange() {
	tree := new(Tree)
	test := "hello, world"
	tree.Push(1, Inf, test)
	tree.BuildTree()

	results, err := tree.QueryIndex(9999)
	if err != nil {
		fmt.Println("queryFailed")
	}

	result := <-results

	if result != test {
		fmt.Println("wrongElement",result,test)
	}

	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}
}

func find(element interface{}, elements []interface{}) (bool, int) {
	for i, e := range elements {
		if element == e {
			return true, i
		}
	}
	return false, -1
}

func FindingMultipleElements() {
	tree := new(Tree)
	tests := make([]interface{}, 5)
	tests[0] = "one"
	tests[1] = "two"
	tests[2] = 3.14
	tests[3] = 4
	tests[4] = "stuff"

	for i, test := range tests {
		tree.Push(10+i, 100+i, test)
	}

	tree.BuildTree()
	results, err := tree.QueryIndex(15)

	if err != nil {
		fmt.Println("queryFailed")
	}

	for result := range results {
		found, index := find(result, tests)
		if !found {
			fmt.Println("receivedUnexpected",result)
		}
		// Remove element from tests
		tests[index], tests = tests[len(tests)-1], tests[:len(tests)-1]
	}

	if len(tests) > 0 {
		for _, test := range tests {
			fmt.Println(fmt.Errorf("Did not find %v\n", test))
		}
	}

	if _, ok := <-results; ok != false {

	}
}

func FindingOverlappingElements() {
	tree := new(Tree)
	tests := make([]interface{}, 2)
	tests[0] = "one"
	tests[1] = "two"
	tree.Push(1, 10, tests[0])
	tree.Push(5, 15, tests[1])
	tree.BuildTree()

	// Index only in first range
	results, err := tree.QueryIndex(4)
	if err != nil {
		fmt.Println("queryFailed")
	}

	result := <-results
	if result != tests[0] {
		fmt.Println("wrongElement",result,tests[0])
	}

	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}

	// Index only in second range
	results, err = tree.QueryIndex(11)
	if err != nil {
		fmt.Println("queryFailed")
	}

	result = <-results
	if result != tests[1] {
		fmt.Println("wrongElement",result,tests[1])
	}

	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}

	// Index in both ranges
	results, err = tree.QueryIndex(6)
	if err != nil {
		fmt.Println("queryFailed")
	}

	for result := range results {
		found, index := find(result, tests)
		if !found {
			fmt.Println("receivedUnexpected",result)
		}
		// Remove element from tests
		tests[index], tests = tests[len(tests)-1], tests[:len(tests)-1]

	}

	if len(tests) > 0 {
		for _, test := range tests {
			fmt.Println(fmt.Errorf("Did not find %v\n", test))
		}
	}

	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}
}

func OutOfRangeNotFound() {
	tree := new(Tree)
	test := "hello, world"

	tree.Push(1, 10, test)

	tree.BuildTree()
	results, err := tree.QueryIndex(20)

	if err != nil {
		fmt.Println("queryFailed")
	}

	if result, ok := <-results; ok != false {

		fmt.Println("receivedUnexpected",result)
	}
}

func AddingReverseDirection() {
	tree := new(Tree)
	test := "hello, world"
	tree.Push(10, 1, test)
	tree.BuildTree()

	results, err := tree.QueryIndex(4)
	if err != nil {
		fmt.Println("queryFailed")
	}

	result := <-results

	if result != test {
		fmt.Println("wrongElement",result,test)
	}
}

func FindingSameElementTwice() {
	tree := new(Tree)
	test := "hello, world"

	tree.Push(1, 10, test)
	tree.Push(5, 15, test)

	tree.BuildTree()
	results, err := tree.QueryIndex(10)

	if err != nil {
		fmt.Println("queryFailed")
	}

	result := <-results

	if result != test {
		fmt.Println("wrongElement",result,test)
	}

	// `test` should only be sent once
	if _, ok := <-results; ok != false {
		fmt.Println("toManyElements")
	}
}

9.6 平衡二叉树

package main

import "fmt"

type AVL struct {
	value int      //值
	height int     //深度
	left *AVL      //左子树
	right *AVL     //右子树
}

//查找元素
func (t *AVL) Search(value int) bool {
	if t == nil {
		return false
	}
	compare := value - t.value
	if compare < 0 {
		return t.left.Search(value)
	}else if compare > 0 {
		return t.right.Search(value)
	}else {
		return true
	}
}



func (t *AVL) leftRotate() *AVL {  //左旋转
	headNode := t.right
	t.right = headNode.left
	headNode.left = t
	//更新结点高度
	t.height = max(t.left.getHeight(),t.right.getHeight()) + 1
	headNode.height = max(headNode.left.getHeight(),headNode.right.getHeight()) + 1
	return headNode
}

func (t *AVL) rightRotate() *AVL {  //右旋转
	headNode := t.left
	t.left = headNode.right
	headNode.right = t
	//更新结点高度
	t.height = max(t.left.getHeight(),t.right.getHeight()) +1
	headNode.height = max(headNode.left.getHeight(),headNode.right.getHeight()) + 1
	return headNode
}

func (t *AVL) rightThenLeftRotate() *AVL {  //右旋转,之后左旋转
	//以失衡点右结点先右旋转
	sonHeadNode := t.right.rightRotate()
	t.right = sonHeadNode
	//再以失衡点左旋转
	return t.leftRotate()
}

func (t *AVL) LeftThenRightRotate() *AVL {  //左旋转,之后右旋转
	//以失衡点左结点先左旋转
	sonHeadNode := t.left.leftRotate()
	t.left = sonHeadNode
	//再以失衡点左旋转
	return t.rightRotate()
}

func (t *AVL) adjust() *AVL {
	if t.right.getHeight() - t.left.getHeight() == 2 {
		if t.right.right.getHeight() > t.right.left.getHeight() {
			t = t.leftRotate()
		}else {
			t = t.rightThenLeftRotate()
		}
	}else if t.left.getHeight() - t.right.getHeight() == 2 {
		if t.left.left.getHeight() > t.left.right.getHeight() {
			t = t.rightRotate()
		} else {
			t = t.LeftThenRightRotate()
		}
	}
	return t
}

//添加元素
func (t *AVL) Insert(value int) *AVL {
	if t == nil {
		newNode := AVL{value,1,nil,nil}
		return &newNode
	}
	if value < t.value {
		t.left = t.left.Insert(value)
		t = t.adjust()
	}else if value > t.value{
		t.right = t.right.Insert(value)
		t = t.adjust()
	}else {
		fmt.Println("the node exit")
	}
	t.height = max(t.left.getHeight(),t.right.getHeight()) + 1
	return t
}


/*删除元素
*1、如果被删除结点只有一个子结点，就直接将A的子结点连至A的父结点上，并将A删除
*2、如果被删除结点有两个子结点，将该结点右子数内的最小结点取代A。
*3、查看是否平衡,该调整调整
 */
func (t *AVL) Delete(value int) *AVL {
	if t ==nil {
		return t
	}
	compare := value - t.value
	if compare < 0 {
		t.left = t.left.Delete(value)
	}else if compare > 0{
		t.right = t.right.Delete(value)
	}else { //找到结点,删除结点（）
		if t.left != nil && t.right != nil {
			t.value = t.right.getMin()
			t.right = t.right.Delete(t.value)
		} else if t.left !=nil {
			t = t.left
		}else {//只有一个右孩子或没孩子
			t = t.right
		}
	}
	if t != nil {
		t.height = max(t.left.getHeight(),t.right.getHeight()) + 1
		t = t.adjust()
	}
	return t
}

//按顺序获得树中元素
func (t *AVL) getAll() []int {
	values := []int{}
	return addValues(values,t)
}

//将一个节点加入切片中
func addValues(values []int,t *AVL) []int {
	if t != nil {
		values = addValues(values,t.left)
		values = append(values,t.value)
		fmt.Println(t.value,t.height)
		values = addValues(values,t.right)
	}
	return values
}

//查找子树最小值
func (t *AVL) getMin() int {
	if t == nil {
		return -1
	}
	if t.left == nil {
		return t.value
	} else {
		return t.left.getMin()
	}
}

//查找子树最大值
func (t *AVL) getMax() int {
	if t == nil {
		return -1
	}
	if t.right == nil {
		return t.value
	} else {
		return t.right.getMax()
	}
}

//查找最小结点
func (t *AVL) getMinNode() *AVL {
	if t == nil {
		return nil
	}else {
		for t.left != nil {
			t = t.left
		}
	}
	return t
}

//查找最大结点
func (t *AVL) getMaxNode() *AVL {
	if t == nil {
		return nil
	}else {
		for t.right != nil {
			t = t.right
		}
	}
	return t
}

//得到树高
func (t *AVL) getHeight() int {
	if t == nil {
		return 0
	}
	return t.height
}

func max(a int,b int) int{
	if a > b {
		return a
	}else {
		return b
	}
}


func main() {
	bsTree := AVL{100,1,nil,nil}
	newTree := bsTree.Insert(60)
	newTree = bsTree.Insert(120)
	newTree = bsTree.Insert(110)
	newTree = bsTree.Insert(130)
	newTree = bsTree.Insert(105)
	fmt.Println(newTree.getAll())

	newTree.Delete(110)
	fmt.Println(newTree.getAll())
	fmt.Println(newTree.Search(60))

}

9.7 B树(2-3-4树)

234树是B树的特例。B树每个节点含有很多个子节点及数据项，每个数据项放的是一个数据块。 2-3-4树中一个节点最多只能有4个孩子，那如果每个孩子数再多一些呢，这就是B树。

B树又称B-树，是一种平衡的多路查找树。B-树的阶是所有结点的孩子结点树的最大值。一棵m阶B-树，或为空树，或为满足下列特性的m叉树：

https://github.com/google/btree

package main
import (
	"fmt"
	"io"
	"math/rand"
	"sort"
	"strings"
	"sync"
	"time"
)

// Item represents a single object in the tree.
type Item interface {
	// Less tests whether the current item is less than the given argument.
	//
	// This must provide a strict weak ordering.
	// If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only
	// hold one of either a or b in the tree).
	Less(than Item) bool
}

const (
	DefaultFreeListSize = 32
)

var (
	nilItems    = make(items, 16)
	nilChildren = make(children, 16)
)

// FreeList represents a free list of btree nodes. By default each
// BTree has its own FreeList, but multiple BTrees can share the same
// FreeList.
// Two Btrees using the same freelist are safe for concurrent write access.
type FreeList struct {
	mu       sync.Mutex
	freelist []*node
}

// NewFreeList creates a new free list.
// size is the maximum size of the returned free list.
func NewFreeList(size int) *FreeList {
	return &FreeList{freelist: make([]*node, 0, size)}
}

func (f *FreeList) newNode() (n *node) {
	f.mu.Lock()
	index := len(f.freelist) - 1
	if index < 0 {
		f.mu.Unlock()
		return new(node)
	}
	n = f.freelist[index]
	f.freelist[index] = nil
	f.freelist = f.freelist[:index]
	f.mu.Unlock()
	return
}

// freeNode adds the given node to the list, returning true if it was added
// and false if it was discarded.
func (f *FreeList) freeNode(n *node) (out bool) {
	f.mu.Lock()
	if len(f.freelist) < cap(f.freelist) {
		f.freelist = append(f.freelist, n)
		out = true
	}
	f.mu.Unlock()
	return
}

// ItemIterator allows callers of Ascend* to iterate in-order over portions of
// the tree.  When this function returns false, iteration will stop and the
// associated Ascend* function will immediately return.
type ItemIterator func(i Item) bool

// New creates a new B-Tree with the given degree.
//
// New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
// and 2-4 children).
func New(degree int) *BTree {
	return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize))
}

// NewWithFreeList creates a new B-Tree that uses the given node free list.
func NewWithFreeList(degree int, f *FreeList) *BTree {
	if degree <= 1 {
		panic("bad degree")
	}
	return &BTree{
		degree: degree,
		cow:    &copyOnWriteContext{freelist: f},
	}
}

// items stores items in a node.
type items []Item

// insertAt inserts a value into the given index, pushing all subsequent values
// forward.
func (s *items) insertAt(index int, item Item) {
	*s = append(*s, nil)
	if index < len(*s) {
		copy((*s)[index+1:], (*s)[index:])
	}
	(*s)[index] = item
}

// removeAt removes a value at a given index, pulling all subsequent values
// back.
func (s *items) removeAt(index int) Item {
	item := (*s)[index]
	copy((*s)[index:], (*s)[index+1:])
	(*s)[len(*s)-1] = nil
	*s = (*s)[:len(*s)-1]
	return item
}

// pop removes and returns the last element in the list.
func (s *items) pop() (out Item) {
	index := len(*s) - 1
	out = (*s)[index]
	(*s)[index] = nil
	*s = (*s)[:index]
	return
}

// truncate truncates this instance at index so that it contains only the
// first index items. index must be less than or equal to length.
func (s *items) truncate(index int) {
	var toClear items
	*s, toClear = (*s)[:index], (*s)[index:]
	for len(toClear) > 0 {
		toClear = toClear[copy(toClear, nilItems):]
	}
}

// find returns the index where the given item should be inserted into this
// list.  'found' is true if the item already exists in the list at the given
// index.
func (s items) find(item Item) (index int, found bool) {
	i := sort.Search(len(s), func(i int) bool {
		return item.Less(s[i])
	})
	if i > 0 && !s[i-1].Less(item) {
		return i - 1, true
	}
	return i, false
}

// children stores child nodes in a node.
type children []*node

// insertAt inserts a value into the given index, pushing all subsequent values
// forward.
func (s *children) insertAt(index int, n *node) {
	*s = append(*s, nil)
	if index < len(*s) {
		copy((*s)[index+1:], (*s)[index:])
	}
	(*s)[index] = n
}

// removeAt removes a value at a given index, pulling all subsequent values
// back.
func (s *children) removeAt(index int) *node {
	n := (*s)[index]
	copy((*s)[index:], (*s)[index+1:])
	(*s)[len(*s)-1] = nil
	*s = (*s)[:len(*s)-1]
	return n
}

// pop removes and returns the last element in the list.
func (s *children) pop() (out *node) {
	index := len(*s) - 1
	out = (*s)[index]
	(*s)[index] = nil
	*s = (*s)[:index]
	return
}

// truncate truncates this instance at index so that it contains only the
// first index children. index must be less than or equal to length.
func (s *children) truncate(index int) {
	var toClear children
	*s, toClear = (*s)[:index], (*s)[index:]
	for len(toClear) > 0 {
		toClear = toClear[copy(toClear, nilChildren):]
	}
}

// node is an internal node in a tree.
//
// It must at all times maintain the invariant that either
//   * len(children) == 0, len(items) unconstrained
//   * len(children) == len(items) + 1
type node struct {
	items    items
	children children
	cow      *copyOnWriteContext
}

func (n *node) mutableFor(cow *copyOnWriteContext) *node {
	if n.cow == cow {
		return n
	}
	out := cow.newNode()
	if cap(out.items) >= len(n.items) {
		out.items = out.items[:len(n.items)]
	} else {
		out.items = make(items, len(n.items), cap(n.items))
	}
	copy(out.items, n.items)
	// Copy children
	if cap(out.children) >= len(n.children) {
		out.children = out.children[:len(n.children)]
	} else {
		out.children = make(children, len(n.children), cap(n.children))
	}
	copy(out.children, n.children)
	return out
}

func (n *node) mutableChild(i int) *node {
	c := n.children[i].mutableFor(n.cow)
	n.children[i] = c
	return c
}

// split splits the given node at the given index.  The current node shrinks,
// and this function returns the item that existed at that index and a new node
// containing all items/children after it.
func (n *node) split(i int) (Item, *node) {
	item := n.items[i]
	next := n.cow.newNode()
	next.items = append(next.items, n.items[i+1:]...)
	n.items.truncate(i)
	if len(n.children) > 0 {
		next.children = append(next.children, n.children[i+1:]...)
		n.children.truncate(i + 1)
	}
	return item, next
}

// maybeSplitChild checks if a child should be split, and if so splits it.
// Returns whether or not a split occurred.
func (n *node) maybeSplitChild(i, maxItems int) bool {
	if len(n.children[i].items) < maxItems {
		return false
	}
	first := n.mutableChild(i)
	item, second := first.split(maxItems / 2)
	n.items.insertAt(i, item)
	n.children.insertAt(i+1, second)
	return true
}

// insert inserts an item into the subtree rooted at this node, making sure
// no nodes in the subtree exceed maxItems items.  Should an equivalent item be
// be found/replaced by insert, it will be returned.
func (n *node) insert(item Item, maxItems int) Item {
	i, found := n.items.find(item)
	if found {
		out := n.items[i]
		n.items[i] = item
		return out
	}
	if len(n.children) == 0 {
		n.items.insertAt(i, item)
		return nil
	}
	if n.maybeSplitChild(i, maxItems) {
		inTree := n.items[i]
		switch {
		case item.Less(inTree):
			// no change, we want first split node
		case inTree.Less(item):
			i++ // we want second split node
		default:
			out := n.items[i]
			n.items[i] = item
			return out
		}
	}
	return n.mutableChild(i).insert(item, maxItems)
}

// get finds the given key in the subtree and returns it.
func (n *node) get(key Item) Item {
	i, found := n.items.find(key)
	if found {
		return n.items[i]
	} else if len(n.children) > 0 {
		return n.children[i].get(key)
	}
	return nil
}

// min returns the first item in the subtree.
func min(n *node) Item {
	if n == nil {
		return nil
	}
	for len(n.children) > 0 {
		n = n.children[0]
	}
	if len(n.items) == 0 {
		return nil
	}
	return n.items[0]
}

// max returns the last item in the subtree.
func max(n *node) Item {
	if n == nil {
		return nil
	}
	for len(n.children) > 0 {
		n = n.children[len(n.children)-1]
	}
	if len(n.items) == 0 {
		return nil
	}
	return n.items[len(n.items)-1]
}

// toRemove details what item to remove in a node.remove call.
type toRemove int

const (
	removeItem toRemove = iota // removes the given item
	removeMin                  // removes smallest item in the subtree
	removeMax                  // removes largest item in the subtree
)

// remove removes an item from the subtree rooted at this node.
func (n *node) remove(item Item, minItems int, typ toRemove) Item {
	var i int
	var found bool
	switch typ {
	case removeMax:
		if len(n.children) == 0 {
			return n.items.pop()
		}
		i = len(n.items)
	case removeMin:
		if len(n.children) == 0 {
			return n.items.removeAt(0)
		}
		i = 0
	case removeItem:
		i, found = n.items.find(item)
		if len(n.children) == 0 {
			if found {
				return n.items.removeAt(i)
			}
			return nil
		}
	default:
		panic("invalid type")
	}
	// If we get to here, we have children.
	if len(n.children[i].items) <= minItems {
		return n.growChildAndRemove(i, item, minItems, typ)
	}
	child := n.mutableChild(i)
	// Either we had enough items to begin with, or we've done some
	// merging/stealing, because we've got enough now and we're ready to return
	// stuff.
	if found {
		// The item exists at index 'i', and the child we've selected can give us a
		// predecessor, since if we've gotten here it's got > minItems items in it.
		out := n.items[i]
		// We use our special-case 'remove' call with typ=maxItem to pull the
		// predecessor of item i (the rightmost leaf of our immediate left child)
		// and set it into where we pulled the item from.
		n.items[i] = child.remove(nil, minItems, removeMax)
		return out
	}
	// Final recursive call.  Once we're here, we know that the item isn't in this
	// node and that the child is big enough to remove from.
	return child.remove(item, minItems, typ)
}

// growChildAndRemove grows child 'i' to make sure it's possible to remove an
// item from it while keeping it at minItems, then calls remove to actually
// remove it.
//
// Most documentation says we have to do two sets of special casing:
//   1) item is in this node
//   2) item is in child
// In both cases, we need to handle the two subcases:
//   A) node has enough values that it can spare one
//   B) node doesn't have enough values
// For the latter, we have to check:
//   a) left sibling has node to spare
//   b) right sibling has node to spare
//   c) we must merge
// To simplify our code here, we handle cases #1 and #2 the same:
// If a node doesn't have enough items, we make sure it does (using a,b,c).
// We then simply redo our remove call, and the second time (regardless of
// whether we're in case 1 or 2), we'll have enough items and can guarantee
// that we hit case A.
func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item {
	if i > 0 && len(n.children[i-1].items) > minItems {
		// Steal from left child
		child := n.mutableChild(i)
		stealFrom := n.mutableChild(i - 1)
		stolenItem := stealFrom.items.pop()
		child.items.insertAt(0, n.items[i-1])
		n.items[i-1] = stolenItem
		if len(stealFrom.children) > 0 {
			child.children.insertAt(0, stealFrom.children.pop())
		}
	} else if i < len(n.items) && len(n.children[i+1].items) > minItems {
		// steal from right child
		child := n.mutableChild(i)
		stealFrom := n.mutableChild(i + 1)
		stolenItem := stealFrom.items.removeAt(0)
		child.items = append(child.items, n.items[i])
		n.items[i] = stolenItem
		if len(stealFrom.children) > 0 {
			child.children = append(child.children, stealFrom.children.removeAt(0))
		}
	} else {
		if i >= len(n.items) {
			i--
		}
		child := n.mutableChild(i)
		// merge with right child
		mergeItem := n.items.removeAt(i)
		mergeChild := n.children.removeAt(i + 1)
		child.items = append(child.items, mergeItem)
		child.items = append(child.items, mergeChild.items...)
		child.children = append(child.children, mergeChild.children...)
		n.cow.freeNode(mergeChild)
	}
	return n.remove(item, minItems, typ)
}

type direction int

const (
	descend = direction(-1)
	ascend  = direction(+1)
)

// iterate provides a simple method for iterating over elements in the tree.
//
// When ascending, the 'start' should be less than 'stop' and when descending,
// the 'start' should be greater than 'stop'. Setting 'includeStart' to true
// will force the iterator to include the first item when it equals 'start',
// thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a
// "greaterThan" or "lessThan" queries.
func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) {
	var ok, found bool
	var index int
	switch dir {
	case ascend:
		if start != nil {
			index, _ = n.items.find(start)
		}
		for i := index; i < len(n.items); i++ {
			if len(n.children) > 0 {
				if hit, ok = n.children[i].iterate(dir, start, stop, includeStart, hit, iter); !ok {
					return hit, false
				}
			}
			if !includeStart && !hit && start != nil && !start.Less(n.items[i]) {
				hit = true
				continue
			}
			hit = true
			if stop != nil && !n.items[i].Less(stop) {
				return hit, false
			}
			if !iter(n.items[i]) {
				return hit, false
			}
		}
		if len(n.children) > 0 {
			if hit, ok = n.children[len(n.children)-1].iterate(dir, start, stop, includeStart, hit, iter); !ok {
				return hit, false
			}
		}
	case descend:
		if start != nil {
			index, found = n.items.find(start)
			if !found {
				index = index - 1
			}
		} else {
			index = len(n.items) - 1
		}
		for i := index; i >= 0; i-- {
			if start != nil && !n.items[i].Less(start) {
				if !includeStart || hit || start.Less(n.items[i]) {
					continue
				}
			}
			if len(n.children) > 0 {
				if hit, ok = n.children[i+1].iterate(dir, start, stop, includeStart, hit, iter); !ok {
					return hit, false
				}
			}
			if stop != nil && !stop.Less(n.items[i]) {
				return hit, false //	continue
			}
			hit = true
			if !iter(n.items[i]) {
				return hit, false
			}
		}
		if len(n.children) > 0 {
			if hit, ok = n.children[0].iterate(dir, start, stop, includeStart, hit, iter); !ok {
				return hit, false
			}
		}
	}
	return hit, true
}

// Used for testing/debugging purposes.
func (n *node) print(w io.Writer, level int) {
	fmt.Fprintf(w, "%sNODE:%v\n", strings.Repeat("  ", level), n.items)
	for _, c := range n.children {
		c.print(w, level+1)
	}
}

// BTree is an implementation of a B-Tree.
//
// BTree stores Item instances in an ordered structure, allowing easy insertion,
// removal, and iteration.
//
// Write operations are not safe for concurrent mutation by multiple
// goroutines, but Read operations are.
type BTree struct {
	degree int
	length int
	root   *node
	cow    *copyOnWriteContext
}

// copyOnWriteContext pointers determine node ownership... a tree with a write
// context equivalent to a node's write context is allowed to modify that node.
// A tree whose write context does not match a node's is not allowed to modify
// it, and must create a new, writable copy (IE: it's a Clone).
//
// When doing any write operation, we maintain the invariant that the current
// node's context is equal to the context of the tree that requested the write.
// We do this by, before we descend into any node, creating a copy with the
// correct context if the contexts don't match.
//
// Since the node we're currently visiting on any write has the requesting
// tree's context, that node is modifiable in place.  Children of that node may
// not share context, but before we descend into them, we'll make a mutable
// copy.
type copyOnWriteContext struct {
	freelist *FreeList
}

// Clone clones the btree, lazily.  Clone should not be called concurrently,
// but the original tree (t) and the new tree (t2) can be used concurrently
// once the Clone call completes.
//
// The internal tree structure of b is marked read-only and shared between t and
// t2.  Writes to both t and t2 use copy-on-write logic, creating new nodes
// whenever one of b's original nodes would have been modified.  Read operations
// should have no performance degredation.  Write operations for both t and t2
// will initially experience minor slow-downs caused by additional allocs and
// copies due to the aforementioned copy-on-write logic, but should converge to
// the original performance characteristics of the original tree.
func (t *BTree) Clone() (t2 *BTree) {
	// Create two entirely new copy-on-write contexts.
	// This operation effectively creates three trees:
	//   the original, shared nodes (old b.cow)
	//   the new b.cow nodes
	//   the new out.cow nodes
	cow1, cow2 := *t.cow, *t.cow
	out := *t
	t.cow = &cow1
	out.cow = &cow2
	return &out
}

// maxItems returns the max number of items to allow per node.
func (t *BTree) maxItems() int {
	return t.degree*2 - 1
}

// minItems returns the min number of items to allow per node (ignored for the
// root node).
func (t *BTree) minItems() int {
	return t.degree - 1
}

func (c *copyOnWriteContext) newNode() (n *node) {
	n = c.freelist.newNode()
	n.cow = c
	return
}

type freeType int

const (
	ftFreelistFull freeType = iota // node was freed (available for GC, not stored in freelist)
	ftStored                       // node was stored in the freelist for later use
	ftNotOwned                     // node was ignored by COW, since it's owned by another one
)

// freeNode frees a node within a given COW context, if it's owned by that
// context.  It returns what happened to the node (see freeType const
// documentation).
func (c *copyOnWriteContext) freeNode(n *node) freeType {
	if n.cow == c {
		// clear to allow GC
		n.items.truncate(0)
		n.children.truncate(0)
		n.cow = nil
		if c.freelist.freeNode(n) {
			return ftStored
		} else {
			return ftFreelistFull
		}
	} else {
		return ftNotOwned
	}
}

// ReplaceOrInsert adds the given item to the tree.  If an item in the tree
// already equals the given one, it is removed from the tree and returned.
// Otherwise, nil is returned.
//
// nil cannot be added to the tree (will panic).
func (t *BTree) ReplaceOrInsert(item Item) Item {
	if item == nil {
		panic("nil item being added to BTree")
	}
	if t.root == nil {
		t.root = t.cow.newNode()
		t.root.items = append(t.root.items, item)
		t.length++
		return nil
	} else {
		t.root = t.root.mutableFor(t.cow)
		if len(t.root.items) >= t.maxItems() {
			item2, second := t.root.split(t.maxItems() / 2)
			oldroot := t.root
			t.root = t.cow.newNode()
			t.root.items = append(t.root.items, item2)
			t.root.children = append(t.root.children, oldroot, second)
		}
	}
	out := t.root.insert(item, t.maxItems())
	if out == nil {
		t.length++
	}
	return out
}

// Delete removes an item equal to the passed in item from the tree, returning
// it.  If no such item exists, returns nil.
func (t *BTree) Delete(item Item) Item {
	return t.deleteItem(item, removeItem)
}

// DeleteMin removes the smallest item in the tree and returns it.
// If no such item exists, returns nil.
func (t *BTree) DeleteMin() Item {
	return t.deleteItem(nil, removeMin)
}

// DeleteMax removes the largest item in the tree and returns it.
// If no such item exists, returns nil.
func (t *BTree) DeleteMax() Item {
	return t.deleteItem(nil, removeMax)
}

func (t *BTree) deleteItem(item Item, typ toRemove) Item {
	if t.root == nil || len(t.root.items) == 0 {
		return nil
	}
	t.root = t.root.mutableFor(t.cow)
	out := t.root.remove(item, t.minItems(), typ)
	if len(t.root.items) == 0 && len(t.root.children) > 0 {
		oldroot := t.root
		t.root = t.root.children[0]
		t.cow.freeNode(oldroot)
	}
	if out != nil {
		t.length--
	}
	return out
}

// AscendRange calls the iterator for every value in the tree within the range
// [greaterOrEqual, lessThan), until iterator returns false.
func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(ascend, greaterOrEqual, lessThan, true, false, iterator)
}

// AscendLessThan calls the iterator for every value in the tree within the range
// [first, pivot), until iterator returns false.
func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(ascend, nil, pivot, false, false, iterator)
}

// AscendGreaterOrEqual calls the iterator for every value in the tree within
// the range [pivot, last], until iterator returns false.
func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(ascend, pivot, nil, true, false, iterator)
}

// Ascend calls the iterator for every value in the tree within the range
// [first, last], until iterator returns false.
func (t *BTree) Ascend(iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(ascend, nil, nil, false, false, iterator)
}

// DescendRange calls the iterator for every value in the tree within the range
// [lessOrEqual, greaterThan), until iterator returns false.
func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(descend, lessOrEqual, greaterThan, true, false, iterator)
}

// DescendLessOrEqual calls the iterator for every value in the tree within the range
// [pivot, first], until iterator returns false.
func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(descend, pivot, nil, true, false, iterator)
}

// DescendGreaterThan calls the iterator for every value in the tree within
// the range [last, pivot), until iterator returns false.
func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(descend, nil, pivot, false, false, iterator)
}

// Descend calls the iterator for every value in the tree within the range
// [last, first], until iterator returns false.
func (t *BTree) Descend(iterator ItemIterator) {
	if t.root == nil {
		return
	}
	t.root.iterate(descend, nil, nil, false, false, iterator)
}

// Get looks for the key item in the tree, returning it.  It returns nil if
// unable to find that item.
func (t *BTree) Get(key Item) Item {
	if t.root == nil {
		return nil
	}
	return t.root.get(key)
}

// Min returns the smallest item in the tree, or nil if the tree is empty.
func (t *BTree) Min() Item {
	return min(t.root)
}

// Max returns the largest item in the tree, or nil if the tree is empty.
func (t *BTree) Max() Item {
	return max(t.root)
}

// Has returns true if the given key is in the tree.
func (t *BTree) Has(key Item) bool {
	return t.Get(key) != nil
}

// Len returns the number of items currently in the tree.
func (t *BTree) Len() int {
	return t.length
}

// Clear removes all items from the btree.  If addNodesToFreelist is true,
// t's nodes are added to its freelist as part of this call, until the freelist
// is full.  Otherwise, the root node is simply dereferenced and the subtree
// left to Go's normal GC processes.
//
// This can be much faster
// than calling Delete on all elements, because that requires finding/removing
// each element in the tree and updating the tree accordingly.  It also is
// somewhat faster than creating a new tree to replace the old one, because
// nodes from the old tree are reclaimed into the freelist for use by the new
// one, instead of being lost to the garbage collector.
//
// This call takes:
//   O(1): when addNodesToFreelist is false, this is a single operation.
//   O(1): when the freelist is already full, it breaks out immediately
//   O(freelist size):  when the freelist is empty and the nodes are all owned
//       by this tree, nodes are added to the freelist until full.
//   O(tree size):  when all nodes are owned by another tree, all nodes are
//       iterated over looking for nodes to add to the freelist, and due to
//       ownership, none are.
func (t *BTree) Clear(addNodesToFreelist bool) {
	if t.root != nil && addNodesToFreelist {
		t.root.reset(t.cow)
	}
	t.root, t.length = nil, 0
}

// reset returns a subtree to the freelist.  It breaks out immediately if the
// freelist is full, since the only benefit of iterating is to fill that
// freelist up.  Returns true if parent reset call should continue.
func (n *node) reset(c *copyOnWriteContext) bool {
	for _, child := range n.children {
		if !child.reset(c) {
			return false
		}
	}
	return c.freeNode(n) != ftFreelistFull
}

// Int implements the Item interface for integers.
type Int int

// Less returns true if int(a) < int(b).
func (a Int) Less(b Item) bool {
	return a < b.(Int)
}


func init() {
	seed := time.Now().Unix()
	fmt.Println(seed)
	rand.Seed(seed)
}

// perm returns a random permutation of n Int items in the range [0, n).
func perm(n int) (out []Item) {
	for _, v := range rand.Perm(n) {
		out = append(out, Int(v))
	}
	return
}

// rang returns an ordered list of Int items in the range [0, n).
func rang(n int) (out []Item) {
	for i := 0; i < n; i++ {
		out = append(out, Int(i))
	}
	return
}

// all extracts all items from a tree in order as a slice.
func all(t *BTree) (out []Item) {
	t.Ascend(func(a Item) bool {
		out = append(out, a)
		return true
	})
	return
}

// rangerev returns a reversed ordered list of Int items in the range [0, n).
func rangrev(n int) (out []Item) {
	for i := n - 1; i >= 0; i-- {
		out = append(out, Int(i))
	}
	return
}

// allrev extracts all items from a tree in reverse order as a slice.
func allrev(t *BTree) (out []Item) {
	t.Descend(func(a Item) bool {
		out = append(out, a)
		return true
	})
	return
}


func main (){
	bTree := New(2)

	for _,item := range perm(100){
		if x := bTree.ReplaceOrInsert(item); x != nil {
			fmt.Println("insert didn't find item", item)
		}
	}

	fmt.Println(bTree.Min())
	fmt.Println(bTree.Max())
	fmt.Println(bTree.Len())

	fmt.Println(bTree.DeleteMin())
	fmt.Println(bTree.DeleteMax())
	fmt.Println(bTree.Len())

	fmt.Println(bTree.Get(Int(55)))
	fmt.Println(bTree.Has(Int(111)))
	fmt.Println(bTree.Delete(Int(98)))

	// 升序遍历
	bTree.Ascend(func(i Item) bool {
		fmt.Println(i)
		return true
	})

	bTree.AscendRange(Int(10),Int(20), func(i Item) bool {
		fmt.Println(i)
		return true
	})

	// 降序遍历
	bTree.Descend(func(i Item) bool {
		fmt.Println(i)
		return true
	})
}

9.8 B+树

https://github.com/timtadh/fs2

package main
import (
	"errors"
	"fmt"
	"reflect"
)

var (
	err error

	defaultOrder = 4
	minOrder     = 3
	maxOrder     = 20

	order          = defaultOrder
	queue          *Node
	verbose_output = false
	version        = 0.1
)

type BPlusTree struct {
	Root *Node
}

type Record struct {
	Value interface{}
}

type Node struct {
	Pointers []interface{}
	Keys     []int
	Parent   *Node
	IsLeaf   bool
	NumKeys  int
	Next     *Node
}

func NewBPlusTree() *BPlusTree {
	return &BPlusTree{}
}

func (t *BPlusTree) Insert(key int, value interface{}) error {
	var pointer *Record
	var leaf *Node

	if _, err := t.Find(key, false); err == nil {
		return errors.New("key already exists")
	}

	pointer, err := makeRecord(value)
	if err != nil {
		return err
	}

	if t.Root == nil {
		return t.startNewTree(key, pointer)
	}

	leaf = t.findLeaf(key, false)

	if leaf.NumKeys < order-1 {
		insertIntoLeaf(leaf, key, pointer)
		return nil
	}

	return t.insertIntoLeafAfterSplitting(leaf, key, pointer)
}

func (t *BPlusTree) Find(key int, verbose bool) (*Record, error) {
	i := 0
	c := t.findLeaf(key, verbose)
	if c == nil {
		return nil, errors.New("key not found")
	}
	for i = 0; i < c.NumKeys; i++ {
		if c.Keys[i] == key {
			break
		}
	}
	if i == c.NumKeys {
		return nil, errors.New("key not found")
	}

	r, _ := c.Pointers[i].(*Record)

	return r, nil
}

func (t *BPlusTree) FindAndPrint(key int, verbose bool) {
	r, err := t.Find(key, verbose)

	if err != nil || r == nil {
		fmt.Printf("Record not found under key %d.\n", key)
	} else {
		fmt.Printf("Record at %d -- key %d, value %s.\n", r, key, r.Value)
	}
}

func (t *BPlusTree) FindAndPrintRange(keyStart, keyEnd int, verbose bool) {
	var i int
	arraySize := keyEnd - keyStart + 1
	returnedKeys := make([]int, arraySize)
	returnedPointers := make([]interface{}, arraySize)
	numFound := t.findRange(keyStart, keyEnd, verbose, returnedKeys, returnedPointers)
	if numFound == 0 {
		fmt.Println("None found,\n")
	} else {
		for i = 0; i < numFound; i++ {
			c, _ := returnedPointers[i].(*Record)
			fmt.Printf("Key: %d  Location: %d  Value: %s\n",
				returnedKeys[i],
				returnedPointers[i],
				c.Value)
		}
	}
}

func (t *BPlusTree) PrintTree() {
	var n *Node
	i := 0
	rank := 0
	newRank := 0

	if t.Root == nil {
		fmt.Printf("Empty tree.\n")
		return
	}
	queue = nil
	enqueue(t.Root)
	for queue != nil {
		n = dequeue()
		if n != nil {
			if n.Parent != nil && n == n.Parent.Pointers[0] {
				newRank = t.pathToRoot(n)
				if newRank != rank {
					fmt.Printf("\n")
				}
			}
			if verbose_output {
				fmt.Printf("(%d)", n)
			}
			for i = 0; i < n.NumKeys; i++ {
				if verbose_output {
					fmt.Printf("%d ", n.Pointers[i])
				}
				fmt.Printf("%d ", n.Keys[i])
			}
			if !n.IsLeaf {
				for i = 0; i <= n.NumKeys; i++ {
					c, _ := n.Pointers[i].(*Node)
					enqueue(c)
				}
			}
			if verbose_output {
				if n.IsLeaf {
					fmt.Printf("%d ", n.Pointers[order-1])
				} else {
					fmt.Printf("%d ", n.Pointers[n.NumKeys])
				}
			}
			fmt.Printf(" | ")
		}
	}
	fmt.Printf("\n")
}

func (t *BPlusTree) PrintLeaves() {
	if t.Root == nil {
		fmt.Printf("Empty tree.\n")
		return
	}

	var i int
	c := t.Root
	for !c.IsLeaf {
		c, _ = c.Pointers[0].(*Node)
	}

	for {
		for i = 0; i < c.NumKeys; i++ {
			if verbose_output {
				fmt.Printf("%d ", c.Pointers[i])
			}
			fmt.Printf("%d ", c.Keys[i])
		}
		if verbose_output {
			fmt.Printf("%d ", c.Pointers[order-1])
		}
		if c.Pointers[order-1] != nil {
			fmt.Printf(" | ")
			c, _ = c.Pointers[order-1].(*Node)
		} else {
			break
		}
	}
	fmt.Printf("\n")
}

func (t *BPlusTree) Delete(key int) error {
	keyRecord, err := t.Find(key, false)
	if err != nil {
		return err
	}
	keyLeaf := t.findLeaf(key, false)
	if keyRecord != nil && keyLeaf != nil {
		t.deleteEntry(keyLeaf, key, keyRecord)
	}
	return nil
}

//
// Private Functions
//
func enqueue(newNode *Node) {
	var c *Node
	if queue == nil {
		queue = newNode
		queue.Next = nil
	} else {
		c = queue
		for c.Next != nil {
			c = c.Next
		}
		c.Next = newNode
		newNode.Next = nil
	}
}

func dequeue() *Node {
	n := queue
	queue = queue.Next
	n.Next = nil
	return n
}

func (t *BPlusTree) height() int {
	h := 0
	c := t.Root
	for !c.IsLeaf {
		c, _ = c.Pointers[0].(*Node)
		h++
	}
	return h
}

func (t *BPlusTree) pathToRoot(child *Node) int {
	length := 0
	c := child
	for c != t.Root {
		c = c.Parent
		length += 1
	}
	return length
}

func (t *BPlusTree) findRange(keyStart, keyEnd int, verbose bool, returnedKeys []int, returnedPointers []interface{}) int {
	var i int
	numFound := 0

	n := t.findLeaf(keyStart, verbose)
	if n == nil {
		return 0
	}
	for i = 0; i < n.NumKeys && n.Keys[i] < keyStart; i++ {
		if i == n.NumKeys { // could be wrong
			return 0
		}
	}
	for n != nil {
		for i = i; i < n.NumKeys && n.Keys[i] <= keyEnd; i++ {
			returnedKeys[numFound] = n.Keys[i]
			returnedPointers[numFound] = n.Pointers[i]
			numFound += 1
		}
		n, _ = n.Pointers[order-1].(*Node)
		i = 0
	}
	return numFound
}

func (t *BPlusTree) findLeaf(key int, verbose bool) *Node {
	i := 0
	c := t.Root
	if c == nil {
		if verbose {
			fmt.Printf("Empty tree.\n")
		}
		return c
	}
	for !c.IsLeaf {
		if verbose {
			fmt.Printf("[")
			for i = 0; i < c.NumKeys-1; i++ {
				fmt.Printf("%d ", c.Keys[i])
			}
			fmt.Printf("%d]", c.Keys[i])
		}
		i = 0
		for i < c.NumKeys {
			if key >= c.Keys[i] {
				i += 1
			} else {
				break
			}
		}
		if verbose {
			fmt.Printf("%d ->\n", i)
		}
		c, _ = c.Pointers[i].(*Node)
	}
	if verbose {
		fmt.Printf("Leaf [")
		for i = 0; i < c.NumKeys-1; i++ {
			fmt.Printf("%d ", c.Keys[i])
		}
		fmt.Printf("%d] ->\n", c.Keys[i])
	}
	return c
}

func cut(length int) int {
	if length%2 == 0 {
		return length / 2
	}

	return length/2 + 1
}

//
//	INSERTION
//
func makeRecord(value interface{}) (*Record, error) {
	newRecord := new(Record)
	if newRecord == nil {
		return nil, errors.New("Error: Record creation.")
	} else {
		newRecord.Value = value
	}
	return newRecord, nil
}

func makeNode() (*Node, error) {
	newNode := new(Node)
	if newNode == nil {
		return nil, errors.New("Error: Node creation.")
	}
	newNode.Keys = make([]int, order-1)
	if newNode.Keys == nil {
		return nil, errors.New("Error: New node keys array.")
	}
	newNode.Pointers = make([]interface{}, order)
	if newNode.Keys == nil {
		return nil, errors.New("Error: New node pointers array.")
	}
	newNode.IsLeaf = false
	newNode.NumKeys = 0
	newNode.Parent = nil
	newNode.Next = nil
	return newNode, nil
}

func makeLeaf() (*Node, error) {
	leaf, err := makeNode()
	if err != nil {
		return nil, err
	}
	leaf.IsLeaf = true
	return leaf, nil
}

func getLeftIndex(parent, left *Node) int {
	leftIndex := 0
	for leftIndex <= parent.NumKeys && parent.Pointers[leftIndex] != left {
		leftIndex += 1
	}
	return leftIndex
}

func insertIntoLeaf(leaf *Node, key int, pointer *Record) {
	var i, insertionPoint int

	for insertionPoint < leaf.NumKeys && leaf.Keys[insertionPoint] < key {
		insertionPoint += 1
	}

	for i = leaf.NumKeys; i > insertionPoint; i-- {
		leaf.Keys[i] = leaf.Keys[i-1]
		leaf.Pointers[i] = leaf.Pointers[i-1]
	}
	leaf.Keys[insertionPoint] = key
	leaf.Pointers[insertionPoint] = pointer
	leaf.NumKeys += 1
	return
}

func (t *BPlusTree) insertIntoLeafAfterSplitting(leaf *Node, key int, pointer *Record) error {
	var newLeaf *Node
	var insertionIndex, split, newKey, i, j int
	var err error

	newLeaf, err = makeLeaf()
	if err != nil {
		return nil
	}

	tempKeys := make([]int, order)
	if tempKeys == nil {
		return errors.New("Error: Temporary keys array.")
	}

	tempPointers := make([]interface{}, order)
	if tempPointers == nil {
		return errors.New("Error: Temporary pointers array.")
	}

	for insertionIndex < order-1 && leaf.Keys[insertionIndex] < key {
		insertionIndex += 1
	}

	for i = 0; i < leaf.NumKeys; i++ {
		if j == insertionIndex {
			j += 1
		}
		tempKeys[j] = leaf.Keys[i]
		tempPointers[j] = leaf.Pointers[i]
		j += 1
	}

	tempKeys[insertionIndex] = key
	tempPointers[insertionIndex] = pointer

	leaf.NumKeys = 0

	split = cut(order - 1)

	for i = 0; i < split; i++ {
		leaf.Pointers[i] = tempPointers[i]
		leaf.Keys[i] = tempKeys[i]
		leaf.NumKeys += 1
	}

	j = 0
	for i = split; i < order; i++ {
		newLeaf.Pointers[j] = tempPointers[i]
		newLeaf.Keys[j] = tempKeys[i]
		newLeaf.NumKeys += 1
		j += 1
	}

	newLeaf.Pointers[order-1] = leaf.Pointers[order-1]
	leaf.Pointers[order-1] = newLeaf

	for i = leaf.NumKeys; i < order-1; i++ {
		leaf.Pointers[i] = nil
	}
	for i = newLeaf.NumKeys; i < order-1; i++ {
		newLeaf.Pointers[i] = nil
	}

	newLeaf.Parent = leaf.Parent
	newKey = newLeaf.Keys[0]

	return t.insertIntoParent(leaf, newKey, newLeaf)
}

func insertIntoNode(n *Node, leftIndex, key int, right *Node) {
	var i int
	for i = n.NumKeys; i > leftIndex; i-- {
		n.Pointers[i+1] = n.Pointers[i]
		n.Keys[i] = n.Keys[i-1]
	}
	n.Pointers[leftIndex+1] = right
	n.Keys[leftIndex] = key
	n.NumKeys += 1
}

func (t *BPlusTree) insertIntoNodeAfterSplitting(oldNode *Node, leftIndex, key int, right *Node) error {
	var i, j, split, kPrime int
	var newNode, child *Node
	var tempKeys []int
	var tempPointers []interface{}
	var err error

	tempPointers = make([]interface{}, order+1)
	if tempPointers == nil {
		return errors.New("Error: Temporary pointers array for splitting nodes.")
	}

	tempKeys = make([]int, order)
	if tempKeys == nil {
		return errors.New("Error: Temporary keys array for splitting nodes.")
	}

	for i = 0; i < oldNode.NumKeys+1; i++ {
		if j == leftIndex+1 {
			j += 1
		}
		tempPointers[j] = oldNode.Pointers[i]
		j += 1
	}

	j = 0
	for i = 0; i < oldNode.NumKeys; i++ {
		if j == leftIndex {
			j += 1
		}
		tempKeys[j] = oldNode.Keys[i]
		j += 1
	}

	tempPointers[leftIndex+1] = right
	tempKeys[leftIndex] = key

	split = cut(order)
	newNode, err = makeNode()
	if err != nil {
		return err
	}
	oldNode.NumKeys = 0
	for i = 0; i < split-1; i++ {
		oldNode.Pointers[i] = tempPointers[i]
		oldNode.Keys[i] = tempKeys[i]
		oldNode.NumKeys += 1
	}
	oldNode.Pointers[i] = tempPointers[i]
	kPrime = tempKeys[split-1]
	j = 0
	for i += 1; i < order; i++ {
		newNode.Pointers[j] = tempPointers[i]
		newNode.Keys[j] = tempKeys[i]
		newNode.NumKeys += 1
		j += 1
	}
	newNode.Pointers[j] = tempPointers[i]
	newNode.Parent = oldNode.Parent
	for i = 0; i <= newNode.NumKeys; i++ {
		child, _ = newNode.Pointers[i].(*Node)
		child.Parent = newNode
	}

	return t.insertIntoParent(oldNode, kPrime, newNode)
}

func (t *BPlusTree) insertIntoParent(left *Node, key int, right *Node) error {
	var leftIndex int
	parent := left.Parent

	if parent == nil {
		return t.insertIntoNewRoot(left, key, right)
	}
	leftIndex = getLeftIndex(parent, left)

	if parent.NumKeys < order-1 {
		insertIntoNode(parent, leftIndex, key, right)
		return nil
	}

	return t.insertIntoNodeAfterSplitting(parent, leftIndex, key, right)
}

func (t *BPlusTree) insertIntoNewRoot(left *Node, key int, right *Node) error {
	t.Root, err = makeNode()
	if err != nil {
		return err
	}
	t.Root.Keys[0] = key
	t.Root.Pointers[0] = left
	t.Root.Pointers[1] = right
	t.Root.NumKeys += 1
	t.Root.Parent = nil
	left.Parent = t.Root
	right.Parent = t.Root
	return nil
}

func (t *BPlusTree) startNewTree(key int, pointer *Record) error {
	t.Root, err = makeLeaf()
	if err != nil {
		return err
	}
	t.Root.Keys[0] = key
	t.Root.Pointers[0] = pointer
	t.Root.Pointers[order-1] = nil
	t.Root.Parent = nil
	t.Root.NumKeys += 1
	return nil
}

func getNeighbourIndex(n *Node) int {
	var i int

	for i = 0; i <= n.Parent.NumKeys; i++ {
		if reflect.DeepEqual(n.Parent.Pointers[i], n) {
			return i - 1
		}
	}

	return i
}

func removeEntryFromNode(n *Node, key int, pointer interface{}) *Node {
	var i, numPointers int

	for n.Keys[i] != key {
		i += 1
	}

	for i += 1; i < n.NumKeys; i++ {
		n.Keys[i-1] = n.Keys[i]
	}

	if n.IsLeaf {
		numPointers = n.NumKeys
	} else {
		numPointers = n.NumKeys + 1
	}

	i = 0
	for n.Pointers[i] != pointer {
		i += 1
	}
	for i += 1; i < numPointers; i++ {
		n.Pointers[i-1] = n.Pointers[i]
	}
	n.NumKeys -= 1

	if n.IsLeaf {
		for i = n.NumKeys; i < order-1; i++ {
			n.Pointers[i] = nil
		}
	} else {
		for i = n.NumKeys + 1; i < order; i++ {
			n.Pointers[i] = nil
		}
	}

	return n
}

func (t *BPlusTree) adjustRoot() {
	var newRoot *Node

	if t.Root.NumKeys > 0 {
		return
	}

	if !t.Root.IsLeaf {
		newRoot, _ = t.Root.Pointers[0].(*Node)
		newRoot.Parent = nil
	} else {
		newRoot = nil
	}
	t.Root = newRoot

	return
}

func (t *BPlusTree) coalesceNodes(n, neighbour *Node, neighbourIndex, kPrime int) {
	var i, j, neighbourInsertionIndex, nEnd int
	var tmp *Node

	if neighbourIndex == -1 {
		tmp = n
		n = neighbour
		neighbour = tmp
	}

	neighbourInsertionIndex = neighbour.NumKeys

	if !n.IsLeaf {
		neighbour.Keys[neighbourInsertionIndex] = kPrime
		neighbour.NumKeys += 1

		nEnd = n.NumKeys
		i = neighbourInsertionIndex + 1
		for j = 0; j < nEnd; j++ {
			neighbour.Keys[i] = n.Keys[j]
			neighbour.Pointers[i] = n.Pointers[j]
			neighbour.NumKeys += 1
			n.NumKeys -= 1
			i += 1
		}
		neighbour.Pointers[i] = n.Pointers[j]

		for i = 0; i < neighbour.NumKeys+1; i++ {
			tmp, _ = neighbour.Pointers[i].(*Node)
			tmp.Parent = neighbour
		}
	} else {
		i = neighbourInsertionIndex
		for j = 0; j < n.NumKeys; j++ {
			neighbour.Keys[i] = n.Keys[j]
			n.Pointers[i] = n.Pointers[j]
			neighbour.NumKeys += 1
		}
		neighbour.Pointers[order-1] = n.Pointers[order-1]
	}

	t.deleteEntry(n.Parent, kPrime, n)
}

func (t *BPlusTree) redistributeNodes(n, neighbour *Node, neighbourIndex, kPrimeIndex, kPrime int) {
	var i int
	var tmp *Node

	if neighbourIndex != -1 {
		if !n.IsLeaf {
			n.Pointers[n.NumKeys+1] = n.Pointers[n.NumKeys]
		}
		for i = n.NumKeys; i > 0; i-- {
			n.Keys[i] = n.Keys[i-1]
			n.Pointers[i] = n.Pointers[i-1]
		}
		if !n.IsLeaf { // why the second if !n.IsLeaf
			n.Pointers[0] = neighbour.Pointers[neighbour.NumKeys]
			tmp, _ = n.Pointers[0].(*Node)
			tmp.Parent = n
			neighbour.Pointers[neighbour.NumKeys] = nil
			n.Keys[0] = kPrime
			n.Parent.Keys[kPrimeIndex] = neighbour.Keys[neighbour.NumKeys-1]
		} else {
			n.Pointers[0] = neighbour.Pointers[neighbour.NumKeys-1]
			neighbour.Pointers[neighbour.NumKeys-1] = nil
			n.Keys[0] = neighbour.Keys[neighbour.NumKeys-1]
			n.Parent.Keys[kPrimeIndex] = n.Keys[0]
		}
	} else {
		if n.IsLeaf {
			n.Keys[n.NumKeys] = neighbour.Keys[0]
			n.Pointers[n.NumKeys] = neighbour.Pointers[0]
			n.Parent.Keys[kPrimeIndex] = neighbour.Keys[1]
		} else {
			n.Keys[n.NumKeys] = kPrime
			n.Pointers[n.NumKeys+1] = neighbour.Pointers[0]
			tmp, _ = n.Pointers[n.NumKeys+1].(*Node)
			tmp.Parent = n
			n.Parent.Keys[kPrimeIndex] = neighbour.Keys[0]
		}
		for i = 0; i < neighbour.NumKeys-1; i++ {
			neighbour.Keys[i] = neighbour.Keys[i+1]
			neighbour.Pointers[i] = neighbour.Pointers[i+1]
		}
		if !n.IsLeaf {
			neighbour.Pointers[i] = neighbour.Pointers[i+1]
		}
	}
	n.NumKeys += 1
	neighbour.NumKeys -= 1

	return
}

func (t *BPlusTree) deleteEntry(n *Node, key int, pointer interface{}) {
	var minKeys, neighbourIndex, kPrimeIndex, kPrime, capacity int
	var neighbour *Node

	n = removeEntryFromNode(n, key, pointer)

	if n == t.Root {
		t.adjustRoot()
		return
	}

	if n.IsLeaf {
		minKeys = cut(order - 1)
	} else {
		minKeys = cut(order) - 1
	}

	if n.NumKeys >= minKeys {
		return
	}

	neighbourIndex = getNeighbourIndex(n)

	if neighbourIndex == -1 {
		kPrimeIndex = 0
	} else {
		kPrimeIndex = neighbourIndex
	}

	kPrime = n.Parent.Keys[kPrimeIndex]

	if neighbourIndex == -1 {
		neighbour, _ = n.Parent.Pointers[1].(*Node)
	} else {
		neighbour, _ = n.Parent.Pointers[neighbourIndex].(*Node)
	}

	if n.IsLeaf {
		capacity = order
	} else {
		capacity = order - 1
	}

	if neighbour.NumKeys+n.NumKeys < capacity {
		t.coalesceNodes(n, neighbour, neighbourIndex, kPrime)
		return
	} else {
		t.redistributeNodes(n, neighbour, neighbourIndex, kPrimeIndex, kPrime)
		return
	}

}
func main (){
	tree := NewBPlusTree()

	for i := 0;i < 100;i++ {
		err := tree.Insert(i, fmt.Sprintf("test%d",i))
		if err != nil {
			fmt.Println(err)
		}
	}

	for i := 0;i < 100;i++ {
		r, err := tree.Find(i, false)
		if err != nil {
			fmt.Println(err)
		}
		fmt.Println(r.Value)
	}


	// tree
	fmt.Println("================tree================")
	tree.PrintTree()
	// leaves
	fmt.Println("================leaves================")
	tree.PrintLeaves()
}

10.图

10.1 网

带权的图就是网

10.2 图的存储结构

10.2.1 邻接矩阵(顺序存储)

顶点数组：存储顶点信息
边数组:存储顶点数组中2个顶点关系和权
图{顶点数组，边数组，顶点数，边数，图类型}

不适合:查找顶点的度，需要扫描整张边数组，效率低，对顶点的相关操作适合:对边依次进行处理的操作，

10.2.2 邻接表(链式存储)

表头结点：存储顶点信息(data)和第一个邻接点地址(firstarc)，一般顺序存储在一个数组中
表中结点：存储表头结点在数组中的位置和下一个结点的指针，可存储权值
图{表头结点数组，顶点数，边数，图类型}

特点:

出度为各自链表中的结点数，入度需要遍历整个表的结点，还有一种方法，求入度，建立一个逆邻接表
稀疏图存储时，比使用邻接矩阵节省空间

10.2.3 十字链表(链式存储)

顶点结点:存储顶点信息(data) 一个弧头结点指针(firstin) 一个弧尾结点指针(firstout)
弧结点:tailvex 和 headvex 分别存储的是弧尾和弧头对应的顶点在数组中的位置下标； hlink 和 tlink 为指针域，分别指向弧头相同的下一个弧和弧尾相同的下一个弧； info 为指针域，存储的是该弧具有的相关信息，例如权值等
图{顶点结点数组，弧数，顶点数}

特点:

存储的是有向图或者有向网
求入度出度方便，入度为弧头的数量，出度为弧尾的数量
程序中构建链表对于每个新初始化的结点采用头插法进行插入

10.2.4 邻接多重表(链式存储)

邻接多重表可以看做是邻接表和十字链表的结合体

使用邻接表解决在无向图中删除某两个结点之间的边的操作时，由于表示边的结点分别处在两个顶点为头结点的链表中，所以需要都找到并删除，操作比较麻烦。处理类似这种操作，使用邻接多重表会更合适。

表结点构成：

mark 为标志域，作用是标记某结点是否已经被操作过，例如在遍历各结点时， mark 域为 0 表示还未遍历；mark 域为 1 表示该结点遍历过； ivex 和 jvex 分别表示该结点表示的边两端的顶点在数组中的位置下标； ilink 指向下一条与 ivex 相关的边； jlink 指向下一条与 jvex 相关的边； info 指向与该边相关的信息。

顶点结点构成：

data 为该顶点的数据域； firstedge 为指向第一条跟该顶点有关系的边。

10.2.5 总结

邻接表适用于所有的图结构，无论是有向图（网）还是无向图（网），存储结构较为简单，但是在存储一些问题时，例如计算某顶点的度，需要通过遍历的方式自己求得
十字链表适用于有向图（网）的存储，使用该方式存储的有向图，可以很容易计算出顶点的出度和入度，只需要知道对应链表中的结点个数即可
邻接多重表适用于无向图（网）的存储，该方式避免了使用邻接表存储无向图时出现的存储空间浪费的现象，同时相比邻接表存储无向图，更方便了某些边操作（遍历、删除等）的实现

10.3 有向无向图

package main

import (
	"fmt"
	"errors"
)

const Infinity int = 65535 //无穷大

//非线程安全
type VertexId uint

type Vertices []VertexId

type Edge struct {
	From VertexId
	To   VertexId
}

type graph struct {
	edges      map[VertexId]map[VertexId]int
	edgesCount int
	isDirected bool //定向图
}

type EdgesIterable interface {
	EdgesIter() <-chan Edge
}

type VerticesIterable interface {
	VerticesIter() <-chan VertexId
}

//边
func (g *graph) EdgesIter() <-chan Edge {
	ch := make(chan Edge)
	go func() {
		for from, connectedVertices := range g.edges {
			for to, _ := range connectedVertices {
				if g.isDirected { //有向边
					ch <- Edge{from, to}
				} else {
					if from < to { //无向边，只输出一次
						ch <- Edge{from, to}
					}
				}
			}
		}
		close(ch)
	}()
	return ch
}

//顶点
func (g *graph) VerticesIter() <-chan VertexId {
	ch := make(chan VertexId)
	go func() {
		for vertex, _ := range g.edges {
			ch <- vertex
		}
		close(ch)
	}()
	return ch
}

//检查顶点是否存在
func (g *graph) CheckVertex(vertex VertexId) bool {
	_, exists := g.edges[vertex]
	return exists
}

//增加顶点
func (g *graph) AddVertex(vertex VertexId) error {
	if !g.CheckVertex(vertex) {
		g.edges[vertex] = make(map[VertexId]int)
		return nil
	} else {
		return errors.New("Vertex already exists")
	}
}

//删除顶点
func (g *graph) RemoveVertex(vertex VertexId) error {
	if !g.CheckVertex(vertex) {
		return errors.New("unknow vertex")
	}
	//先删除边
	for _to, _ := range g.edges[vertex] {
		g.RemoveEdge(vertex, _to)
	}
	delete(g.edges, vertex)
	for _, connectedVertices := range g.edges {
		delete(connectedVertices, vertex)
	}
	return nil
}

//统计顶点
func (g *graph) VerticesCount() int {
	return len(g.edges)
}

//判断边是否存在
func (g *graph) CheckEdge(from, to VertexId) bool {
	if _, ok := g.edges[from][to]; ok {
		return true
	}
	return false
}

//增加边,存在就修改权
func (g *graph) AddEdge(from, to VertexId, weight int) error {
	//自身循环
	if from == to {
		return errors.New("cannot add self loop")
	}
	//不存在边
	if !g.CheckVertex(from) || !g.CheckVertex(to) {
		return errors.New("vertices not exist")
	}
	//判断边存在不
	if g.edges[from][to] > 0 {
		return errors.New("edge  exist")
	}
	g.edges[from][to] = weight
	if !g.isDirected {
		g.edges[to][from] = weight
	}
	g.edgesCount++
	return nil
}

//删除边
func (g *graph) RemoveEdge(from, to VertexId) error {
	//判断边是否存在
	if !g.CheckEdge(from, to) {
		return errors.New("edge not exist")
	}
	//删除
	delete(g.edges[from], to)
	if !g.isDirected {
		delete(g.edges[to], from)
	}
	g.edgesCount--
	return nil
}

//统计边
func (g *graph) EdgesCount() int {
	return g.edgesCount
}

//获取边权
func (g *graph) GetEdgeWeight(from, to VertexId) int {
	if !g.CheckEdge(from, to) {
		return Infinity
	}
	return g.edges[from][to]
}

//获取邻结点和权
func (g *graph) GetNeighbours(vertex VertexId) VerticesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)
		go func() {
			if connected, ok := g.edges[vertex]; ok {
				for vid, _ := range connected {
					ch <- vid
				}
			}
			close(ch)
		}()
		return ch
	}
	return VerticesIterable(&VerticesIterableHelp{iter: iterator})
}

//帮助获取
type VerticesIterableHelp struct {
	iter func() <-chan VertexId
}

func (v *VerticesIterableHelp) VerticesIter() <-chan VertexId {
	return v.iter()
}

type DirGraph struct {
	graph
}


//================有向图=======================
func NewDirected() *DirGraph {
	return &DirGraph{
		graph{
			edgesCount: 0,
			edges:      make(map[VertexId]map[VertexId]int),
			isDirected: true,
		},
	}
}

//入度
func (g *graph) GetPredecessors(vertex VertexId) VerticesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)
		go func() {
			for VertexId, _ := range g.edges {
				if g.CheckEdge(VertexId, vertex) {
					ch <- VertexId
				}
			}
			close(ch)
		}()
		return ch
	}

	return VerticesIterable(&VerticesIterableHelp{iter: iterator})
}

//出度
func (g *graph) GetSuccessors(vertex VertexId) VerticesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)
		go func() {
			if connected, ok := g.edges[vertex]; ok {
				for VertexId, _ := range connected {
					if g.CheckEdge(vertex, VertexId) {
						ch <- VertexId
					}
				}
			}
			close(ch)
		}()
		return ch
	}

	return VerticesIterable(&VerticesIterableHelp{iter: iterator})
}

func (g *DirGraph) Reverse() *DirGraph {
	r := NewDirected()

	vertices := g.VerticesIter()
	for vertex := range vertices {
		r.AddVertex(vertex)
	}

	edges := g.EdgesIter()
	for edge := range edges {
		r.AddEdge(edge.To, edge.From, 1)
	}

	return r
}

//================无向图=======================

type UnGraph struct {
	graph
}

func NewUndirected() *UnGraph {
	return &UnGraph{
		graph{
			edgesCount: 0,
			edges:      make(map[VertexId]map[VertexId]int),
			isDirected: false,
		},
	}
}

func main() {
	TestNewUndirected()
	TestNewDirected()
}


func TestNewUndirected() {
	g := NewUndirected()
	//增加顶点
	for i := 0; i < 10; i++ {
		g.AddVertex(VertexId(i))
	}

	if g.VerticesCount() != 10 {
		fmt.Println("count err")
		return
	}

	//增加边
	for i := 0; i < 10; i++ {
		_ = g.AddEdge(VertexId(i), VertexId(i%2), 1)
	}
	if !g.CheckEdge(2, 0) {
		fmt.Println("err")
		return
	}
	if g.CheckEdge(2, 1) {
		fmt.Println("err")
		return
	}
	if g.GetEdgeWeight(2, 0) != 1 {
		fmt.Println("err")
		return
	}

	//删除顶点
	if err := g.RemoveVertex(VertexId(2));err != nil {
		fmt.Println(err)
		return
	}
	if g.CheckVertex(VertexId(2)) {
		fmt.Println("err")
		return
	}
	if g.CheckEdge(2, 0) {
		fmt.Println("err")
		return
	}

	//增加边，存在修改
	if err := g.AddEdge(3, 0, 1);err != nil {
		fmt.Println("err")
		return
	}
	if !g.CheckEdge(3, 0) {
		fmt.Println("err")
		return
	}

	//删除边
	if err := g.RemoveEdge(3, 0);err != nil {
		fmt.Println("err")
		return
	}
	if g.CheckEdge(3, 0) {
		fmt.Println("err")
		return
	}

	//统计边
	c := g.EdgesIter()
	countEdge := 0
	for _ = range c {
		countEdge++
	}

	if g.EdgesCount() != countEdge {
		fmt.Println("err")
		return
	}
}

func TestNewDirected() {
	g := NewDirected()
	//增加顶点
	for i := 0; i < 10; i++ {
		g.AddVertex(VertexId(i))
	}
	if g.VerticesCount() != 10 {
		fmt.Println("count err")
		return
	}
	//增加边
	for i := 0; i < 10; i++ {
		g.AddEdge(VertexId(i), VertexId(i%2), 1)
	}

	if !g.CheckEdge(2, 0) {
		fmt.Println("err")
		return
	}
	if g.CheckEdge(2, 1) {
		fmt.Println("err")
		return
	}
	if g.GetEdgeWeight(2, 0) != 1 {
		fmt.Println("err")
		return
	}
	//删除顶点
	if err := g.RemoveVertex(VertexId(2));err != nil {
		fmt.Println(err)
		return
	}
	if g.CheckVertex(VertexId(2)) {
		fmt.Println("err")
		return
	}
	if g.CheckEdge(2, 0) {
		fmt.Println("err")
		return
	}
	//增加边，存在修改
	if err := g.AddEdge(3, 0, 1);err != nil {
		fmt.Println("err")
		return
	}
	if !g.CheckEdge(3, 0) {
		fmt.Println("err")
		return
	}
	//删除边
	if err := g.RemoveEdge(3, 0);err != nil {
		fmt.Println("err")
		return
	}
	if g.CheckEdge(3, 0) {
		fmt.Println("err")
		return
	}

	//统计边
	c := g.EdgesIter()
	countEdge := 0
	for _ = range c {
		countEdge++
	}

	if g.EdgesCount() != countEdge {
		fmt.Println("err")
		return
	}

	//查看
	//for p := range g.EdgesIter() {
	//	t.Log(p)
	//}
	//入度
	gp := g.GetPredecessors(VertexId(1)).VerticesIter()
	for p := range gp {
		if p != 3 && p != 5 && p != 7 && p != 9 {
			fmt.Println("err")
			return
		}
	}

	for p := range g.GetSuccessors(VertexId(4)).VerticesIter() {
		if p != VertexId(0) {
			fmt.Println("err")
			return
		}
	}
}

11.最短路径

11.1 Dijkstra

Dijkstra算法适用于边权为正的无向和有向图,不适用于有负边权的图

package main

import (
	hp "container/heap"
	"fmt"
)

type edge struct {
	node   string
	weight int
}

type graph struct {
	nodes map[string][]edge
}

func newGraph() *graph {
	return &graph{nodes: make(map[string][]edge)}
}

func (g *graph) addEdge(origin, destiny string, weight int) {
	g.nodes[origin] = append(g.nodes[origin], edge{node: destiny, weight: weight})
	g.nodes[destiny] = append(g.nodes[destiny], edge{node: origin, weight: weight})
}

func (g *graph) getEdges(node string) []edge {
	return g.nodes[node]
}

func (g *graph) Dijkstra(origin, destiny string) (int, []string) {
	h := newHeap()
	h.push(path{value: 0, nodes: []string{origin}})
	visited := make(map[string]bool)

	for len(*h.values) > 0 {
		// Find the nearest yet to visit node
		p := h.pop()
		node := p.nodes[len(p.nodes)-1]

		if visited[node] {
			continue
		}

		if node == destiny {
			return p.value, p.nodes
		}

		for _, e := range g.getEdges(node) {
			if !visited[e.node] {
				// We calculate the total spent so far plus the cost and the path of getting here
				h.push(path{value: p.value + e.weight, nodes: append([]string{}, append(p.nodes, e.node)...)})
			}
		}

		visited[node] = true
	}

	return 0, nil
}

type path struct {
	value int
	nodes []string
}

type minPath []path

func (h minPath) Len() int           { return len(h) }
func (h minPath) Less(i, j int) bool { return h[i].value < h[j].value }
func (h minPath) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *minPath) Push(x interface{}) {
	*h = append(*h, x.(path))
}

func (h *minPath) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

type heap struct {
	values *minPath
}

func newHeap() *heap {
	return &heap{values: &minPath{}}
}

func (h *heap) push(p path) {
	hp.Push(h.values, p)
}

func (h *heap) pop() path {
	i := hp.Pop(h.values)
	return i.(path)
}


func main() {
	fmt.Println("Dijkstra")
	// Example
	graph := newGraph()
	graph.addEdge("S", "B", 4)
	graph.addEdge("S", "C", 2)
	graph.addEdge("B", "C", 1)
	graph.addEdge("B", "D", 5)
	graph.addEdge("C", "D", 8)
	graph.addEdge("C", "E", 10)
	graph.addEdge("D", "E", 2)
	graph.addEdge("D", "T", 6)
	graph.addEdge("E", "T", 2)
	fmt.Println(graph.Dijkstra("S", "T"))
}

11.2 Prim

package main

import (
	"fmt"
	//"github.com/davecgh/go-spew/spew"
	"sync"
)

type node struct {
	id string
}

type Edge struct {
	src    Node
	dst    Node
	weight float64
}

type Graph struct {
	sync.RWMutex
	edge    map[string]map[string]float64
	nodeMap map[string]Node // record all the node in a graph
}

type Node interface {
	NodeID() string
}

func NewNode(id string) Node {
	return &node{id: id}
}

func (n *node) NodeID() string {
	return n.id
}

func NewEdge(src Node, dst Node, w float64) *Edge {
	return &Edge{src: src, dst: dst, weight: w}
}

func NewGraph() *Graph {
	return &Graph{
		edge:    make(map[string]map[string]float64),
		nodeMap: make(map[string]Node),
	}
}

func (g *Graph) AddEdge(nodeID1 string, nodeID2 string, w float64) {
	g.Lock()
	defer g.Unlock()

	if nodeID1 == nodeID2 {
		panic("can't add same vertex in one edge")
		return
	}

	if w == 0 {
		panic("weight can't use 0")
		return
	}

	// record each vertex
	g.nodeMap[nodeID1] = NewNode(nodeID1)
	g.nodeMap[nodeID2] = NewNode(nodeID2)

	if _, ok := g.edge[nodeID1]; ok {
		g.edge[nodeID1][nodeID2] = w
	} else {
		tempMap := make(map[string]float64)
		tempMap[nodeID2] = w
		g.edge[nodeID1] = tempMap
	}
}

func main() {
	g := NewGraph()
	g.AddEdge("A", "B", 7)
	g.AddEdge("A", "D", 5)
	g.AddEdge("B", "C", 8)
	g.AddEdge("B", "A", 7)
	g.AddEdge("B", "D", 9)
	g.AddEdge("B", "E", 7)
	g.AddEdge("C", "B", 8)
	g.AddEdge("C", "E", 5)
	g.AddEdge("D", "A", 5)
	g.AddEdge("D", "B", 9)
	g.AddEdge("D", "F", 6)
	g.AddEdge("D", "E", 15)
	g.AddEdge("D", "F", 6)
	g.AddEdge("E", "B", 7)
	g.AddEdge("E", "C", 5)
	g.AddEdge("E", "D", 15)
	g.AddEdge("E", "F", 8)
	g.AddEdge("E", "G", 9)
	g.AddEdge("F", "D", 6)
	g.AddEdge("F", "E", 8)
	g.AddEdge("F", "G", 11)
	g.AddEdge("G", "E", 9)
	g.AddEdge("G", "F", 11)

	fmt.Println(g)
	g.Prim("D")
}

func (g *Graph) Prim(src string) {
	knowNode := make(map[int]string)
	unknowNode := g.nodeMap
	tempEdgeMap := g.edge
	edgeMap := make(map[int]*Edge)
	totalWeight := float64(0)
	key := 0

	knowNode[key] = src
	delete(unknowNode, knowNode[key])
	key++
	var temp string

	// 找到与knowNodeMap里节点权值最小的节点，并将该节点加入nodeMap
	for len(unknowNode) > 0 {
		min := float64(1000000)
		for nodeID := range unknowNode {
			for _, v := range knowNode {
				if tempEdgeMap[nodeID][v] < min && tempEdgeMap[nodeID][v] != 0 {
					min = tempEdgeMap[nodeID][v]
					knowNode[key] = nodeID
					temp = v
				}
			}
		}

		n1 := NewNode(temp)
		n2 := NewNode(knowNode[key])
		edge := NewEdge(n1, n2, min)
		edgeMap[key-1] = edge

		// 从未知节点map删除已经找到的当前权值最小的节点
		delete(unknowNode, knowNode[key])
		totalWeight += min
		key++
	}

	fmt.Println(totalWeight)
	fmt.Println(knowNode)
}

11.3 Kruskal

package main

import (
	"container/heap"
	"container/list"
	"log"
	"sort"
)

// Edge is a connection bitween two vertecies. Every edge has a weight between the vertecies.
type Edge struct {
	source string
	sink   string
	weight float32
}

type edgeSlice []Edge

func (e edgeSlice) Len() int {
	return len(e)
}

func (e edgeSlice) Less(i, j int) bool {
	return e[i].weight < e[j].weight
}

func (e edgeSlice) Swap(i, j int) {
	e[i], e[j] = e[j], e[i]
}

func sortEdges(edges []Edge) {
	var readyToSort edgeSlice = edges
	sort.Sort(readyToSort)
}

// Graph is a complete graph with vertecies and edges between them.
type Graph struct {
	vertecies map[string][]Edge
}

// AddVertex adds a vertex to the graph
func (g *Graph) AddVertex(vertex string) {
	g.vertecies[vertex] = make([]Edge, 0)
}

// AddEdge adds an edge to the graph
func (g *Graph) AddEdge(source string, sink string, weight float32) {
	edge := Edge{source, sink, weight}
	g.vertecies[source] = append(g.vertecies[source], edge)
}

func (g *Graph) getVertecies() []string {
	var edges = make([]string, len(g.vertecies))
	i := 0
	for k := range g.vertecies {
		edges[i] = k
		i++
	}

	return edges
}

func (g Graph) getEdges(vertex string) ([]Edge, bool) {
	edges, ok := g.vertecies[vertex]
	return edges, ok
}

type vertexQueue []string

func (vq vertexQueue) Len() int            { return len(vq) }
func (vq vertexQueue) Less(i, j int) bool  { return vq[i] < vq[j] }
func (vq vertexQueue) Swap(i, j int)       { vq[i], vq[j] = vq[j], vq[i] }
func (vq *vertexQueue) Push(x interface{}) { *vq = append(*vq, x.(string)) }
func (vq *vertexQueue) Pop() interface{} {
	items := *vq
	n := len(*vq)
	x := items[n-1]
	*vq = items[0 : n-1]
	return x
}

func graphContainsNoCycles(g traverseGraph, from, to string) bool {
	return depthFirstSearch(g, from, to) == false
}

func depthFirstSearch(g traverseGraph, from, to string) bool {
	verteciesNext := make(vertexQueue, 0)
	heap.Init(&verteciesNext)
	heap.Push(&verteciesNext, from)

	for verteciesNext.Len() > 0 {
		vertex := heap.Pop(&verteciesNext).(string)
		edges, hasVertex := g.vertecies[vertex]
		if hasVertex {
			for e := edges.Front(); e != nil; e = e.Next() {
				edge := e.Value.(Edge)
				if edge.sink == to {
					return true
				}

				heap.Push(&verteciesNext, edge.sink)
			}
		}
	}

	return false
}

func addUndirectedEdge(tg *traverseGraph, edge Edge) {
	addEdge(tg, edge)
	reverseEdge := Edge{edge.sink, edge.source, edge.weight}
	addEdge(tg, reverseEdge)
}
func addEdge(tg *traverseGraph, x Edge) {
	edgesForVertex, hasVertex := tg.vertecies[x.source]
	if !hasVertex {
		edgesForVertex = list.New()
		tg.vertecies[x.source] = edgesForVertex
	}

	edgesForVertex.PushBack(x)
}

func getUniqueEdges(g *Graph, vertecies []string) []Edge {
	edges := make([]Edge, 0)
	for _, vertex := range vertecies {
		edgeInVertex, hasVertex := g.getEdges(vertex)
		if hasVertex {
			for _, edge := range edgeInVertex {
				has := false
				for _, e := range edges {
					has = has || e == edge
				}

				if has == false {
					edges = append(edges, edge)
				}
			}
		}
	}

	return edges
}

// Kruskals performs kruskal's algorithm
func Kruskals(g *Graph) []Edge {
	vertecies := g.getVertecies()
	numVertecies := len(vertecies)

	edges := getUniqueEdges(g, vertecies)
	sortEdges(edges)

	var gCopy = createEmptyGraphWithVertecies(*g)

	traversedVertecies := make(map[string]bool)
	a := make([]Edge, numVertecies-1) // resulting set
	it := 0
	for _, currentEdge := range edges {
		_, hasSource := traversedVertecies[currentEdge.source]
		_, hasSink := traversedVertecies[currentEdge.sink]
		if hasSource && hasSink {
			if graphContainsNoCycles(gCopy, currentEdge.source, currentEdge.sink) {
				a[it] = currentEdge
				traversedVertecies[currentEdge.source] = true
				traversedVertecies[currentEdge.sink] = true
				addUndirectedEdge(&gCopy, currentEdge)
				it++
			} else {
				log.Printf("Dropped %v -> %v", currentEdge.source, currentEdge.sink)
			}
		} else {
			a[it] = currentEdge
			traversedVertecies[currentEdge.source] = true
			traversedVertecies[currentEdge.sink] = true
			addUndirectedEdge(&gCopy, currentEdge)
			it++
		}

		if it == numVertecies-1 {
			break
		}
	}

	return a
}

// New creates a new graph and assigns its values
func New() Graph {
	vertecies := make(map[string][]Edge)
	g := Graph{vertecies}
	return g
}

type traverseGraph struct {
	vertecies map[string]*list.List
}

func createEmptyGraphWithVertecies(g Graph) traverseGraph {
	vertecies := make(map[string]*list.List)
	var gCopy = traverseGraph{vertecies}
	for k := range g.vertecies {
		traverseEdges := list.New()
		gCopy.vertecies[k] = traverseEdges
	}

	return gCopy
}

func buildExampleGraph() Graph {
	var g = New()
	var vertecies = []string{"a", "b", "c", "d"}
	for _, vertex := range vertecies {
		g.AddVertex(vertex)
	}

	g.AddEdge("a", "b", 1)
	g.AddEdge("b", "c", 2)
	g.AddEdge("c", "a", 2)
	g.AddEdge("c", "d", 8)
	g.AddEdge("d", "a", 1)

	return g
}

func main() {
	g := buildExampleGraph()
	edges := Kruskals(&g)
	for _, edge := range edges {
		log.Printf("Edge from %s to %s with cost %v", edge.source, edge.sink, edge.weight)
	}
}