23树实现

这几天在看HashMap中的红黑树,发现较为复杂,就从2-3树开始完整实现了一遍。 为啥会有2-3树 最合理的情况下,是有一棵满二叉树。但是构造一棵满二叉树并不容易。看一下二叉树的一般生长过程 二叉树在生长过程中,无法保持总是满的(我给你两个数,你给我弄个满二叉树 生长一般是自顶向下的,左右子树的树高容易不一致(极端情况下,退化成链表 如果第2步,不急着分清父子,第3步才来生成一棵2-Tree的话,就能得到一棵满树。 同样的推广到4,5步,再重新变形一下 emmm,这好像不是一棵满树啊。因为依旧是向下生长,并没有改变其左右不均匀的问题。那我们试着往上试试。 看起来除了A有两个爸爸,其他好像没啥问题啊。依然满足节点左侧所有点小于节点,右侧所有点大于节点。稍微变形一下 一棵满的3-Tree闪亮登场。 生成2-3树 插入 对于2-3树的每个叶子节点来说,只有两种情况 空2-Tree变成空3-Tree 空3-Tree变成满2-Tree 升级 当叶子节点由空3-Tree变为满2-Tree的时候,我们选择往上生长,这个过程就叫它升级好了。也只有两种情况 满2-Tree的子结点由空3-Tree变成满2-Tree,整个满2-Tree变成满3-Tree 满3-Tree的子结点由空3-Tree变成满2-Tree,整个满3-Tree变成满4-Tree,再分解成满两棵满2-Tree,树高+1 伪代码实现 首先定义树 class Tree { var p: Tree? = null //父亲 var v: LinkedList<Int> = LinkedList() //结点值 var c: LinkedList<Tree> = LinkedList() //子结点 val type get() = "${v.size}-${c.size}" //根据值的数量和子结点数量确定树的类型 } 然后就是插入代码 fun insert(tree: Tree) { when (tree.type) { "1-0" -> {//添加一个单点 when (this....

September 30, 2018

Windows下Terminal解决方案

不得不说Windows的Terminal实在是太不友好了。 CMD,没啥好说的,要死的玩意儿。 PowerShell,知乎上吹的比较厉害,但是另起一套,和*nix上完全不一样,学习成本不划算,何况我并不是一个专业用户。 WSL,知乎吹的更厉害了,用这玩意儿,各个开发的SDK得准备两套,简直神经病。而且,一个实现不完整的Linux == 不能用的Linux。 ...

September 15, 2018

Esxi 安装 Openwrt

新建虚拟机,添加一块小硬盘,4G足矣,再添加一个光驱,加载一个Linux ISO(只是需要一个Shell命令 启动虚拟机,选择从光盘启动。 ...

September 15, 2018

堆排序

堆排序 将数组看成一个二叉堆,大致就是这样的 父节点要大于子节点 简单一点,遍历整个树,每个节点都和父节点比较,如果大于父节点,则交换位置 tailrec fun casWithFather(array: IntArray, index: Int) { if (index == 0) { //第一个节点 do nothing } else { //和父节点比,如果大于父节点,递归和父节点比。 val parent = (index + 1) / 2 - 1 if (array[parent] < array[index]) { array.swap(index, parent) casWithFather(array, parent) } } } 最大堆排序 经过上一步的处理,这个堆已经满足了父节点大于子节点,为一个最大堆。 如何来利用最大堆排序呢,我们取出最大的父节点,然后再生成最大堆。 取出最大父节点 与最尾端节点交换位置 对新的堆排序(排除掉取出放在尾端的节点) tailrec fun casWithChild(array: IntArray, farther: Int, end: Int) { val lc = farther * 2 + 1 //左节点 val rc = farther * 2 + 2 //右节点 if (lc >= end) {//到达了需要排序"堆"的终点 return } val better = if (rc >= end || array[lc] > array[rc]) { lc } else { rc } if (array[farther] < array[better]) { array....

August 20, 2018

希尔排序

希尔排序 希尔排序是基于插入排序的一个演进 插入排序很大一部分开销在于插入这个操作上,后面所有的数据都需要移动。 分割 我们先按N为步进来分割数组,如下为N=4 1 5 9 …… 2 6 10 …… 3 7 11 …… 4 8 12 …… 对每个子数组进行排序 合并 实际上就是不分割数组,进行插入排序。 优点 分割之后,每个数组较小,能减少移动次数。 合并时,整个数组都是部分有序的,也能减少移动次数。...

August 20, 2018

归并排序

简单版本 两个已经排序好的数组, 1,3,5,7,8,9...... 2,4,5,7,10...... 显而易见,用两个指针m、n,分别指向两个数组的开头 比较m、n大小 小的指针所在点放入新数组,并将该指针向后移动一位 重复比较,移动 最后有一个指针到了尽头,将另外的指针剩余部分放入新数组尾部 这样就完成了排序。 有序?不存在的 如果只有一个数组,而且是无序的,想要使用归并排序,怎么办? 按长度分成2个数组,是有序的话,就归并 不是有序的,分成4个数组,是有序的话,就归并 还不是有序的,一直分成有序的为止,此时每个数组长度为1 然后归并 代码 static void sort(int[] array) { for (int i = 1; i < array.length / 2; i *= 2) { int step = i * 2; for (int j = 0; j + step <= array.length; j += step) { merge(array, j, i, i); } final int left = array.length % (i * 2); if (left > 0) { merge(array, array....

August 20, 2018

QNAP TS-453Bmini 体验

很早之前就有弄一台服务器或者NAS放家里的想法, 从树莓派,工控板,Gen8,到ITX小板,几乎各种方案都在我脑海中过了一遍。 最近京东618将至,又开始看起各种PC配置和NAS,虽然我很清楚没啥卵用,但是后面想到,干脆当作给自己买一个玩具好了。 ...

June 13, 2018

Socks5 Proxy & Shadowsocks

Socks5代理协议非常简单,小巧,整个文档很短,应用支持度也非常不错。对于个人开发实现来说是个不错的选择。 ...

May 29, 2018

Socks5 协议

...

November 28, 2017

Kotlin协程(翻译-未完成)

引言 Kotlin,作为一个语言,标准库中通过提供最小的底层API来给其他库更好的利用协程。不像其他语言,async 和 await 并不是Kotlin的关键字,甚至都不是标准库的一部分。此外,Kotlin的中断函数(suspending function)概念比 future 和 promise 提供了更安全,更不容易出错的异步操作。 协程基础 第一个协程 fun main(args: Array<String>) { launch(CommonPool) { // create new coroutine in common thread pool delay(1000L) // non-blocking delay for 1 second (default time unit is ms) println("World!") // print after delay } println("Hello,") // main function continues while coroutine is delayed Thread.sleep(2000L) // block main thread for 2 seconds to keep JVM alive } 运行结果...

September 6, 2017