Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial red black treered black tree定义红黑树是一种平衡树，他满足下面的性质 1.节点是红色或黑色。2.根是黑色。3.所有叶子都是黑色（叶子是NIL节点）。4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 red black tree解读性质红黑树的性质难以理解，这是因为他太过于抽象了, 如果你了解B Tree, 我们现在考虑节点中最多包含3个键的B Tree，他又叫2-3-4tree,意思是任何一个节点都有2，3或4个直接子孙，直接子孙指的是和当前节点相邻的子孙，相邻指的是恰好有一条边连接。2-3-4树的编码是比较复杂的，原因在于节点种类过多。我们现在考虑这样一种情况，RB tree中的红色节点代表他和他父亲在一起，即他+他的父亲构成了2key3son ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # T tree T tree 是一颗二叉树，他和avl tree有着一定的联系,总所周知，avl树为一颗二叉树，利用其中序维护信息，利用子树高度维护平衡。我们借此修改一下，我们尝试让avl树的每个节点维护多个信息[信息序列]，于是T tree就出现了。T tree是一颗二叉树，每个节点维护一个有序序列，用T 树的中序遍历方式，将其节点维护的序列依次相连即成为了我们维护的信息。 T tree 解释为了便于编码，我们不考虑序列中会出现相同的元素，可以证明，对于泛型编程方式而言，这并不影响该数据结构的功能，该数据结构依旧具备维护相同元素的能力 T tree结论非叶节点维护的序列都充满了各自的容器 T tree树上信息每一颗子树都要维护一个序列，对于每个节点，我们都维护一个稍微小一点的序列，比该序列中元素更小的元素放入左子树，否则放入右子树。 T tree搜索搜索的话，就是普通二叉树的搜索，比当前节 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 234tree参见4阶Btree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 23tree参见3阶Btree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # B* Tree B*树在B+树的基础上再把内部节点也整上链表，同时要求空间使用率为$\frac{2}{3}$而不是$\frac{1}{2}$ 代码 随缘

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial B+树优点 因为内部节点、根节点保存的是索引(指针),这导致单位储存空间储存的指针要比单位空间储存的键多得多，这同时导致了B+树能够比B树更加扁平。 代码 这东西实现难度有点高，太码农了，我随缘实现吧。哈哈哈哈哈哈。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial B TreeB树是一颗多叉树，和二叉树比较类似,但是每个节点有多个子节点和多个键，通常我们称最多拥有N个子节点的B树为N阶B树，B树为了保证树的有序，树上节点的子节点数量恰好比键的数量多1，这就保证了存在一种方式将子节点和键排在一起，且每个键的左边、右边都是子节点，这样形成的序列即为维护的序列。 B Tree 约束B树的节点分三类，根节点、叶子节点、内部节点(除了根节点和叶子节点以外的节点)所有的叶子节点的深度相同,这一点保证树的平衡根节点的键的的数量在区间[2,N-1]上 , N>=3每个内部节点、叶子节点的键的数量在区间$[\lceil\frac{N}{2}\rceil-1,N-1]$上每个节点的键的个数恰好比子节点个数多1 B Tree insertB树的插入很简单，找到应该插入的叶子节点，然后插入。这会可能导致树不符合约束->叶子节点上键的数量过多，此时叶子结点 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial AVL Tree AVL Tree使用高度差作为平衡因子，他要求兄弟的高度差的绝对值不超过1 code avl Tree代码

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial binary search treeBST是二叉搜索树，满足中序遍历是一个有序的序列,他是最最基础的二叉树，他不一定平衡， BST insert插入的时候，在树上递归插入，比当前节点大就向右边走，否则向左走 BST search查找的时候，同上 BST erase删除的时候，相对复杂，如果只有一个儿子，很简单，但是当他有两个儿子的时候，我们可以选择将一个儿子顶替自己，另外一个儿子去找前驱或后继即可。 BST code我们使用内存池来维护整个数据结构 BST代码

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 总览这篇博客将用于整理各种搜索树的数据结构,目前已经整理了BST、AVL、BTree、B+Tree、B*Tree、23Tree、234Tree、TTree、RBTree、LLRBTree、AATree、SplayTree、Treap、无旋Treap、scapegoatTree,VPTree、cartesianTree, 项目地址链接 前置条件基本数据结构：变长数组、栈、队列、字符串的实现(此时暂未实现，使用STL代替，后面有时间会自己实现)内存池机制 树的设计我们设计一个基类让所有的树来继承此基类，然后在看后面会有什么改变，以后再来更新 基类 我们的基类只提供接口，不提供数据类型 tree代码 更新： 搜索树的设计 由于笔者能力有限，设计欠佳，导致后面的空间树、字典树等数据结构无法加入tree中，所以我们在tree的后面加一层search_tree来表示搜索树。 搜索树代码 ...