通常C++通过指针引用计数来回收对象，但是这不能处理循环引用。为了避免引用计数的缺陷，后来出现了标记清除，分代等垃圾回收算法。Go的垃圾回收官方形容为 非分代 非紧缩 写屏障 并发标记清理。标记清理算法的字面解释，就是将可达的内存块进行标记mark，最后没有标记的不可达内存块将进行清理sweep。 三色标记法判断一个对象是不是垃圾需不需要标记，就看是否能从当前栈或全局数据区 直接或间接的引用到这个对象。这个初始的当前goroutine的栈和全局数据区称为GC的root区。扫描从这里开始，通过markroot将所有root区域的指针标记为可达，然后沿着这些指针扫描，递归地标记遇到的所有可达对象。因此引出几个问题： 标记清理能不能与用户代码并发 如何获得对象的类型而找到所有可达区域 标记位记录在...阅读全文
目录 红黑树原理详解及golang实现 二叉查找树 性质 红黑树 性质 operation 红黑树的插入 golang实现 类型定义 leftRotate RightRotate Item Interface insert 完整代码 小结 红黑树原理详解及golang实现 在看红黑树原理之前，先看下二叉查找树。 二叉查找树 二叉查找树，又称二叉排序树，二叉搜索树。 性质 它具备一下性质： 1、左子树上的所有节点均小于它的根节点值。 2、右子树上的所有节点的值均大于等于它根节点的值。 3、左佑子树也分别二叉排序树。 4、没有键值相等的节点。 既然叫搜索树，那这种结构的好处当然也就是搜索咯， 假如我们要查找15 1、从root节点开始，15<50，找左子树。 2、15<20，找左子树， 3、15...阅读全文
2-3-4树和普通红黑树 某些教程不区分普通红黑树和左倾红黑树的区别，直接将左倾红黑树拿来教学，并且称其为红黑树，因为左倾红黑树与普通的红黑树相比，实现起来较为简单，容易教学。在这里，我们区分开左倾红黑树和普通红黑树。 红黑树是一种近似平衡的二叉查找树，从2-3树或2-3-4树衍生而来。通过对二叉树节点进行染色，染色为红或黑节点，来模仿2-3树或2-3-4树的3节点和4节点，从而让树的高度减小。2-3-4树对照实现的红黑树是普通的红黑树，而2-3树对照实现的红黑树是一种变种，称为左倾红黑树，其更容易实现。 使用平衡树数据结构，可以提高查找元素的速度，我们在本章介绍2-3-4树，再用二叉树形式来实现2-3-4树，也就是普通的红黑树。 一、2-3-4 树 1.1. 2-3-4 树介绍 2-3-4...阅读全文
