《红黑树》专题

一、AVL树 AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。 上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。 二、红黑树 R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查

一、树的介绍 1.树的定义 树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。 把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： (01) 每个节点有零个或多个子节点； (02) 没有父节点的节点称为根节点； (03) 每一个非根节点有且只有一个父节点； (04) 除了根节点外，每个子节点可以分为多个不相交的子树。 2.树的基

一、前言 树作为一种重要的数据结构，即是面试重点考察知识点，也是实际生产应用中可能会灵活应用的一种数据结构。那么其重要性不言而喻，无论是在剑指offer，还是在leetcode中，都有很多关于树的题目。 本部分内容主要介绍树的一些基础概念及Java实现，同时介绍一些常见的树，如二叉搜索树，平衡树，红黑树等。 二、目录 树的基础 其他常见的树 并查集 B-树，B+树，B*树

1 Boosting   Boosting是一类将弱学习器提升为强学习器的算法。这类算法的工作机制类似：先从初始训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注。 然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器的数目达到事先指定的值T，最终将这T个基学习器进行加权结合。   Boost算法是在算法开始

1 Bagging   Bagging采用自助采样法(bootstrap sampling)采样数据。给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时，样本仍可能被选中， 这样，经过m次随机采样操作，我们得到包含m个样本的采样集。   按照此方式，我们可以采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基本学习器，再将这些基本学习

  集成学习通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统。集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化能力。   根据个体学习器的生成方式，目前的集成学习方法大致可以分为两大类。即个体学习器之间存在强依赖性，必须串行生成的序列化方法以及个体学习器之间不存在强依赖性，可同时生成的并行化方法。 前者的代表是Boosting，后者的代表是Bagging和随机森

1 决策树理论 1.1 什么是决策树   所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。 树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，从根节点到叶节点所经历的路径对应一个判定测试序列。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 1.2 决策树学习流

递归 1. 树的高度 2. 平衡树 3. 两节点的最长路径 4. 翻转树 5. 归并两棵树 6. 判断路径和是否等于一个数 7. 统计路径和等于一个数的路径数量 8. 子树 9. 树的对称 10. 最小路径 11. 统计左叶子节点的和 12. 相同节点值的最大路径长度 13. 间隔遍历 14. 找出二叉树中第二小的节点 层次遍历 1. 一棵树每层节点的平均数 2. 得到左下角的节点 前中后序遍历

题目链接 牛客网 题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回 。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 // java public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; Tr

题目链接 牛客网 题目描述 根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解题思路 前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。 // java // 缓存中序遍历数组每个值对应的索引 private Map ind

68.1 二叉查找树 题目链接 Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree 解题思路 在二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。 // java public TreeNode lowestCommonAncestor

NowCoder 题目描述 平衡二叉树左右子树高度差不超过 1。 解题思路 // java private boolean isBalanced = true; public boolean IsBalanced_Solution(TreeNode root) { height(root); return isBalanced; } private int height(Tre

NowCoder 题目描述 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路 // java public int TreeDepth(TreeNode root) { return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));

NowCoder 解题思路 利用二叉查找树中序遍历有序的特点。 // java private TreeNode ret; private int cnt = 0; public TreeNode KthNode(TreeNode pRoot, int k) { inOrder(pRoot, k); return ret; } private void inOrder(Tree

NowCoder 题目描述 请实现两个函数，分别用来序列化和反序列化二叉树。 解题思路 // java private String deserializeStr; public String Serialize(TreeNode root) { if (root == null) return "#"; return root.val + " " + Seria