Java版-速通数据结构-树基础知识

现在面试问mysql,红黑树好像都是必备问题了。动不动就让手写红黑树或者简单介绍下红黑树。然而，我们如果直接去看红黑树，可能会一下子蒙了。在看红黑树之前，需要先了解下树的基础知识，从简单到复杂，看看红黑树是在什么场景下出现的，是哪种东西。
本文主要是介绍二叉树，二叉搜索树，然后到高度平衡二叉树，根据树的基本操作和特点，帮助理解那些特殊结构的树，是怎样演化而来的。

二叉树（Binary tree）基本概念

二叉树（Binary tree）是树形结构的一个重要类型。看它这名字，就是最多有俩叉的一种特殊的树形结构。通常，它的俩叉分别叫做左子树和右子树。
对二叉树的结构定义如下：

public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int x) {val = x;}
}

二叉树的遍历

在这里插入图片描述

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
例如，对于如上图二叉树，访问的先后顺序依次是：FBADCEGIH。
下面使用简单递归来写个：

//前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();generate(root, result);return result;}private void generate(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);if (root.left == null && root.right == null) {return;}if (root.left != null) {generate(root.left, result);}if (root.right != null) {generate(root.right, result);}}

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
例如，对于如上图二叉树，访问的先后顺序依次是：ABCDEFGHI。

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderTraversal(root, result);return result;}/*** 递归方式求解** @param root* @param result*/void inorderTraversal(TreeNode root, List<Integer> result) {if (root.left != null) {inorderTraversal(root.left, result);}result.add(root.val);if (root.right != null) {inorderTraversal(root.right, result);}}

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
例如，对于如上图二叉树，访问的先后顺序依次是：ACEDBHIGF。

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();generate(root, result);return result;}/*** 递归方法** @param root* @param result*/private void generate(TreeNode root, List<Integer> result) {//后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点if (root == null) {return;}if (root.left != null) {generate(root.left, result);}if (root.right != null) {generate(root.right, result);}result.add(root.val);}

层次遍历

层序遍历就是逐层遍历树结构。
例如，对于如上图二叉树，访问的先后顺序依次是：FBGADICEH。

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> item = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode n = queue.poll();item.add(n.val);if (n.left != null) {queue.add(n.left);}if (n.right != null) {queue.add(n.right);}}result.add(item);}return result;}

二叉树的深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
是不是通过上面对于二叉树的遍历，发现，二叉树用递归方法，简直是太好写了，下面我们对这个深度的求解也使用递归：

int answer = 0;public int maxDepth(TreeNode root) {if (root == null) {return 0;}int depth = 1;depth(root, depth);return answer;}private void depth(TreeNode root, int depth) {if (root.left == null && root.right == null) {answer = Math.max(answer, depth);}if (root.left != null) {depth(root.left, depth + 1);}if (root.right != null) {depth(root.right, depth + 1);}}

到这里我们会发现，对于二叉树的遍历操作，几乎都可以用递归来解决，超简单呀。

二叉搜索树(BinarySearchTree)

BST 定义

BST是二叉树的一种特殊表示形式，它满足如下特性:

  • 1,每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值
  • 2,每个节点中的值必须小于（或等于）存储在其右子树中的任何值

我们可以把BST看成是进化了的二叉树。而且观察BST的这个特点，是不是让你想起来我们之前说过的数组的二分法，利用二分法对有序数组进行查找，可以提高搜索效率。如果对BST进行搜索，我们也可以充分利用BST的特征。

验证BST

对于二叉树，我们可以进行中序遍历（左中右），观察遍历得到的值是不是从小到大排列，可以使用此点验证二叉搜索树；

LinkedList<Integer> data = new LinkedList<>();public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (root.left != null && !isValidBST(root.left)) {return false;}//左中右遍历，让值依次增大即可if (!data.isEmpty()) {Integer n = data.peekLast();if (n >= root.val) {return false;}}data.add(root.val);if (root.right != null && !isValidBST(root.right)) {return false;}return true;}

BST基本操作

搜索

搜索的具体思路跟二分法也是蜜汁类似，不懂二分法的请翻看我以前写的关于数组的基本操作。
对于BST来说，如果当前比较数值过小，往右搜索，过大，往左搜索。

public TreeNode searchBST(TreeNode root, int val) {if (root == null) {return null;}if (root.val == val) {return root;}if (root.val > val && root.left != null) {return searchBST(root.left, val);}if (root.val < val && root.right != null) {return searchBST(root.right, val);}return null;}

插入

对于插入操作也是一样的，在比较的基础上，找到合适的位置，哈哈。

public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {return root;}if (root.val > val && root.left == null) {root.left = new TreeNode(val);return root;}if (root.val < val && root.right == null) {root.right = new TreeNode(val);return root;}if (root.left != null && root.val > val) {insertIntoBST(root.left, val);}if (root.right != null && root.val < val) {insertIntoBST(root.right, val);}return root;}

删除

对于删除操作，可能比上面两种操作相对复杂一点。

    1. 如果目标节点没有子节点，我们可以直接移除该目标节点。
    1. 如果目标节只有一个子节点，我们可以用其子节点作为替换。
    1. 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。

对于 1 和 2，很好理解。对于3，我们先来看一个结点，值的大小顺序为：左<中<右，如果我们要删除中间结点并且还要保持这个顺序不变，则我们有两个方法：1，使用左侧树的最大值去掉中间结点；2，使用右侧最小值取代中间结点。这样才能使得转变之后的树还满足BST的特征。
代码如下：

    /*** @param root* @param key* @return*/public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return root;}if (root.val == key) {if (root.left == null && root.right == null) {return null;}if (root.left == null) {root = root.right;return root;}if (root.right == null) {root = root.left;return root;}root = getLeftChildMaxNode(root);return root;}if (root.val > key) {root.left = deleteNode(root.left, key);return root;}if (root.val < key) {root.right = deleteNode(root.right, key);return root;}return root;}/*** 转变右子树最小结点** @param root* @return*/private TreeNode getRightChildMinNode(TreeNode root) {if (root == null) {return root;}TreeNode left = root.left;TreeNode right = root.right;if (right.left == null) {right.left = left;return right;}//root的left直接挪到root.left的最小结点上TreeNode temp = right.left;while (temp.left != null) {temp = temp.left;}temp.left = left;return right;}/*** 转变左子树最大结点** @return*/private TreeNode getLeftChildMaxNode(TreeNode root) {if (root == null) {return root;}TreeNode left = root.left;TreeNode right = root.right;if (left.right == null) {left.right = right;return left;}TreeNode temp = left.right;while (temp.right != null) {temp = temp.right;}temp.right = right;return left;}

高度平衡二叉树

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
如果二叉搜索树的高度为 h ，则时间复杂度为 O(h) 。所以，二叉搜索树的高度的确很重要。对于一个有N个结点，高度为h的二叉树，h>= l o g 2 n {log_2{n}} log2​n。对于具有 N 个节点的二叉搜索树的高度在 logN 到 N 区间变化。也就是说，搜索操作的时间复杂度可以从 logN 变化到 N 。这是一个巨大的性能差异。所以，我们应该尽量把二叉搜索树，往高度平衡的二叉搜索树上靠，来提高搜索效率。

高度平衡二叉树验证

emm,还是递归，超简单，按照定义写即可：

Boolean res = true;public boolean isBalanced(TreeNode root) {singleBalanced(root);return res;}int singleBalanced(TreeNode root) {if (root == null) {return 0;}int left = singleBalanced(root.left) + 1;int right = singleBalanced(root.right) + 1;if (Math.abs(left - right) > 1) {res = false;}return Math.max(left, right);}

有序数组转换成高度平衡二叉搜索树

我们取数组的中间元素作为根结点， 将数组分成左右两部分，对数组的两部分用递归的方法分别构建左右子树。
感觉其实是二分法的反作用。
这个可以用于对于普通二叉搜索树，先用中序遍历，生成有序数组，之后，将有序数组构建成高度平衡二叉树。
这是采用拆解重构建的方式构造高度平衡二叉树的一种方法。之后，我们还会介绍通过调整普通二叉搜索树，构建高度平衡二叉树或者近似于高度平衡二叉树的方法。

   public TreeNode sortedArrayToBST(int[] nums) {if (nums == null || nums.length == 0) {return null;}return build(nums, 0, nums.length - 1);}TreeNode build(int[] nums, int left, int right) {if (left == right) {return new TreeNode(nums[left]);}int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);if (left + 1 == right) {root.right = new TreeNode(nums[right]);return root;}if (left + 2 == right) {root.left = new TreeNode(nums[left]);root.right = new TreeNode(nums[right]);return root;}root.left = build(nums, left, mid - 1);root.right = build(nums, mid + 1, right);return root;}

N叉树

N叉树:一个结点有N个叉，哈哈。
二叉树属于N叉树的一个特例。
结点定义：

class Node {public int val;public List<Node> children;public Node() {}public Node(int _val, List<Node> _children) {val = _val;children = _children;}}

N叉树的遍历

前序遍历

public List<Integer> preorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.add(root.val);if (root.children == null || root.children.size() < 1) {return res;}for (Node n : root.children) {List<Integer> items = preorder(n);res.addAll(items);}return res;}

后序遍历

/*** 递归方法** @param root* @return*/public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}postorder(root, res);return res;}void postorder(Node root, List<Integer> res) {if (root.children == null) {res.add(root.val);return;}for (Node n : root.children) {postorder(n, res);}res.add(root.val);}

层序遍历

public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<Node> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> data = new ArrayList<>();for (int i = 0; i < size; i++) {Node node = queue.poll();data.add(node.val);if (node.children != null && node.children.size() > 0) {queue.addAll(node.children);}}res.add(data);}return res;}

前缀树

前缀树定义

在这里插入图片描述

前缀树特点：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
  • 每个节点的所有子节点包含的字符都不相同。

下面为两种常用前缀树的结构：
1，使用数组来存储后缀结点：

class TrieNode {public static final int N = 26;public TrieNode[] children = new TrieNode[N];// ......}

2，使用map来存储后缀结点：

class TrieNode {public Map<Character, TrieNode> children = new HashMap<>();// ......
};

实现前缀树的插入和搜索

class Trie {private Map<Character, TrieNode> data = new HashMap<>();public Trie() {}public void insert(String word) {if (word == null || word.isEmpty()) {return;}if (search(word)) {return;}char[] words = word.toCharArray();char head = words[0];TrieNode currt = data.get(head);if (currt == null) {currt = new TrieNode(head);data.put(head, currt);}for (int i = 1; i < words.length; i++) {char c = words[i];if (currt.next == null) {currt.next = new ArrayList<>();}TrieNode target = currt.next.stream().filter(n -> n.c == c).findFirst().orElse(null);if (target == null) {target = new TrieNode(c);currt.next.add(target);}currt = target;}currt.isWord = true;}public boolean search(String word) {if (word == null || word.isEmpty()) {return false;}char[] words = word.toCharArray();char head = words[0];TrieNode currt = data.get(head);if (currt == null) {return false;}for (int i = 1; i < words.length; i++) {char c = words[i];if (currt.next == null || currt.next.size() == 0) {return false;}List<TrieNode> next = currt.next;TrieNode t = next.stream().filter(n -> n.c == c).findFirst().orElse(null);if (t == null) {return false;}currt = t;}return currt.isWord;}public boolean startsWith(String prefix) {if (prefix == null || prefix.isEmpty()) {return false;}char[] words = prefix.toCharArray();char head = words[0];TrieNode currt = data.get(head);if (currt == null) {return false;}for (int i = 1; i < words.length; i++) {char c = words[i];if (currt.next == null || currt.next.size() == 0) {return false;}List<TrieNode> next = currt.next;TrieNode t = next.stream().filter(n -> n.c == c).findFirst().orElse(null);if (t == null) {return false;}currt = t;}return true;}}

小结

本文从最简单的二叉树开始讲起，介绍了简单二叉树的遍历，
之后延伸到对于搜索友好的二叉搜索树，对比二叉搜索树和我之前chat里面讲过的二分法，你会发现，提高搜索效率的秘诀，在于构建有序的结构，之后尽量利用二分法的原理，使得搜索的时间复杂度靠近 l o g 2 n log_2n log2​n。
但是在实际操作中，我们会发现，将树维护在高度平衡内，实在是要耗费的力气太大了，于是不得不在高度平衡和构建树上做一个妥协，由此衍生出了很多工业级别的树，但是限于本文篇幅，这里没有涉及，或许我会在后续的chat安排上。

除了二叉树，本文还简单介绍了下N叉树和前缀树，简单了解下树的其他应用方式。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/484748.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

C++《set与map》

C++《set与map》

在之前我们已经学习了解了CSTL当中的string和vector等容器&#xff0c;现在我们已经懂得了这些容器提供的接口该如何使用&#xff0c;并且了解了这些容器的底层结构。接下来我们在本篇当中将继续学习STL内的容器set与map&#xff0c;在此这两个容器与我们之前学习的容器提供的成…
阅读更多...
Scala—Slice（提取子序列）方法详解

Scala—Slice（提取子序列）方法详解

Scala—Slice&#xff08;提取子序列&#xff09;方法详解 在 Scala 中&#xff0c;slice 方法用于从集合中提取一个连续的子序列&#xff08;切片&#xff09;。可以应用于多种集合类型&#xff0c;如 List、Array、Seq 等。 一、slice 方法的定义 slice 根据提供的起始索引…
阅读更多...
Android显示系统（05）- OpenGL ES - Shader绘制三角形（使用glsl文件）

Android显示系统（05）- OpenGL ES - Shader绘制三角形（使用glsl文件）

一、前言&#xff1a; 上一篇文章我们使用了Shader绘制了一个基本的三角形&#xff0c;但是&#xff0c;发现那样写Shader程序特别麻烦&#xff0c;各种加双引号&#xff0c;还没有语法高亮提示。因为glsl也和java、c一样是一门语言&#xff0c;实际工程项目都是单独的glsl文件…
阅读更多...
挑战用React封装100个组件【009】

挑战用React封装100个组件【009】

Hello&#xff0c;大家好&#xff0c;今天我挑战的组件是这样的&#xff01; 欢迎大家把项目拉下来使用哦&#xff01; 项目地址&#xff1a; https://github.com/hismeyy/react-component-100 今天还是用到了react-icons。这里就不过多介绍啦&#xff0c;大家可以在前面的挑战…
阅读更多...
电子病历静态数据脱敏路径探索

电子病历静态数据脱敏路径探索

一、引言 数据脱敏&#xff08;Data Masking&#xff09;&#xff0c;屏蔽敏感数据&#xff0c;对某些敏感信息&#xff08;比如patient_name、ip_no、ad、no、icd11、drug等等 &#xff09;通过脱敏规则进行数据的变形&#xff0c;实现隐私数据的可靠保护。电子病历作为医疗领…
阅读更多...
React性能优化

React性能优化

三个可以优化的地方 避免过度多次渲染 组件会在以下情况下重新渲染 注意&#xff1a;例如组件组合的形式&#xff0c;<Test><Counter></Counter></Test>,即使Test发生了重新渲染&#xff0c;Counter也不会重新渲染。另外使用React这样的库或框架时&a…
阅读更多...
部署项目报错

部署项目报错

vue2项目部署后 Error: Cannot find module /views/*** 1.起因 登录页、首页等静态页面可以正常进入&#xff0c;后端访问也正常&#xff0c;可以获取到验证码。 但是登录之后会发现首页空白或者进入不到首页 F12查看有报错信息&#xff1a;Error: Cannot find module ‘/v…
阅读更多...
高端空气净化器airgle—甲醛克星 | 双十二选购指南

高端空气净化器airgle—甲醛克星 | 双十二选购指南

随着双十二购物节的临近&#xff0c;许多消费者开始关注高端空气净化器的选购。甲醛作为室内空气污染的主要元凶之一&#xff0c;选择一款高效的空气净化器显得尤为重要。本文将详细介绍Airgle高端空气净化器的技术优势及其在除甲醛方面的卓越表现。 甲醛对健康的影响 甲醛超标…
阅读更多...
LCR 023. 相交链表

LCR 023. 相交链表

一.题目&#xff1a; LCR 023. 相交链表 - 力扣&#xff08;LeetCode&#xff09; 二.我的原始解法-无&#xff1a; 三.其他人的正确及好的解法&#xff0c;力扣解法参考&#xff1a; 哈希表法及双指针法&#xff1a;LCR 023. 相交链表 - 力扣&#xff08;LeetCode&#xff0…
阅读更多...
RocketMq详解：六、RocketMq的负载均衡机制

RocketMq详解：六、RocketMq的负载均衡机制

上一章&#xff1a;《SpringBootAop实现RocketMq的幂等》 文章目录 1.背景1.1 什么是负载均衡1.2 负载均衡的意义 2.RocketMQ消息消费2.1 消息的流转过程2.2 Consumer消费消息的流程 3.RocketMq的负载均衡策略3.1 Broker负载均衡3.2 Producer发送消息负载均衡3.3 消费端的负载均…
阅读更多...
02-开发环境搭建

02-开发环境搭建

02-开发环境搭建 鸿蒙开发环境的准备主要分为以下环节&#xff1a; 注册开发者实名认证创建应用下载安装开发工具新建工程 注册开发者 在华为开发者联盟网站上&#xff0c;注册成为开发者&#xff0c;并完成实名认证。 打开华为开发者联盟官网&#xff0c;点击“注册”进入…
阅读更多...
使用SQLark分析达梦慢SQL执行计划的一次实践

使用SQLark分析达梦慢SQL执行计划的一次实践

最近刚参加完达梦的 DCP 培训与考试&#xff0c;正好业务系统有个 sql 查询较慢&#xff0c;就想着练练手。 在深入了解达梦的过程中&#xff0c;发现达梦新出了一款叫 SQLark 百灵连接的工具。 我首先去官网大致浏览了下。虽然 SQLark 在功能深度上不如 DM Manager 和 PL/SQ…
阅读更多...
Hive分区值的插入

Hive分区值的插入

对于Hive分区表&#xff0c;在我们插入数据的时候需要指定对应的分区值&#xff0c;而这里就会涉及很多种情况。比如静态分区插入、动态分区插入、提供的分区值和分区字段类型不一致&#xff0c;或者提供的分区值是NULL的情况&#xff0c;下面我们依次来展现下不同情况下的表现…
阅读更多...
云计算vspere 安装过程

云计算vspere 安装过程

1 材料的准备 1 安装虚拟机 vmware workstation 2 安装esxi 主机 3 在esxi 主机上安装windows 2018 dns 服务器 4 在虚拟机上安装windows 2018 服务器 6 安装vcenter 5 登入界面测试 这里讲一下&#xff0c;由于部署vspere 需要在windows 2012 服务器上部…
阅读更多...
【0x0001】HCI_Inquiry命令详解

【0x0001】HCI_Inquiry命令详解

目录 一、命令概述 1.1. 返回事件说明 1.2. 设备报告规则 二、命令格式及参数 2.1. HCI_Inquiry命令格式 2.2. LAP参数 2.3. Inquiry_Length 2.4. Num_Responses 三、响应事件 3.1. HCI_Command_Status 事件 3.2. HCI_Inquiry_Result, HCI_Inquiry_Result_with_RSSI…
阅读更多...
五.指派问题

五.指派问题

匈牙利发求解指派问题找独立0元素&#xff0c;常用的步骤为&#xff1a;
阅读更多...
2024蜀道山高校联合公益赛

2024蜀道山高校联合公益赛

mixian 数组越界&#xff0c;可以去攻击stdout泄露libc&#xff0c;之后伪随机数绕过 from pwn import* from struct import pack import ctypes #from LibcSearcher import * from ae64 import AE64 def bug():gdb.attach(p)pause() def s(a):p.send(a) def sa(a,b):p.sendaf…
阅读更多...
【若依框架】RuoYi-Vue的前端和后端配置步骤和启动步骤

【若依框架】RuoYi-Vue的前端和后端配置步骤和启动步骤

&#x1f399;告诉你&#xff1a;Java是世界上最美好的语言 &#x1f48e;比较擅长的领域&#xff1a;前端开发 是的&#xff0c;我需要您的&#xff1a; &#x1f9e1;点赞❤️关注&#x1f499;收藏&#x1f49b; 是我持续下去的动力&#xff01; 目录 一. 作者有话说 …
阅读更多...
Python毕业设计选题：基于大数据的旅游景区推荐系统_django

Python毕业设计选题：基于大数据的旅游景区推荐系统_django

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 系统首页界面 用户注册界面 用户登录界面 景点信息界面 景点资讯界面 个人中心界面 …
阅读更多...
Endnote 参考文献内容没有按引用顺序进行排序

Endnote 参考文献内容没有按引用顺序进行排序

Endnote 参考文献内容没有按引用顺序进行排序&#xff1a; word论文正文第一个引用就是[4]打头&#xff0c;疯狂卸载重装&#xff0c;修改设置&#xff0c;排查了大半天&#xff0c;最后解决了。 常规解决方案 就是在Endnote 软件里面对outputstyle进行修改&#xff0c;将Biogr…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023