江干网站建设,广州注册公司名称,湖北网站建设找哪家,大型房产网站模板现在面试问mysql,红黑树好像都是必备问题了。动不动就让手写红黑树或者简单介绍下红黑树。然而#xff0c;我们如果直接去看红黑树#xff0c;可能会一下子蒙了。在看红黑树之前#xff0c;需要先了解下树的基础知识#xff0c;从简单到复杂#xff0c;看看红黑树是在什么…现在面试问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 ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();generate(root, result);return result;}private void generate(TreeNode root, ListInteger 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 ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();inorderTraversal(root, result);return result;}/*** 递归方式求解** param root* param result*/void inorderTraversal(TreeNode root, ListInteger result) {if (root.left ! null) {inorderTraversal(root.left, result);}result.add(root.val);if (root.right ! null) {inorderTraversal(root.right, result);}}后序遍历
后序遍历是先遍历左子树然后遍历右子树最后访问树的根节点。 例如对于如上图二叉树访问的先后顺序依次是ACEDBHIGF。
public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();generate(root, result);return result;}/*** 递归方法** param root* param result*/private void generate(TreeNode root, ListInteger 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 ListListInteger levelOrder(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}QueueTreeNode queue new LinkedList();queue.add(root);while (!queue.isEmpty()) {int size queue.size();ListInteger 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
对于二叉树我们可以进行中序遍历左中右观察遍历得到的值是不是从小到大排列可以使用此点验证二叉搜索树
LinkedListInteger 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 和 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}} log2n。对于具有 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 ListNode children;public Node() {}public Node(int _val, ListNode _children) {val _val;children _children;}}N叉树的遍历
前序遍历
public ListInteger preorder(Node root) {ListInteger 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) {ListInteger items preorder(n);res.addAll(items);}return res;}后序遍历
/*** 递归方法** param root* return*/public ListInteger postorder(Node root) {ListInteger res new ArrayList();if (root null) {return res;}postorder(root, res);return res;}void postorder(Node root, ListInteger res) {if (root.children null) {res.add(root.val);return;}for (Node n : root.children) {postorder(n, res);}res.add(root.val);}层序遍历
public ListListInteger levelOrder(Node root) {ListListInteger res new ArrayList();if (root null) {return res;}QueueNode queue new LinkedList();queue.add(root);while (!queue.isEmpty()) {int size queue.size();ListInteger 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 MapCharacter, TrieNode children new HashMap();// ......
};实现前缀树的插入和搜索
class Trie {private MapCharacter, 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;}ListTrieNode 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;}ListTrieNode 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 log2n。 但是在实际操作中我们会发现将树维护在高度平衡内实在是要耗费的力气太大了于是不得不在高度平衡和构建树上做一个妥协由此衍生出了很多工业级别的树但是限于本文篇幅这里没有涉及或许我会在后续的chat安排上。
除了二叉树本文还简单介绍了下N叉树和前缀树简单了解下树的其他应用方式。
