红黑树

树树: 数据结构中是以二叉堆的模式呈现的如果从链表的观点登程,相当于是放宽了有序的的要求容许两个不同地位的元素有相等的序对于序为n的节点来说,能够指向多个序为n+1的节点: 相应的后者称为前者的孩子前者称为后者的父节点最大的序即为树的高度 0节点的左右两个节点别离为0节点的左子节点和右子节点0节点也是这两个子节点的父节点在一个树中,只有0节点没有父节点.这个节点叫做根节点二叉搜寻树二叉搜寻树: 父节点大于或者等于左子节点及所有子节点父节点小于或者等于右子节点及所有子节点初始化要在二叉搜寻树中查问任意一个值: 最坏的状况就是查问到最上面的节点进行比拟的次数为树的高度 因为这是二叉树,若树的元素个数为n,则现实状况下树的高度不大于log~2~n二叉搜寻树中,每个父节点最多子节点有两个子节点树中任意节点有三个指针: 别离指向父节点,左子节点和右子节点.其中根节点没有父节点 typedef struct TREENODE{ struct TREENODE *father; struct TREENODE *left; struct TREENODE *right; int value;}tNode;在一个二叉搜寻树中,插入新节点: 比拟新节点与以后节点的值如果大于以后节点,则比拟新节点与以后节点右子节点的值如果小于以后节点,则比拟新节点与以后左子节点的值如果下一个将要比拟的节点不存在,就将新节点插入进来 void insertNode(tNode* root, int val) {tNode* new = (tNode*)malloc(sizeof(tNode));new -> value = val;new -> left = NULL;new -> right = NULL;while (true) { if (root -> value < val) if (root -> right != NULL) root = root -> right; else { // 右子节点不存在,则新节点成为右子节点 new -> father = root; root -> right = new; return; // 实现赋值之后函数完结 } else if (root -> !=NULL) root = root -> left else { new -> father = root; root -> left = new; return; }}}生成二叉搜寻树之后,能够将二叉搜寻树打印进去,查看生成的二叉搜寻树是否正确 ...

花了好几天的业余时间，看文章，总算是用C实现了一遍红黑树，次要还是本人C语言程度不够高，调试断点节约了不少工夫，闲话少说 1. 红黑树结构体//这里偷懒就应0代表彩色，1代表红色了typedef struct RBTreeNode { int data; //数据域 int color; //0彩色 1红色 struct RBTreeNode *parent;//父亲结点 struct RBTreeNode *left; //左子结点 struct RBTreeNode *right; //右子结点} RBTreeNode;2. 前序遍历//这里打印了节点的色彩和父节点void preOrderTraverse(RBTreeNode *root){ if (root != NULL) { if (root->parent != NULL) { printf("%d color: %d parent:%d\n", root->data, root->color, root->parent->data); }else{ printf("%d color: %d\n", root->data, root->color); } preOrderTraverse(root->left); preOrderTraverse(root->right); }}3.1 左旋跟AVL树差不多，多了parent相干的操作 /** * 左旋 * parent parent * 8 12 * 4 12 8 50 * 9 50 => 4 9 70 * 70 */RBTreeNode *left_rotation(RBTreeNode *root){ struct RBTreeNode *new_root; new_root = root->right; root->right = new_root->left; //将9的父亲设置为老的root 即8 if (new_root->left != NULL) { new_root->left->parent = root; } //新root的parent即老parent new_root->parent = root->parent; //而后解决老root的parent if (root->parent == NULL) { //老root是根节点 new_root->parent = NULL; }else{ //判断父亲左右 if (new_root->parent->left == root) { new_root->parent->left = new_root; }else{ new_root->parent->right = new_root; } } root->parent = new_root; new_root->left = root; return new_root;}3.2 右旋/** * 右旋 * 8 4 * 4 12 2 8 * 2 6 => 1 6 12 * 1 */RBTreeNode *right_rotation(RBTreeNode *root){ struct RBTreeNode *new_root; new_root = root->left; root->left = new_root->right; //将6的父亲设置为老的root 即8 if (new_root->right != NULL) { new_root->right->parent = root; } //新root的parent即老parent new_root->parent = root->parent; //而后解决老root的parent if (root->parent == NULL) { //老root是根节点 new_root->parent = NULL; }else{ //判断父亲左右 if (new_root->parent->left == root) { new_root->parent->left = new_root; }else{ new_root->parent->right = new_root; } } new_root->right = root; root->parent = new_root; // printf("***本人right_rotation***: \n"); // printfNode(new_root); // printf("***左***: \n"); // printfNode(new_root->left); // printf("***右***: \n"); // printfNode(new_root->right); return new_root;}3.3 代码图解/** * 1.插入的只有一个根节点 * * 8(R) => 8(B) * * 2.1父节点是彩色，啥也不必干 * 8(B) * / => 不变 * 4(R) * * 2.2 父节点是红色,祖父肯定是彩色啦，看叔叔是啥色彩 * * 2.2.1 父节点是祖父节点的左节点 * * 2.2.1.1如果叔叔也是红色 * 将父节点,叔节点设为彩色,将祖父节点设为红色,将祖父节点设为“以后节点”(红色节点)；即，之后递归持续对“以后节点”进行操作 * * 8(B) 8(R) 8(B) * / \ / \ / \ * 4(R) 12(R) => 4(B) 12(B) => 4(B) 12(B) * / / / * 2(R) 2(R) 2(R) * * 2.2.1.2如果叔叔不存在或是彩色 * 2.2.1.2.1新节点在左子树 * 父节点设为彩色,将祖父节点设为红色，对祖父节点右旋 * * 8(B) 8(R) 8(B) * / \ 着色 / \ 对4右旋 / \ * 4(B) 12(B) => 4(R) 12(B) => 2(B) 12(B) * / / / \ * 2(R) 2(B) 1(R) 4(R) * / / * 1(R) 1(R) * * 2.2.1.2.2新节点在右子树 * root与父节点替换 并把父节点设为新root的左节点,即转化为2.2.1.2.1，解决如上 * * 8(B) 8(B) 8(B) 8(B) * / \ 替换 / \ 着色 / \ 对4右旋 / \ * 4(B) 12(B) => 4(B) 12(B) => 4(R) 12(B) => 3(B) 12(B) * / / / / \ * 2(R) 3(R) 3(B) 2(R) 4(R) * \ / / * 3(R) 2(R) 2(R) * * * * 2.2.2 父节点是祖父节点的右节点 * 2.2.2.1如果叔叔也是红色 * 将父节点,叔节点设为彩色,将祖父节点设为红色,将祖父节点设为“以后节点”(红色节点)；即，之后递归持续对“以后节点”进行操作 * * 8(B) 8(R) 8(B) * / \ / \ / \ * 4(R) 12(R) => 4(B) 12(B) => 4(B) 12(B) * \ \ \ * 20(R) 20(R) 20(R) * * 2.2.2.2如果叔叔不存在或是彩色(这里的绘图简化些，其实都一样的) * 2.2.2.2.1新节点在左子树 * root与父节点替换 并把父节点设为新root的右节点,即转化为2.2.2.2.2 * 8(B) 8(B) 8(R) 10(B) * \ 替换 \ 着色 \ 对8右旋 / \ * 12(R) => 10(R) => 10(B) => 8(R) 12(R) * / \ \ * 10(R) 12(R) 12(R) * * 2.2.2.2.2新节点在右子树 * 将父节点设为彩色 将祖父节点设为红色 左旋 * * 8(B) 8(R) 12(B) * \ 着色 \ 对8左旋 / \ * 12(B) => 12(B) => 8(R) 20(R) * \ \ * 20(R) 20(R) * * */4. 自均衡RBTreeNode *rebalance3(RBTreeNode *root, RBTreeNode *rootNode)//返回新的根节点{ //1 插入根节点,只需置黑即可 if (root->parent == NULL) { root->color = 0; } //2 有父节点 if (root->parent != NULL) { //2.1 父节点是彩色，啥也不必干 if (root->parent->color == 0) { //do nothing }else{ //2.2 父节点是红色,祖父肯定是彩色啦，看叔叔是啥色彩 RBTreeNode *parent, *gparent, *uncle; parent = root->parent; gparent = root->parent->parent; int return_flag = 0; if (gparent == rootNode) { return_flag = 1; } //先判断父节点是祖父节点的左节点还是右节点，即叔叔节点是啥 //2.2.1 父节点是祖父节点的左节点 if (parent == gparent->left) { uncle = gparent->right; //2.2.1.1如果叔叔也是红色 if (uncle != NULL && uncle->color == 1) { //1.将父节点设为彩色 parent->color = 0; //2.将叔节点设为彩色 uncle->color = 0; //3.将祖父节点设为红色 gparent->color = 1; //4.将祖父节点设为“以后节点”(红色节点)；即，之后持续对“以后节点”进行操作 return rebalance3(gparent, rootNode); }else{ //2.2.1.2如果叔叔彩色 或不存在 //2.2.1.2.1 root是左节点 if (root == parent->left) { //1.将父节点设为彩色 parent->color = 0; //2.将祖父节点设为红色 gparent->color = 1; gparent = right_rotation(gparent); }else{ //2.2.1.2.2 root是右节点 //1.root与父节点替换 并把父节点设为新root的左节点,即转化为2.2.1.2.1 gparent->left = root; root->parent = gparent; root->left = parent; parent->parent = root; parent->right = NULL; return rebalance3(parent, rootNode); } } }else{ //2.2.2 父节点是祖父节点的右节点 uncle = gparent->left; //2.2.2.1如果叔叔也是红色 if (uncle != NULL && uncle->color == 1) { //1.将父节点设为彩色 parent->color = 0; //2.将叔节点设为彩色 uncle->color = 0; //3.将祖父节点设为红色 gparent->color = 1; //4.将祖父节点设为“以后节点”(红色节点)；即，之后持续对“以后节点”进行操作 return rebalance3(gparent, rootNode); }else{ //2.2.2.2如果叔叔彩色 或不存在 //2.2.2.2.1 root是左节点 if (root == parent->left) { //1.root与父节点替换 并把父节点设为新root的左节点,即转化为2.2.2.2.2 gparent->right = root; root->parent = gparent; root->right = parent; parent->parent = root; parent->left = NULL; return rebalance3(parent, rootNode); }else{ //2.2.2.2.2 root是右节点 //1.将父节点设为彩色 parent->color = 0; //2.将祖父节点设为红色 gparent->color = 1; gparent = left_rotation(gparent); } } } if (return_flag == 1) { return gparent; } } } return rootNode;}5.1 插入（未均衡）RBTreeNode *insert(RBTreeNode *root, int data, RBTreeNode *parent){ if (NULL == root) { return getNode(data, parent); } if (data >= root->data) { root->right = insert(root->right, data, root); }else{ root->left = insert(root->left, data, root); } return root;}5.2 插入(均衡)RBTreeNode *inserRB(RBTreeNode *root, int data, RBTreeNode *parent){ root = insert(root,data,parent); return rebalance3(RBTreeEndNode,root);}6 测试红黑树构建int main(){ struct RBTreeNode *node; //2.2.1.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 2, NULL); printf("***2.2.1.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.1.2.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 2, NULL); node = inserRB(node, 1, NULL); printf("***2.2.1.2.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.1.2.2 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 2, NULL); node = inserRB(node, 3, NULL); printf("***2.2.1.2.2 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.2.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 20, NULL); printf("***2.2.2.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.2.2.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 10, NULL); printf("***2.2.2.2.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.2.2.2 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 20, NULL); printf("***2.2.2.2.2 测试用例 前序***: \n"); preOrderTraverse(node);}测试后果: ...

二叉搜寻树的缺点二叉搜寻树作为数据存储的构造有重要的劣势：能够疾速的查找给定关键字的数据项，并且能够疾速的插入和删除数据项，然而，二叉搜寻树有一个很麻烦的问题：如果插入的数据是有序的数据，比方上面的状况有一棵初始化为9 8 12的二叉树插入上面的数据：7 6 5 4 3 非均衡树：比拟好的二叉搜寻树数据应该是左右均匀分布的然而插入间断数据后，散布的不平均，咱们称这种树为非均衡树对于一颗均衡二叉树来说，插入/查找等操作的效率是O(logN)对于一颗非均衡树，相当于编写了一个链表 树的平衡性为了能以较快的工夫O(logN)来操作一棵树，咱们须要保障树总是均衡的：至多大部分是均衡的，那么工夫复杂度也是靠近O(logN)的也就是说树中每个节点的右边的子孙节点的个数，应该尽可能的等于左边的子孙节点的个数常见的均衡树有哪些？ AVL树：AVL树是较早的一种均衡树，它有些方法保留树的均衡（每个节点多存储了一个额定的数据）因为AVL树是均衡的，所以工夫复杂度也是O(logN)然而，每次插入/删除操作绝对于红黑树效率不高，所以整体效率不如红黑树 红黑树：红黑树也是通过一些个性来放弃树的均衡因为红黑树，所以工夫复杂度也是在O(logN)另外插入/删除等操作，红黑树的性能要优于AVL树，所以当初均衡树的利用根本都是红黑树 红黑树红黑树规定：红黑树，除了合乎二叉搜寻树的根本规定外，还增加了以下个性：【性质1】.节点是红色或彩色【性质2】.根节点是彩色【性质3】.每个叶子节点都是彩色的空节点（NIL节点）【性质4】.每个红色节点的子节点都是彩色（从每个叶子到根的门路上不能有两个间断的红色节点）【性质5】.从任意节点到其每个节点的所有门路都蕴含雷同数目的彩色节点规定很重要，上面练习会用到，下图就是一个红黑树，下面的五点都合乎 红黑树的绝对均衡后面的束缚，确保了红黑树的要害个性：从根到叶子的最长可能门路，不会超过最短可能门路的两倍长后果就是这个树根本是均衡的尽管没有做到相对的均衡，然而能够保障在最坏的状况下，仍然是高效的 为什么能够做到最长门路不超过最短门路的两倍呢？【性质4】决定了门路不能有两个相连的红色节点【性质5】所有门路都有雷同数目的彩色节点这就表明了没有门路能多余任何其余门路的两倍长 插入新节点遇到状况的解决办法插入一个新节点时，有可能树不再均衡，能够通过三种形式的变换，让树保持平衡换色/左旋转/右旋转 变色为了从新合乎红黑树的规定，尝试把红色节点变成彩色，或者把彩色节点变成红色首先须要晓得插入的新节点通常默认为红色节点因为在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规定的（插入9） 而插入彩色节点，必然会导致有一条门路上多了彩色节点，这是很难调整的红色节点有可能导致呈现红红相连的状况，然而这种状况能够通过色彩变换和旋转来调整 左旋转逆时针旋转红黑树的两个节点，使得父节点被本人的有孩子取代，而本人成为本人的左孩子图中，身为右孩子的x取代了a的地位，而a变成了x的左孩子。此为左旋转 右旋转顺时针旋转红黑树的两个节点，使得父节点被本人的左孩子取代，而本人成为本人的右孩子图中，身为左孩子的x取代了a的地位，而a变成x的右孩子 插入操作接下来，讨论一下插入的状况设要插入的节点为N,其父节点为P其祖父节点为G，其父亲的兄弟节点为U(即P和U是同一节点的子节点) 状况一：新节点N位于树的根，没有父节点这种状况下，咱们间接将红色变换成彩色即可，这样满足性质2 状况二新节点的父节点P是彩色性质4没有生效（新节点是红色的），性质5也没有任何问题只管新节点N有两个彩色的叶子节点nil，然而新节点N是红色的，所以通过它的门路中彩色节点的个数仍然雷同，满足性质5（下图省略了nil） 状况三P为红色，U也是红色 操作计划：将P和U变换为彩色，并且将G变换为红色可能呈现的问题然而N的祖父节点G的父节点也可能是红色，这就违反了性质3，能够递归调整色彩然而如果递归调整色彩到了根节点，就须要进行旋转了，这个上面遇到了再解说 状况四N的叔叔U是黑节点，且N是左孩子。简写：父红叔黑祖黑 N是左儿子变换：父黑--祖红--右旋转 状况五N的叔叔U是彩色节点，且N是右孩子。简写：父红叔黑祖黑，N是右孩子变换：以P为根，左旋转将P作为新插入的红色节点思考即可本人（N）变成彩色祖变成红色以祖为根，进行右旋转 实操上面咱们将10，9，8，7，6，5，4，3，2，1顺次插入树中造成红黑树。多图预警。。。。 红黑树的常识就到这里，至于代码实现看下面的图也晓得是十分难的，临时就先不钻研代码，先捋分明逻辑。

map与unordered_map都是c++ stl中的关联容器，两者的应用也都大致相同。不过在底层的实现上，map应用的是红黑树，unordered_map应用的则是hash表。 红黑树红黑树是一种绝对均衡的二叉搜寻树，并且其附加定义如下： 节点有且只有两种色彩，红色和彩色根节点和叶子节点必须是彩色，其中，叶子节点是虚构存在的空节点NULL红色节点的两个子节点必须是彩色任意节点到叶子节点的门路上，必须蕴含雷同数目的彩色节点能够参考一下以下blog：Red-Black Trees 绝对于AVL均衡树，红黑树对于平衡性的要求没有那么高，因为其对于色彩的定义，任意节点左右子树的高度差在一倍之内（最长门路为节点红黑相间，最短门路为节点全黑），因而频繁插入和删除节点时，触发均衡调整的次数更少，均衡调整的过程也更易收敛。 而c++ stl中的map应用红黑树作为底层实现，对于map中的键值，它只有可能比拟大小：如数值、字符串或其它可能反对大小比拟的类就能够。 hash表hash表，其实就是通过肯定的算法：hash函数将原始数据转为一段固定长度的数值（表这个词其实没有具体意义，hash的存储形式有很多，如再链表法，如凋谢地址法的数据结构，表只是对于它们的一种抽象称说）。 具体可见：什么是hash 这里次要答复一下我本人长期的一个误区： 即之前我始终认为hash只实用于key-value这样的数据，并且认为hash表中只存储value，那么依据key的hash值寻找数据时，存在hash抵触的话，就没法晓得以后hash值对应的value数据到底哪个是对应于key的。 其实，hash也能够对于不是key-value这样的数据进行存储，比方就是一系列大量的数值或字符串，咱们能够应用hash算法，而不是简略的数组顺序存储，为的是放慢查找速度；并且对于key-value这样的数据，其实hash表中所存储的不是只有value，而是key-value这个键值对都存储了，这样在有hash抵触的状况下就能依据key值找到真正对应的value。

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异： 从根结点开始查找，把根结点设置为当前结点；若当前结点为空，返回null；若当前结点不为空，用当前结点的key跟查找key作比较；若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；非常简单，但简单不代表它效率不好。正由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为O(2lgN)，也即整颗树刚好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没

平衡：树的左右子树的高度差距在一个可控的范围内 B-TREE 多路搜索树AVL 平衡二叉树: 空树或它的左右两个子树的高度差的绝对值不超过1，左右两个子树都是一颗平衡二叉树。RB-TREE 红黑树: 红黑树属于平衡二叉树，但不是严格的平衡二叉树，相对接近平衡的二叉树， 最大深度<=最小深度的两倍(即没有一条路径比其他路径长出两倍)BST 二叉搜索树(Binary Search Tree):BBST 平衡二叉排序树(Balance Binary Sort Tree)红黑树概念: 红黑树特点: 红黑树应用场景: TreeMap 基于红黑树实现的排序Map，默认按key(实现comparable接口)来比较排序。 TreeMap的增删查改以及统计操作的时间复杂度都为O(logn)TreeSetJDK1.8中 HashMap每个数组节点挂的元素个数超过8 ConcurrentHashMap每个数组节点挂的元素个数超过8红黑树与AVL树对比: 红黑树的查询性能略逊色于AVL树 红黑树放弃了追求完全平衡，追求大致平衡， 红黑树的高度相对更高，因此红黑树的插入和删除性能比AVL效率高

CollectionList(有序,可重复)ArrayList数组，线程不安全。查询：带下标访问数组，O(1)修改：由于arraylist不允许空的空间，当在一个arraylist的中间插入或者删除元素，需要遍历移动插入/删除位置到数组尾部的所有元素。另外arraylist需要扩容时，需要将实际存储的数组元素复制到一个新的数组去，因此一般认为修改的时间复杂度O(N)扩容/minCapacity为原list长度/private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);}private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);}默认情况1.5倍增长Vector数组，线程安全(条件)与ArrayList不同的是使用了同步（Synchronized），基本实现了线程安全对象进行操作时，不加锁的话还是有问题，例如下面的例子public Object deleteLast(Vector v){ int lastIndex = v.size()-1; v.remove(lastIndex);}执行deleteLast操作时如果不加锁，可能会出现remove时size错误扩容默认2倍增长Stack堆栈继承Vector通过push、pop进行入栈，出栈LinkedList双向链表，线程不安全查询，需要遍历链表，时间复杂度O(N)修改，只需要修改1～2个节点的指针地址，时间复杂度O(1)Set(无序,唯一)HashSetHashMap, 线程不安全操作元素时间复杂度, O(1)LinkedHashSetLinkedHashMap，线程不安全public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {… public LinkedHashSet() {super(16, .75f, true);}}//hashset.java中的构造方法HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor);}操作元素 O(1)由于底层结构是LinkedHashMap，可以记录元素之间插入的顺序TreeSetTreeMap, 线程不安全由于是树结构，可以保证数据存储是有序的操作元素时间复杂度，O(logN)Queue队列queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。1、没有实现的阻塞接口的LinkedList： 实现了java.util.Queue接口和java.util.AbstractQueue接口　内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue　PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。 PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。　ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，　ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。2)实现阻塞接口的java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。五个队列所提供的各有不同：ArrayBlockingQueue ：一个由数组支持的有界队列。LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。MapHashMap链表结构，Node结构static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; }JDK 1.8新特性，当节点数大于8时，将链表转换为红黑树static final int TREEIFY_THRESHOLD = 8;if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);过长的链表搜索性能降低，使用红黑树来提高查找性能。hash值计算static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}对key的hash码高16位实现异或a⊕b = (¬a ∧ b) ∨ (a ∧¬b)如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); …插入table时，下标index = (n - 1) & hash在n较小时，hash码的低位的0和1不均匀，容易冲突导致碰撞。而通过上述XOR算法调整后，hash的低16位会变大，从而使得0和1分布更加均匀。计算表容量static final int MAXIMUM_CAPACITY = 1 << 30; public HashMap(int initialCapacity, float loadFactor) { /省略此处代码/ this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);}static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;假设cap=37，则n=36， 100100右移1， 010010，或结果=110110右移2， 001101，或结果=111111右移4， 000011，或结果=111111右移8， 000000，或结果=111111右移16， 000000，或结果=111111结果为63，二进制或操作只有在两数都为0时，才为0，因此通过循环右移，或操作，实际是为了找到n的最高位，并将后面的数字全部全改写为1，从而实现返回大于等于initialCapacity的最小的2的幂。扩容final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({“rawtypes”,“unchecked”}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //遍历旧链表 Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) //单节点 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //树 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { //链表 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //尾部指针hi if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}这段代码的含义是将oldTab[j]中的链表对半拆到newTab[j]和newTab[j + oldCap]if ((e.hash & oldCap) == 0)怎么理解我们知道oldTab中的index = (n - 1) & hash，假设n=8，则newTab中的index = (16-1) & hash，那么在newTab中的index为index或者index + 8，那么e.hash & oldCap == 0 ,hash 必然为 X001000的形态才有可能，也就是说if ((e.hash & oldCap) == 0)代表newindex == index的情况loHead loTail/ hiTail hiHead 这2对指针前面说了if ((e.hash & oldCap) == 0)表示newindex == index，那么lo指针指向的就是此类节点，hi指针指向剩下的节点通过tail指针的移动，实现链表拆分以及各节点next指针的更新HashTableDictionary, 线程安全操作元素时间复杂度, O(1)synchronized 线程安全写入数据public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings(“unchecked”) Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { //遍历链表 if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null;}private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings(“unchecked”) Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++;}扩容遍历，重新计算index，并填入newMapprotected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; for (int i = oldCapacity ; i– > 0 ;) { for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; //反转链表 newMap[index] = e; } }}TreeMap红黑树是平衡二叉树排序树，我们来看下它的特性红黑树特性二叉排序树特性是一棵空树，或者是具有下列性质的二叉树左子树也是二叉排序树，且非空左子树上所有结点的值均小于它的根结点的值右子树也是二叉排序树，且非空右子树上所有结点的值均大于它的根结点的值平衡二叉树特性它是一棵空树或它的左右两个子树的高度差的绝对值不超过1左右两个子树都是一棵平衡二叉树。红黑树的特性:节点是红色或黑色。根节点是黑色。每个叶节点（NIL节点，空节点）是黑色的。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。查找基于递归的思想处理/查找大于等于K的最小节点/final Entry<K,V> getCeilingEntry(K key) { Entry<K,V> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp < 0) { //key < p.key if (p.left != null) p = p.left; else return p; } else if (cmp > 0) { key > p.key if (p.right != null) { p = p.right; } else { //叔节点 Entry<K,V> parent = p.parent; Entry<K,V> ch = p; while (parent != null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } else return p; } return null;}/查找小于等于K的最大节点, 原理类似，省略/final Entry<K,V> getFloorEntry(K key) { …}/查找大于K的最大节点, 原理类似，省略/final Entry<K,V> getHigherEntry(K key) { …}/查找小于K的最大节点, 原理类似，省略/final Entry<K,V> getLowerEntry(K key) { …}恢复平衡插入/删除节点会破坏红黑树的平衡，为了恢复平衡，可以进行2类操作：旋转和着色旋转左旋private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; }}右旋插入节点插入节点总是为红色场景分析情形1: 新节点位于树的根上，没有父节点将新节点(根节点设置为黑色）情形2: 新节点的父节点是黑色无处理情形3:新节点的父节点是红色，分3类情况3A: 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。3B: 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子3C: 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子总结==为了保证红黑树特性5，插入的节点需要是红色====根节点是红色或者黑色，都不影响红黑树特性5，也就是说当父节点和叔节点均为红色时，可以通过将互换祖父与父、叔节点的颜色来上朔不平衡，并最终通过将根节点从红色设置为黑色来解决不平衡====当叔节点为黑色，父节点为红色时，按照上述思路将父节点与祖父节点颜色互换后，必然会使得当前节点所在的子树黑色节点过多而影响红黑树特性5，因此需要通过旋转将黑色节点向相反方向转移，以平衡根的两侧==3A当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。处理思路:父节点与叔节点变黑色祖父节点变红色当前节点转换为祖父节点，迭代处理graph TD1[祖父红]–>2[父黑]1–>3[叔黑]2–>4{新红}2–>5[兄]3B当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子 处理思路:左旋/右旋父节点后续操作见3C3C当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子 处理思路父节点设置为黑色祖父节点设置为红色右旋/左旋祖父节点private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; //新插入的节点为红色 while (x != null && x != root && x.parent.color == RED) { // x的父节点 == x的父-父-左子节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); // y为x的叔节点 if (colorOf(y) == RED) { //叔节点为红色, 3A setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { //叔节点为黑色 if (x == rightOf(parentOf(x))) { //3B x = parentOf(x); rotateLeft(x); } //3C setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //3A setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { //3C x = parentOf(x); rotateRight(x); } //3B setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK;}删除节点情况分析被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况①"进行处理；若只有一个儿子，则按"情况② “进行处理。private void deleteEntry(Entry<K,V> p) { modCount++; size–; // 情况3 将p的值赋予后继节点s，并转换为删除s if (p.left != null && p.right != null) { Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } // 情况2 Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { // Link replacement to parent replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. p.left = p.right = p.parent = null; // Fix replacement if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { root = null; //p是根节点 } else { //情况1 if (p.color == BLACK) fixAfterDeletion(p); if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } }}重新平衡删除节点x，根据上文分析，x有0或1个子节点x是红色节点，那么删除它不会破坏平衡如果x是黑色4A 兄节点为红色4B 兄节点的两个子节点均为黑色4C 兄节点的远端子节点为黑色，另一个为红色或无4D 兄节点的远端子节点为红色，另一个为红色或无兄节点及其子树的黑色节点应该比X多一个4A 兄节点为红色处理方法：兄节点设置为黑色父节点设置为红色左旋/右旋父节点，变形为B/C/D情况4B 兄节点的两个子节点均为黑色处理方法：兄节点设置为红色x设置为父节点，上溯不平衡4C 远端侄节点为黑色，另一个为红色或无处理方法近端侄节点设置为黑色兄节点设置为红色右旋/左旋兄节点转换为4D处理4D 兄节点为黑色，远端侄节点为红色，一个为红色或无处理方法将父节点的颜色赋予兄节点将父节点设置为黑色将远端侄节点的颜色设置为黑色左旋父节点 ...

前言网上有非常多的关于红黑树理论的描述，本文的重点将不在于此，但是会在文中给出优秀文章的链接。对红黑树不了解的建议先阅读文章再看实现。本红黑树实现不支持多线程环境。因为删除操作灰常复杂，所以后续更新。源码在文末可以查看。参考链接https://www.geeksforgeeks.org…https://www.geeksforgeeks.org...http://www.codebytes.in/2014/…https://blog.csdn.net/eson_15…数据结构定义的红黑树的节点如下：private static class Node<T>{ static final int RED = 0; static final int BLACK = 1; T value; int color = RED; Node<T> leftChild; Node<T> rightChild; Node<T> parent; Node(T value) { this.value = value; } boolean isRoot() { return this.parent == null; } boolean isLeaf() { return this.leftChild == null && this.rightChild == null; } boolean isLeftChild() { return this.parent != null && this.parent.leftChild == this; } boolean isRightChild() { return this.parent != null && this.parent.rightChild == this; } Node<T> getUncle() { if(this.parent == null || this.parent.parent == null) return null; if(this.parent.isLeftChild()) { return this.parent.parent.rightChild; } else { return this.parent.parent.leftChild; } } Node<T> getSibling() { if(this.parent == null) return null; return this.parent.leftChild == this ? this.parent.rightChild : this.parent.leftChild; } boolean isRed() { return this.color == RED; } boolean isBlack() { return this.color == BLACK; } }该Node作为RedBlackTree的一个内部类存在。除了和普通的TreeNode相同给的左子节点和右子节点的引用，还额外引用了父节点，方便我们回溯。除此以外还封装了一些方法，比如获得自己的祖父节点，叔叔节点以及兄弟节点等。旋转操作因为额外持有了父节点，所以在执行旋转操作的时候需要额外注意空指针以及不恰当的赋值带来的循环引用。左旋和右旋的代码如下： private void rotateLeft(Node<T> node) { if(node == null || node.rightChild == null) return; Node<T> parent = node.parent; Node<T> rightChild = node.rightChild; if(rightChild.leftChild != null) { node.rightChild = rightChild.leftChild; node.rightChild.parent = node; } else { node.rightChild = null; } rightChild.leftChild = node; node.parent = rightChild; if(parent != null) { rightChild.parent = parent; if(node == parent.leftChild) { parent.leftChild = rightChild; } else { parent.rightChild = rightChild; } } else { rightChild.parent = null; root = rightChild; } } private void rotateRight(Node<T> node) { if(node == null || node.leftChild == null) return; Node<T> parent = node.parent; Node<T> leftChild = node.leftChild; if(leftChild.rightChild != null) { node.leftChild = leftChild.rightChild; node.leftChild.parent = node; } else { node.leftChild = null; } leftChild.rightChild = node; node.parent = leftChild; if(parent != null) { leftChild.parent = parent; if(node == parent.leftChild) { parent.leftChild = leftChild; } else { parent.rightChild = leftChild; } } else { leftChild.parent = null; root = leftChild; } }插入我们知道，在红黑树中插入一个节点相当于在一个二叉搜索树中插入一个节点。因此该节点一定是作为叶节点而插入的。二者唯一的不同在于，默认插入的节点为红色，我们需要重新调整树结构从而确保红黑树重新达到平衡。 @Override public void insert(T t) { Node<T> newNode = new Node<T>(t); if(root == null) { root = newNode; root.color = Node.BLACK; size++; } else { Node<T> tmp = root; while(tmp != null) { if(tmp.value.equals(t)) { newNode = tmp; break; } else if(tmp.value.compareTo(t) < 0) { if(tmp.rightChild == null) { tmp.rightChild = newNode; newNode.parent = tmp; size++; break; } else { tmp = tmp.rightChild; } } else { if(tmp.leftChild == null) { tmp.leftChild = newNode; newNode.parent = tmp; size++; break; } else { tmp = tmp.leftChild; } } } } adjust(newNode); } private void adjust(Node<T> node) { if(node.isRoot()) { node.color = Node.BLACK; return; } else if(node.parent.isRed()) { //肯定存在祖父节点，因为根节点必须为黑色 Node<T> parent = node.parent; Node<T> grandParent = node.parent.parent; Node<T> uncle = node.getUncle(); if(uncle!=null && uncle.isRed()) { parent.color = Node.BLACK; uncle.color = Node.BLACK; grandParent.color = Node.RED; adjust(grandParent); } else { if(node.isLeftChild() && node.parent.isLeftChild()) { parent.color = Node.BLACK; grandParent.color = Node.RED; rotateRight(grandParent); } else if(node.isRightChild() && node.parent.isRightChild()) { parent.color = Node.BLACK; grandParent.color = Node.RED; rotateLeft(grandParent); } else if(node.isLeftChild() && node.parent.isRightChild()) { node.color = Node.BLACK; grandParent.color = Node.RED; rotateRight(parent); rotateLeft(grandParent); } else { node.color = Node.BLACK; grandParent.color = Node.RED; rotateLeft(parent); rotateRight(grandParent); } } } }删除待更新源码public interface RedBlackTreeADT<T extends Comparable<T>> { boolean contains(T t); void insert(T t); void delete(T t); int size(); }public class RedBlackTree<T extends Comparable<T>> implements RedBlackTreeADT<T>{ private int size; private Node<T> root; private static class Node<T>{ static final int RED = 0; static final int BLACK = 1; T value; int color = RED; Node<T> leftChild; Node<T> rightChild; Node<T> parent; Node(T value) { this.value = value; } boolean isRoot() { return this.parent == null; } boolean isLeaf() { return this.leftChild == null && this.rightChild == null; } boolean isLeftChild() { return this.parent != null && this.parent.leftChild == this; } boolean isRightChild() { return this.parent != null && this.parent.rightChild == this; } Node<T> getUncle() { if(this.parent == null || this.parent.parent == null) return null; if(this.parent.isLeftChild()) { return this.parent.parent.rightChild; } else { return this.parent.parent.leftChild; } } Node<T> getSibling() { if(this.parent == null) return null; return this.parent.leftChild == this ? this.parent.rightChild : this.parent.leftChild; } boolean isRed() { return this.color == RED; } boolean isBlack() { return this.color == BLACK; } } @Override public boolean contains(T t) { Node<T> tmp = root; while(tmp != null) { int cmp = tmp.value.compareTo(t); if(cmp == 0) { return true; } else if (cmp < 0) { tmp = tmp.rightChild; } else { tmp = tmp.leftChild; } } return false; } @Override public void insert(T t) { Node<T> newNode = new Node<T>(t); if(root == null) { root = newNode; root.color = Node.BLACK; size++; } else { Node<T> tmp = root; while(tmp != null) { if(tmp.value.equals(t)) { newNode = tmp; break; } else if(tmp.value.compareTo(t) < 0) { if(tmp.rightChild == null) { tmp.rightChild = newNode; newNode.parent = tmp; size++; break; } else { tmp = tmp.rightChild; } } else { if(tmp.leftChild == null) { tmp.leftChild = newNode; newNode.parent = tmp; size++; break; } else { tmp = tmp.leftChild; } } } } adjust(newNode); } private void adjust(Node<T> node) { if(node.isRoot()) { node.color = Node.BLACK; return; } else if(node.parent.isRed()) { //肯定存在祖父节点，因为根节点必须为黑色 Node<T> parent = node.parent; Node<T> grandParent = node.parent.parent; Node<T> uncle = node.getUncle(); if(uncle!=null && uncle.isRed()) { parent.color = Node.BLACK; uncle.color = Node.BLACK; grandParent.color = Node.RED; adjust(grandParent); } else { if(node.isLeftChild() && node.parent.isLeftChild()) { parent.color = Node.BLACK; grandParent.color = Node.RED; rotateRight(grandParent); } else if(node.isRightChild() && node.parent.isRightChild()) { parent.color = Node.BLACK; grandParent.color = Node.RED; rotateLeft(grandParent); } else if(node.isLeftChild() && node.parent.isRightChild()) { node.color = Node.BLACK; grandParent.color = Node.RED; rotateRight(parent); rotateLeft(grandParent); } else { node.color = Node.BLACK; grandParent.color = Node.RED; rotateLeft(parent); rotateRight(grandParent); } } } } private void rotateLeft(Node<T> node) { if(node == null || node.rightChild == null) return; Node<T> parent = node.parent; Node<T> rightChild = node.rightChild; if(rightChild.leftChild != null) { node.rightChild = rightChild.leftChild; node.rightChild.parent = node; } else { node.rightChild = null; } rightChild.leftChild = node; node.parent = rightChild; if(parent != null) { rightChild.parent = parent; if(node == parent.leftChild) { parent.leftChild = rightChild; } else { parent.rightChild = rightChild; } } else { rightChild.parent = null; root = rightChild; } } private void rotateRight(Node<T> node) { if(node == null || node.leftChild == null) return; Node<T> parent = node.parent; Node<T> leftChild = node.leftChild; if(leftChild.rightChild != null) { node.leftChild = leftChild.rightChild; node.leftChild.parent = node; } else { node.leftChild = null; } leftChild.rightChild = node; node.parent = leftChild; if(parent != null) { leftChild.parent = parent; if(node == parent.leftChild) { parent.leftChild = leftChild; } else { parent.rightChild = leftChild; } } else { leftChild.parent = null; root = leftChild; } } @Override public int size() { return size; } public void printTree() { this.printTree(this.root); } private void printTree(Node<T> root) { if(root == null) { System.out.print(“nil(BLACK)”); return; } printTree(root.leftChild); System.out.print(root.value + “(” + (root.color==Node.RED ? “RED” : “BLACK”) + “)”); printTree(root.rightChild); } @Override public void delete(T t) { // TODO Auto-generated method stub }}有任何问题，欢迎指出！ ...