前言要理解红黑树，需要掌握以下知识二分查找算法二分查找树自平衡树（AVL树和红黑树）基于二分查找算法，设计了二分查找树。为了弥补二叉搜索树的不足，出现了一些自平衡树，如AVL树、红黑树等，二分搜索算法最多只需要32次就可以在其中找到指定的数据40亿条数据，这就是二分查找算法的魅力所在。二分查找算法（BinarySearchAlgorithm，又称二分查找算法）是一种在有序数组中查找特定元素的查找算法。注意排序数组的前提。下图中找4，从中间的元素开始找4<7，从左边找4>3，从右边找4<6，找到元素。二分查找算法的时间和空间复杂度，\({n}\)为数组长度。平均时间复杂度\({O(\logn)}\)最差时间复杂度\({O(\logn)}\)最优时间复杂度\({O(1)}\)循环空间复杂度\({O(1)}\)RecursiveSpaceComplexity\({O(\logn)}\)Java递归实现二分查找。publicstaticintbinarySearch(int[]arr,intstart,intend,inthkey){if(start>end){return-1;}intmid=start+(end-start)/2;//防止溢出if(arr[mid]>hkey){returnbinarySearch(arr,start,mid-1,hkey);}if(arr[mid]hkey){end=mid-1;}elseif(arr[mid]1){if(height(z.right.right)>height(z.right.left)){z=rotateLeft(z);}else{z.right=rotateRight(z.right);z=向左旋转(z);}}elseif(balance<-1){if(height(z.left.left)>height(z.left.right)){z=rotateRight(z);}else{z.left=rotateLeft(z.left);z=向右旋转(z);}}返回z；}https://github.com/eugenp/tut...红黑树属性红黑树中的每个节点都有一个颜色属性。每次插入或删除元素时，都会重新着色和旋转以达到平衡。红黑树属于二叉搜索树，它包含了二叉搜索树的属性，还包括以下属性：每个节点要么是黑色，要么是红色。所有叶节点(NIL)都被视为黑色。每个红色节点的两个子节点都必须是黑色的（不能连续出现两个红色节点）。从根到叶节点(NIL)的每条路径都包含相同数量的黑色节点。SearchSearch不会破坏树的平衡，逻辑也比较简单，通常有以下几个步骤。从根节点开始查找，设置根节点为当前节点；如果当前节点为空，则返回null；如果当前节点不为空，则查找关键字小于当前节点关键字，将左子节点设置为当前节点。当前节点不为空，查找关键字大于当前节点关键字，右子节点设置为当前节点。当前节点不为空，搜索关键字等于当前节点关键字，返回当前节点。代码实现可以参考Java中的TreeMap。项p=root;while(p!=null){intcmp=k.compareTo(p.key);如果(cmp<0){p=p.left;}elseif(cmp>0){p=p.right;}else{返回p;}}返回空值；Insert插入操作分为两部分：一是寻找插入位置；另一种是插入后自平衡。将根节点赋值给当前节点，循环寻找插入位置的节点；当搜索关键字等于当前节点关键字时，更新存储在节点中的值并返回；当搜索关键字小于当前节点关键字时，将当前节点的左子节点设置为当前节点；当搜索关键字大于当前节点关键字时，将当前节点的右子节点设置为当前节点节点;循环结束后，构造一个新节点作为当前节点的左（右）子节点；通过旋转和改变颜色来实现自我平衡。代码实现可以参考Java中的TreeMap。条目t=root;条目父级；国际运动会；做{父母=t;cmp=k.compareTo(t.key);如果(cmp<0){t=t.left;}elseif(cmp>0){t=t.right;}else{returnt.setValue(value);//更新节点的值，返回}}while(t!=null);条目e=新条目<>(键,值,父级);如果（cmp<0）{parent.left=e;}else{parent.right=e;}fixAfterInsertion(e);//通过旋转变色自平衡插入场景分析根节点为空，设置插入节点为根节点，设置为黑色；插入节点的key已经存在，只需要更新插入值，不需要自平衡；插入节点的父节点为黑色，直接插入，不需要Self-balancing；插入节点的父节点为红色。场景4，节点插入后出现了两个连续的红色节点，需要重新着色旋转。这里有很多情况，详见下文。首先声明下一个节点关系，祖先节点（10），叔节点（20），父节点（9），插入节点（8）。通常，通过判断插入节点的叔叔节点来确定合适的平衡操作。叔叔节点存在并且是红色的。先找到位置，插入节点8；将父节点9和叔节点20变为黑色，将祖父节点10变为红色；祖父节点10是根节点，所以它又变黑了。叔节点不存在或为黑，父节点为祖先节点的左节点，插入节点为父节点的左子节点。先找到位置，插入节点7；向右旋转祖先节点9；将父节点8变为黑色，将祖先节点9变为红色；叔节点不存在或为黑，父节点为祖先节点的左节点，插入节点为父节点的右孩子。先找到位置，插入节点8；将父节点7向左旋转；向右旋转祖先节点9；将插入节点8变为黑色，将祖先节点9变为红色；叔节点不存在或为黑，父节点为祖先节点的右节点，插入节点为父节点的右子节点。先找到位置，插入节点10；将祖先节点8向左旋转；将父节点9变为黑色，将祖先节点8变为红色；叔节点不存在或为黑，父节点为祖先节点的右节点，插入节点为父节点的左子节点。先找到位置，插入节点9；将父节点向右旋转10；将祖先节点8向左旋转；将插入节点9变为黑色，将祖先节点8变为红色；delete和delete操作分为两部分：一是找到节点delete；2删除后自平衡。删除一个节点后，需要找到一个节点来替换被删除的位置。根据二叉搜索树的性质，删除一个节点后，删除的节点可以用左子树中的最大值或右子树中的最小值代替。如果删除的节点没有子节点，可以直接删除，不替换；如果只有一个子节点，则替换为该子节点。考虑一些删除场景，使用下面的可视化工具模拟场景。https://www.cs.csubak.edu/~ms...ReplacingNodesandDeletingNodes其中一个红色节点找到并删除节点3，将其删除；节点2替换被删除的位置，为删除节点3变成黑色。替换节点和被删除节点都是黑色，其兄弟节点为黑色，兄弟节点的子节点至少有一个红色。替换节点和删除节点均为黑色，其兄弟节点为黑色，兄弟节点的子节点至少有一个红色。替换节点和删除节点均为黑色，其兄弟节点为黑色，兄弟节点的两个子节点均为黑色。替换和删除的节点是黑色的，它们的兄弟节点是红色的。AVL树和红黑树的比较下面分别是AVL树和红黑树存储的[1-10]张图片。可以看出AVL树更加严格的平衡，导致查询速度更快。为了保持严格的平衡，频繁轮换会有性能损失。与严格的AVL树相比，红黑树的旋转次数更少。
