nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial red black treered black tree定义红黑树是一种平衡树，他满足下面的性质 1.节点是红色或黑色。2.根是黑色。3.所有叶子都是黑色（叶子是NIL节点）。4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 red black...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # T tree T tree 是一颗二叉树，他和avl tree有着一定的联系,总所周知，avl树为一颗二叉树，利用其中序维护信息，利用子树高度维护平衡。我们借此修改一下，我们尝试让avl树的每个节点维护多个信息[信息序列]，于是T tree就出现了。T tree是一颗二叉树，每个节点维护一个有序序列，用T 树的中序遍历方式，将其节点维护的序列依次相连即成为了我们维护的信息。 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...

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

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial binary search treeBST是二叉搜索树，满足中序遍历是一个有序的序列,他是最最基础的二叉树，他不一定平衡， BST insert插入的时候，在树上递归插入，比当前节点大就向右边走，否则向左走 BST search查找的时候，同上 BST...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 总览这篇博客将用于整理各种搜索树的数据结构,目前已经整理了BST、AVL、BTree、B+Tree、B*Tree、23Tree、234Tree、TTree、RBTree、LLRBTree、AATree、SplayTree、Treap、无旋Treap、scapegoatTree,VPTree、cartesianTree, 项目地址链接 前置条件基本数据结构：变长数组、栈、队列、字符串的实现(此时暂未实现...