申请专利的网站,青岛房产网站,为什么做这个网站反馈问题,哪学网页设计引言
二叉搜索树#xff08;Binary Search Tree#xff0c;BST#xff09;是一种特殊的二叉树结构#xff0c;每个节点的左子树节点值小于根节点值#xff0c;而右子树节点值大于根节点值。二叉搜索树在计算机科学中有着广泛的应用#xff0c;尤其在动态查找表和优先队列…引言
二叉搜索树Binary Search TreeBST是一种特殊的二叉树结构每个节点的左子树节点值小于根节点值而右子树节点值大于根节点值。二叉搜索树在计算机科学中有着广泛的应用尤其在动态查找表和优先队列的实现中。本文将详细介绍二叉搜索树的定义、基本操作及平衡二叉树AVL树和红黑树。
二叉搜索树的定义和操作
定义
二叉搜索树是一种节点值满足特定排序的二叉树定义如下
每个节点都有一个值。左子树中所有节点的值都小于根节点的值。右子树中所有节点的值都大于根节点的值。左右子树也分别是二叉搜索树。
基本操作
插入操作
插入操作是向二叉搜索树中添加一个新节点。根据新节点的值与当前节点的值比较决定插入左子树或右子树。以下是插入操作的代码示例
class TreeNode {int value;TreeNode left, right;// 构造函数TreeNode(int item) {value item;left right null;}
}class BinarySearchTree {TreeNode root;BinarySearchTree() {root null;}// 插入值到二叉搜索树void insert(int value) {root insertRec(root, value);}// 递归方式插入值TreeNode insertRec(TreeNode root, int value) {// 如果树为空则创建新节点if (root null) {root new TreeNode(value);return root;}// 如果值小于根节点则插入左子树if (value root.value)root.left insertRec(root.left, value);// 如果值大于根节点则插入右子树else if (value root.value)root.right insertRec(root.right, value);// 返回未变更的节点指针return root;}// 中序遍历打印树void inorder() {inorderRec(root);}// 递归方式中序遍历树void inorderRec(TreeNode root) {if (root ! null) {inorderRec(root.left);System.out.print(root.value );inorderRec(root.right);}}// 测试插入操作public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.insert(50);tree.insert(30);tree.insert(20);tree.insert(40);tree.insert(70);tree.insert(60);tree.insert(80);// 打印插入后的树System.out.print(中序遍历结果: );tree.inorder(); // 输出20 30 40 50 60 70 80 }
}插入操作图解
初始化一个空树。插入第一个值 50成为根节点。插入值 30比 50 小插入到 50 的左子树。插入值 20比 30 小插入到 30 的左子树。插入值 40比 30 大插入到 30 的右子树。插入值 70比 50 大插入到 50 的右子树。插入值 60比 70 小插入到 70 的左子树。插入值 80比 70 大插入到 70 的右子树。 50/ \30 70/ \ / \
20 40 60 80#mermaid-svg-0NqS8JUjJmFpPME0 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 .error-icon{fill:#552222;}#mermaid-svg-0NqS8JUjJmFpPME0 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-0NqS8JUjJmFpPME0 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-0NqS8JUjJmFpPME0 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-0NqS8JUjJmFpPME0 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-0NqS8JUjJmFpPME0 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-0NqS8JUjJmFpPME0 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-0NqS8JUjJmFpPME0 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-0NqS8JUjJmFpPME0 .marker.cross{stroke:#333333;}#mermaid-svg-0NqS8JUjJmFpPME0 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-0NqS8JUjJmFpPME0 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 .cluster-label text{fill:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 .cluster-label span{color:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 .label text,#mermaid-svg-0NqS8JUjJmFpPME0 span{fill:#333;color:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 .node rect,#mermaid-svg-0NqS8JUjJmFpPME0 .node circle,#mermaid-svg-0NqS8JUjJmFpPME0 .node ellipse,#mermaid-svg-0NqS8JUjJmFpPME0 .node polygon,#mermaid-svg-0NqS8JUjJmFpPME0 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-0NqS8JUjJmFpPME0 .node .label{text-align:center;}#mermaid-svg-0NqS8JUjJmFpPME0 .node.clickable{cursor:pointer;}#mermaid-svg-0NqS8JUjJmFpPME0 .arrowheadPath{fill:#333333;}#mermaid-svg-0NqS8JUjJmFpPME0 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-0NqS8JUjJmFpPME0 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-0NqS8JUjJmFpPME0 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-0NqS8JUjJmFpPME0 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-0NqS8JUjJmFpPME0 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-0NqS8JUjJmFpPME0 .cluster text{fill:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 .cluster span{color:#333;}#mermaid-svg-0NqS8JUjJmFpPME0 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-0NqS8JUjJmFpPME0 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 20 30 40 50 60 70 80 删除操作
删除操作是从二叉搜索树中移除一个节点。根据要删除节点的位置及其子节点情况进行相应处理。以下是删除操作的代码示例
class BinarySearchTree {TreeNode root;BinarySearchTree() {root null;}// 删除指定值的节点void deleteKey(int value) {root deleteRec(root, value);}// 递归方式删除值TreeNode deleteRec(TreeNode root, int value) {// 基本情况树为空if (root null) return root;// 递归查找要删除的节点if (value root.value)root.left deleteRec(root.left, value);else if (value root.value)root.right deleteRec(root.right, value);else {// 节点只有一个子节点或没有子节点if (root.left null)return root.right;else if (root.right null)return root.left;// 节点有两个子节点获取右子树中最小值root.value minValue(root.right);// 递归删除右子树中的最小值节点root.right deleteRec(root.right, root.value);}return root;}// 查找最小值int minValue(TreeNode root) {int minValue root.value;while (root.left ! null) {minValue root.left.value;root root.left;}return minValue;}// 中序遍历打印树void inorder() {inorderRec(root);}// 递归方式中序遍历树void inorderRec(TreeNode root) {if (root ! null) {inorderRec(root.left);System.out.print(root.value );inorderRec(root.right);}}// 测试删除操作public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.insert(50);tree.insert(30);tree.insert(20);tree.insert(40);tree.insert(70);tree.insert(60);tree.insert(80);System.out.println(删除前的树);tree.inorder(); // 输出20 30 40 50 60 70 80 tree.deleteKey(20);System.out.println(\n删除20后的树);tree.inorder(); // 输出30 40 50 60 70 80 tree.deleteKey(30);System.out.println(\n删除30后的树);tree.inorder(); // 输出40 50 60 70 80 tree.deleteKey(50);System.out.println(\n删除50后的树);tree.inorder(); // 输出40 60 70 80 }
}删除操作图解
假设我们要从上面的树中删除值 50、30 和 20
删除 20节点 20 没有子节点直接删除。删除 30节点 30 有一个子节点 40用 40 替换 30。删除 50节点 50 有两个子节点用其右子树的最小值 60 替换 50然后删除 60。
删除前50/ \30 70/ \ / \
20 40 60 80删除 20 后50/ \30 70\ / \40 60 80删除 30 后50/ \40 70/ \60 80删除 50 后60/ \40 70\80#mermaid-svg-JJyJrZcIvuwgrvEp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp .error-icon{fill:#552222;}#mermaid-svg-JJyJrZcIvuwgrvEp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-JJyJrZcIvuwgrvEp .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-JJyJrZcIvuwgrvEp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-JJyJrZcIvuwgrvEp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-JJyJrZcIvuwgrvEp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-JJyJrZcIvuwgrvEp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-JJyJrZcIvuwgrvEp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-JJyJrZcIvuwgrvEp .marker.cross{stroke:#333333;}#mermaid-svg-JJyJrZcIvuwgrvEp svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-JJyJrZcIvuwgrvEp .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp .cluster-label text{fill:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp .cluster-label span{color:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp .label text,#mermaid-svg-JJyJrZcIvuwgrvEp span{fill:#333;color:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp .node rect,#mermaid-svg-JJyJrZcIvuwgrvEp .node circle,#mermaid-svg-JJyJrZcIvuwgrvEp .node ellipse,#mermaid-svg-JJyJrZcIvuwgrvEp .node polygon,#mermaid-svg-JJyJrZcIvuwgrvEp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-JJyJrZcIvuwgrvEp .node .label{text-align:center;}#mermaid-svg-JJyJrZcIvuwgrvEp .node.clickable{cursor:pointer;}#mermaid-svg-JJyJrZcIvuwgrvEp .arrowheadPath{fill:#333333;}#mermaid-svg-JJyJrZcIvuwgrvEp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-JJyJrZcIvuwgrvEp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-JJyJrZcIvuwgrvEp .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-JJyJrZcIvuwgrvEp .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-JJyJrZcIvuwgrvEp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-JJyJrZcIvuwgrvEp .cluster text{fill:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp .cluster span{color:#333;}#mermaid-svg-JJyJrZcIvuwgrvEp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-JJyJrZcIvuwgrvEp :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 删除前 50 30 70 20 40 60 80 删除20后 50 30 70 40 60 80 删除30后 50 40 70 60 80 删除50后 60 40 70 80 查找操作
查找操作是搜索二叉搜索树中是否存在某个特定值。根据目标值与当前节点值比较决定在左子树或右子树中继续查找。以下是查找操作的代码示例
class BinarySearchTree {TreeNode root;BinarySearchTree() {root null;}// 查找指定值是否存在boolean search(int value) {return searchRec(root, value);}// 递归方式查找值boolean searchRec(TreeNode root, int value) {// 基本情况树为空或值为根节点值if (root null || root.value value) return root ! null;// 值小于根节点值则在左子树中查找if (value root.value)return searchRec(root.left, value);// 值大于根节点值则在右子树中查找return searchRec(root.right, value);}// 插入值到二叉查找树void insert(int value) {root insertRec(root, value);}// 递归方式插入值TreeNode insertRec(TreeNode root, int value) {// 如果树为空则创建新节点if (root null) {root new TreeNode(value);return root;}// 如果值小于根节点则插入左子树if (value root.value)root.left insertRec(root.left, value);// 如果值大于根节点则插入右子树else if (value root.value)root.right insertRec(root.right, value);// 返回未变更的节点指针return root;}// 测试查找操作public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.insert(50);tree.insert(30);tree.insert(20);tree.insert(40);tree.insert(70);tree.insert(60);tree.insert(80);// 测试查找操作System.out.println(tree.search(50)); // 输出trueSystem.out.println(tree.search(90)); // 输出false}
}查找操作图解
假设我们在上面的树中查找值 50 和 90
查找 50从根节点开始50 正是根节点值查找成功。查找 90从根节点 50 开始90 大于 50查找右子树。然后 90 大于 70查找右子树。接着 90 大于 80发现右子树为空查找失败。 #mermaid-svg-etntd5lqM2mIb3fl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-etntd5lqM2mIb3fl .error-icon{fill:#552222;}#mermaid-svg-etntd5lqM2mIb3fl .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-etntd5lqM2mIb3fl .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-etntd5lqM2mIb3fl .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-etntd5lqM2mIb3fl .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-etntd5lqM2mIb3fl .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-etntd5lqM2mIb3fl .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-etntd5lqM2mIb3fl .marker{fill:#333333;stroke:#333333;}#mermaid-svg-etntd5lqM2mIb3fl .marker.cross{stroke:#333333;}#mermaid-svg-etntd5lqM2mIb3fl svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-etntd5lqM2mIb3fl .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-etntd5lqM2mIb3fl .cluster-label text{fill:#333;}#mermaid-svg-etntd5lqM2mIb3fl .cluster-label span{color:#333;}#mermaid-svg-etntd5lqM2mIb3fl .label text,#mermaid-svg-etntd5lqM2mIb3fl span{fill:#333;color:#333;}#mermaid-svg-etntd5lqM2mIb3fl .node rect,#mermaid-svg-etntd5lqM2mIb3fl .node circle,#mermaid-svg-etntd5lqM2mIb3fl .node ellipse,#mermaid-svg-etntd5lqM2mIb3fl .node polygon,#mermaid-svg-etntd5lqM2mIb3fl .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-etntd5lqM2mIb3fl .node .label{text-align:center;}#mermaid-svg-etntd5lqM2mIb3fl .node.clickable{cursor:pointer;}#mermaid-svg-etntd5lqM2mIb3fl .arrowheadPath{fill:#333333;}#mermaid-svg-etntd5lqM2mIb3fl .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-etntd5lqM2mIb3fl .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-etntd5lqM2mIb3fl .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-etntd5lqM2mIb3fl .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-etntd5lqM2mIb3fl .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-etntd5lqM2mIb3fl .cluster text{fill:#333;}#mermaid-svg-etntd5lqM2mIb3fl .cluster span{color:#333;}#mermaid-svg-etntd5lqM2mIb3fl div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-etntd5lqM2mIb3fl :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 50 30 70 20 40 60 80 查找50 查找90 null 平衡二叉树
平衡二叉树是一类特殊的二叉搜索树通过自动调整树的结构使树的高度保持在较低水平从而提高查找、插入和删除操作的效率。常见的平衡二叉树有 AVL 树和红黑树。
AVL 树
AVL 树是一种自平衡二叉搜索树它的每个节点都需要满足以下平衡条件任意节点的左右子树高度差不超过 1。AVL 树通过旋转操作来保持平衡。
AVL 树的旋转操作
右旋Right Rotation左旋Left Rotation左右旋Left-Right Rotation右左旋Right-Left Rotation #mermaid-svg-kGZ84yyTsdEoNgP1 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .error-icon{fill:#552222;}#mermaid-svg-kGZ84yyTsdEoNgP1 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-kGZ84yyTsdEoNgP1 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .marker.cross{stroke:#333333;}#mermaid-svg-kGZ84yyTsdEoNgP1 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-kGZ84yyTsdEoNgP1 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .cluster-label text{fill:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .cluster-label span{color:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .label text,#mermaid-svg-kGZ84yyTsdEoNgP1 span{fill:#333;color:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .node rect,#mermaid-svg-kGZ84yyTsdEoNgP1 .node circle,#mermaid-svg-kGZ84yyTsdEoNgP1 .node ellipse,#mermaid-svg-kGZ84yyTsdEoNgP1 .node polygon,#mermaid-svg-kGZ84yyTsdEoNgP1 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-kGZ84yyTsdEoNgP1 .node .label{text-align:center;}#mermaid-svg-kGZ84yyTsdEoNgP1 .node.clickable{cursor:pointer;}#mermaid-svg-kGZ84yyTsdEoNgP1 .arrowheadPath{fill:#333333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-kGZ84yyTsdEoNgP1 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-kGZ84yyTsdEoNgP1 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-kGZ84yyTsdEoNgP1 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-kGZ84yyTsdEoNgP1 .cluster text{fill:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 .cluster span{color:#333;}#mermaid-svg-kGZ84yyTsdEoNgP1 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-kGZ84yyTsdEoNgP1 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 右旋 左旋 左右旋 右左旋 红黑树
红黑树是一种自平衡二叉搜索树每个节点都有颜色属性红色或黑色并且需要满足以下性质
节点是红色或黑色。根节点是黑色。每个叶节点NIL 节点是黑色。如果一个节点是红色则它的两个子节点都是黑色。从一个节点到该节点的所有后代叶节点的所有路径上包含相同数目的黑色节点。
红黑树的旋转和颜色翻转
左旋Left Rotation右旋Right Rotation颜色翻转Color Flip #mermaid-svg-fI27XpPXamydoCox {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-fI27XpPXamydoCox .error-icon{fill:#552222;}#mermaid-svg-fI27XpPXamydoCox .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-fI27XpPXamydoCox .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-fI27XpPXamydoCox .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-fI27XpPXamydoCox .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-fI27XpPXamydoCox .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-fI27XpPXamydoCox .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-fI27XpPXamydoCox .marker{fill:#333333;stroke:#333333;}#mermaid-svg-fI27XpPXamydoCox .marker.cross{stroke:#333333;}#mermaid-svg-fI27XpPXamydoCox svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-fI27XpPXamydoCox .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-fI27XpPXamydoCox .cluster-label text{fill:#333;}#mermaid-svg-fI27XpPXamydoCox .cluster-label span{color:#333;}#mermaid-svg-fI27XpPXamydoCox .label text,#mermaid-svg-fI27XpPXamydoCox span{fill:#333;color:#333;}#mermaid-svg-fI27XpPXamydoCox .node rect,#mermaid-svg-fI27XpPXamydoCox .node circle,#mermaid-svg-fI27XpPXamydoCox .node ellipse,#mermaid-svg-fI27XpPXamydoCox .node polygon,#mermaid-svg-fI27XpPXamydoCox .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-fI27XpPXamydoCox .node .label{text-align:center;}#mermaid-svg-fI27XpPXamydoCox .node.clickable{cursor:pointer;}#mermaid-svg-fI27XpPXamydoCox .arrowheadPath{fill:#333333;}#mermaid-svg-fI27XpPXamydoCox .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-fI27XpPXamydoCox .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-fI27XpPXamydoCox .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-fI27XpPXamydoCox .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-fI27XpPXamydoCox .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-fI27XpPXamydoCox .cluster text{fill:#333;}#mermaid-svg-fI27XpPXamydoCox .cluster span{color:#333;}#mermaid-svg-fI27XpPXamydoCox div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-fI27XpPXamydoCox :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 左旋 右旋 颜色翻转 红黑树的插入操作
红黑树的插入操作和普通二叉搜索树相同但插入新节点后需要进行重新平衡操作。以下是红黑树的插入操作代码示例
class RedBlackTreeNode {int value;RedBlackTreeNode left, right, parent;boolean color; // true for Red, false for Black// 构造函数RedBlackTreeNode(int item) {value item;left right parent null;color true; // new nodes are red by default}
}class RedBlackTree {private RedBlackTreeNode root;private final RedBlackTreeNode TNULL;// 初始化public RedBlackTree() {TNULL new RedBlackTreeNode(0);TNULL.color false;TNULL.left null;TNULL.right null;root TNULL;}// 前序遍历private void preOrderHelper(RedBlackTreeNode node) {if (node ! TNULL) {System.out.print(node.value );preOrderHelper(node.left);preOrderHelper(node.right);}}// 中序遍历private void inOrderHelper(RedBlackTreeNode node) {if (node ! TNULL) {inOrderHelper(node.left);System.out.print(node.value );inOrderHelper(node.right);}}// 后序遍历private void postOrderHelper(RedBlackTreeNode node) {if (node ! TNULL) {postOrderHelper(node.left);postOrderHelper(node.right);System.out.print(node.value );}}// 查找树中的节点private RedBlackTreeNode searchTreeHelper(RedBlackTreeNode node, int key) {if (node TNULL || key node.value) {return node;}if (key node.value) {return searchTreeHelper(node.left, key);}return searchTreeHelper(node.right, key);}// 平衡插入操作private void fixInsert(RedBlackTreeNode k) {RedBlackTreeNode u;while (k.parent.color true) {if (k.parent k.parent.parent.right) {u k.parent.parent.left;if (u.color true) {u.color false;k.parent.color false;k.parent.parent.color true;k k.parent.parent;} else {if (k k.parent.left) {k k.parent;rightRotate(k);}k.parent.color false;k.parent.parent.color true;leftRotate(k.parent.parent);}} else {u k.parent.parent.right;if (u.color true) {u.color false;k.parent.color false;k.parent.parent.color true;k k.parent.parent;} else {if (k k.parent.right) {k k.parent;leftRotate(k);}k.parent.color false;k.parent.parent.color true;rightRotate(k.parent.parent);}}if (k root) {break;}}root.color false;}// 左旋private void leftRotate(RedBlackTreeNode x) {RedBlackTreeNode y x.right;x.right y.left;if (y.left ! TNULL) {y.left.parent x;}y.parent x.parent;if (x.parent null) {this.root y;} else if (x x.parent.left) {x.parent.left y;} else {x.parent.right y;}y.left x;x.parent y;}// 右旋private void rightRotate(RedBlackTreeNode x) {RedBlackTreeNode y x.left;x.left y.right;if (y.right ! TNULL) {y.right.parent x;}y.parent x.parent;if (x.parent null) {this.root y;} else if (x x.parent.right) {x.parent.right y;} else {x.parent.left y;}y.right x;x.parent y;}// 插入节点public void insert(int key) {RedBlackTreeNode node new RedBlackTreeNode(key);node.parent null;node.value key;node.left TNULL;node.right TNULL;node.color true;RedBlackTreeNode y null;RedBlackTreeNode x this.root;while (x ! TNULL) {y x;if (node.value x.value) {x x.left;} else {x x.right;}}node.parent y;if (y null) {root node;} else if (node.value y.value) {y.left node;} else {y.right node;}if (node.parent null) {node.color false;return;}if (node.parent.parent null) {return;}fixInsert(node);}// 查找树中的节点public RedBlackTreeNode searchTree(int k) {return searchTreeHelper(this.root, k);}// 前序遍历public void preorder() {preOrderHelper(this.root);}// 中序遍历public void inorder() {inOrderHelper(this.root);}// 后序遍历public void postorder() {postOrderHelper(this.root);}// 打印树private void printHelper(RedBlackTreeNode root, String indent, boolean last) {if (root ! TNULL) {System.out.print(indent);if (last) {System.out.print(R----);indent ;} else {System.out.print(L----);indent | ;}String sColor root.color ? RED : BLACK;System.out.println(root.value ( sColor ));printHelper(root.left, indent, false);printHelper(root.right, indent, true);}}public void printTree() {printHelper(this.root, , true);}// 测试红黑树public static void main(String[] args) {RedBlackTree bst new RedBlackTree();bst.insert(55);bst.insert(40);bst.insert(65);bst.insert(60);bst.insert(75);bst.insert(57);bst.printTree();System.out.println(\n前序遍历:);bst.preorder();System.out.println(\n\n中序遍历:);bst.inorder();System.out.println(\n\n后序遍历:);bst.postorder();}
}红黑树插入操作图解
假设我们在一棵空的红黑树中插入以下节点55、40、65、60、75、57以下是每一步的插入和相应的颜色标注和旋转操作
插入 55成为根节点颜色变为黑色。插入 40为 55 的左子节点颜色为红色。插入 65为 55 的右子节点颜色为红色。插入 60为 65 的左子节点颜色为红色需要左旋 65。插入 75为 65 的右子节点颜色为红色。插入 57为 60 的左子节点颜色为红色需要右旋 60然后左旋 55。 #mermaid-svg-iGTXChZlDEdCqhcI {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-iGTXChZlDEdCqhcI .error-icon{fill:#552222;}#mermaid-svg-iGTXChZlDEdCqhcI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-iGTXChZlDEdCqhcI .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-iGTXChZlDEdCqhcI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-iGTXChZlDEdCqhcI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-iGTXChZlDEdCqhcI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-iGTXChZlDEdCqhcI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-iGTXChZlDEdCqhcI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-iGTXChZlDEdCqhcI .marker.cross{stroke:#333333;}#mermaid-svg-iGTXChZlDEdCqhcI svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-iGTXChZlDEdCqhcI .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-iGTXChZlDEdCqhcI .cluster-label text{fill:#333;}#mermaid-svg-iGTXChZlDEdCqhcI .cluster-label span{color:#333;}#mermaid-svg-iGTXChZlDEdCqhcI .label text,#mermaid-svg-iGTXChZlDEdCqhcI span{fill:#333;color:#333;}#mermaid-svg-iGTXChZlDEdCqhcI .node rect,#mermaid-svg-iGTXChZlDEdCqhcI .node circle,#mermaid-svg-iGTXChZlDEdCqhcI .node ellipse,#mermaid-svg-iGTXChZlDEdCqhcI .node polygon,#mermaid-svg-iGTXChZlDEdCqhcI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-iGTXChZlDEdCqhcI .node .label{text-align:center;}#mermaid-svg-iGTXChZlDEdCqhcI .node.clickable{cursor:pointer;}#mermaid-svg-iGTXChZlDEdCqhcI .arrowheadPath{fill:#333333;}#mermaid-svg-iGTXChZlDEdCqhcI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-iGTXChZlDEdCqhcI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-iGTXChZlDEdCqhcI .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-iGTXChZlDEdCqhcI .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-iGTXChZlDEdCqhcI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-iGTXChZlDEdCqhcI .cluster text{fill:#333;}#mermaid-svg-iGTXChZlDEdCqhcI .cluster span{color:#333;}#mermaid-svg-iGTXChZlDEdCqhcI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-iGTXChZlDEdCqhcI :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 40 红 55 黑 57 红 60 红 65 红 75 红 结论
通过上述讲解和实例代码我们详细展示了二叉搜索树的定义、基本操作及平衡二叉树AVL 树和红黑树。二叉搜索树在计算机科学中有着广泛的应用平衡二叉树通过保持树的高度在较低水平从而提高查找、插入和删除操作的效率。希望这篇博客对您有所帮助记得关注、点赞和收藏哦以便随时查阅更多优质内容 如果您觉得这篇文章对您有帮助请关注我的CSDN博客点赞并收藏这篇文章您的支持是我持续创作的动力 关键内容总结
二叉搜索树的定义和基本操作二叉搜索树的插入、删除和查找操作平衡二叉树AVL 树和红黑树AVL 树的旋转操作红黑树的性质和操作 推荐阅读深入探索设计模式专栏详细讲解各种设计模式的应用和优化。点击查看深入探索设计模式。 特别推荐设计模式实战专栏深入解析设计模式的实际应用提升您的编程技巧。点击查看设计模式实战。
如有任何疑问或建议欢迎在评论区留言讨论。谢谢阅读
