树

• 之前讲过一些数据结构, 树也是一种数据结构, java中很多代码的底层原理是树

概念:

• 节点: 在树结构中,每一个元素称之为节点
• 度: 每一个节点的子节点数量称之为度

1.1. 二叉树

• 二叉树中,任意一个节点的度要小于等于2

1.2. 二叉查找树

1.2.1. 二叉查找树的特点

• 二叉查找树,又称二叉排序树或者二叉搜索树

• 每一个节点上最多有两个子节点

• 左子树上所有节点的值都小于根节点的值

• 右子树上所有节点的值都大于根节点的值

• 二叉查找树结构图

  

• 二叉查找树和二叉树对比结构图

  

• 二叉查找树添加节点规则

  • 小的存左边
  • 大的存右边
  • 一样的不存

• 练习: 分别把下面两组数据构成二叉搜索树

  37，24，12，30，53，45，96

  12，24，30，37，45，53，96

1.2.2. 小结:

• 掌握二叉搜索树的规则
• 二叉搜索树的好处是查询效率高

1.3. 平衡二叉树

• 平衡二叉树的特点

  • 二叉树左右两个子树的高度差不超过1
  • 任意节点的左右两个子树都是一颗平衡二叉树

• 平衡二叉树旋转

  • 旋转触发时机

    • 当添加一个节点之后,该树不再是一颗平衡二叉树

  • 左旋

    • 就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点

    

  • 右旋

    • 就是将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点

      

1.3.1. 平衡二叉树旋转的四种情况

• 左左

  • 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡

  • 如何旋转: 直接对整体进行右旋即可

    

• 左右

  • 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡

  • 如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋

    

• 右右

  • 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡

  • 如何旋转: 直接对整体进行左旋即可

    

• 右左

  • 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡

  • 如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋

    

1.4. 红黑树

1.4.1. 红黑树的特点

• 平衡二叉B树
• 每一个节点可以是红或者黑
• 红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的

1.4.2. 红黑树的红黑规则有哪些

1. 每一个节点或是红色的,或者是黑色的
2. 根节点必须是黑色
3. 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的
4. 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连 的情况)
5. 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点

1.4.3. 红黑树添加节点后如何保持红黑规则