集合

hashMap数据结构之二叉树

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。二叉树每个节点的左子树和右子树也分别满足二叉树的定义。

Java中有两个方式实现二叉树:数组存储，链式存储。基于链式存储的树的节点可定义如下:

public class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(){}
  TreeNode(int val) { this.val =val;}
  TreeNode(int val, TreeNode left, TreeNode right){
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

二叉树分类

❒ 满二叉树

❒ 完全二叉树

❒ 二叉搜索树

✔ 二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型。
✔ 二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
✔ 插入，查找，删除的时间复杂度O(logn)
✔ 左右子树极度不平衡，此时查找的时间复杂度肯定是0(n)。

❒ 红黑树：红黑树是一种自平衡的二叉搜索树，具有以下性质：

✔ 每个结点不是红色就是黑色
✔ 根节点是黑色的
✔ 如果一个节点是红色的，则它的两个孩子结点是黑色的
✔ 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
✔ 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

❒ 什么是二叉树

✔ 每个节点最多有两个“叉”，分别是左子节点和右子节点。
✔ 不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
✔ 二叉树每个节点的左子树和右子树也分别满足二叉树的定义。

❒ 什么是二叉搜索树

✔ 二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树
✔ 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值而右子树节点的值都大于这个节点的值
✔ 没有键值相等的节点
✔ 通常情况下二叉树搜索的时间复杂度为O(logn)

❒ 什么是‌红黑树

是一种自平衡的二叉搜索树，具有以下性质‌：
‌✔ 节点颜色‌：红黑树的每个节点可以是红色或黑色。
‌✔ 根节点颜色‌：根节点必须是黑色。
‌✔ 叶子节点颜色‌：叶子节点（NIL或空节点）必须是黑色。
‌✔ 子节点颜色‌：红色节点的子节点必须是黑色，即不存在两个连续的红色节点。
✔ ‌黑色节点数量‌：从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点