| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 |
- 数据结构-树型结构
- 度：节点拥有的子节点的数量称为节点的度数（Degree），而树的度数是所有节点中度数的最大值。
- 树的种类：
- 1、二叉树
- 二叉树中，任意的一个节点的度必须小于或等于2
- 节点：在树结构中，每一个元素称为节点
- 度：每一个节点的子节点的个数。
- 2、二叉查找树
- 二叉查找树也叫【二叉排序树】，也叫【二叉搜索树】
- 每一个节点上最多有两个子节点。
- 左子树上所有节点的值都小于根节点的值
- 右子树上所有节点的值都大于根节点的值
- 二叉查找树添加子节点的时候，要求：
- 比父节点小的放左边
- 比父节点大的放右边
- 一样的不放
- 3、平衡二叉搜索树 AVL树
- 要求二叉树的左右子树的高度差不能超过1。
- 要求任意的节点的左右两个子树都是一棵平衡二叉树
- 平衡二叉树旋转
- 旋转触发的时机：当添加一个节点之后，这棵树不再是平衡二叉树的时候，就会进行旋转。
- 二叉树的旋转：
- 左旋：
- 把根节点右侧往左拉，原来的右子节点变为新的父节点，并且把多余的左子节点让出，
- 给降级的根节点当右子节点。
- 右旋：
- 就是把根节点左侧往右拉，原来的左子节点变为新的父节点，并且把多余的右子节点让出，
- 给降级的根节点当左子节点。
- 触发平衡二叉树旋转的四种情况：
- 左左：
- 当根节点左子树的左子树有节点插入，导致二叉树不平衡。
- 旋转方式：直接对整体进行右旋即可
- 左右：
- 当根节点左子树的右子树有节点插入，导致二叉树不平衡。
- 旋转方式：先在左子树对应的节点位置进行左旋，然后再对整体进行右旋
- 右右：
- 当根节点右子树的右子树有节点插入，导致二叉树不平衡。
- 旋转方式：直接对整体进行左旋即可
- 右左：
- 当根节点右子树的左子树有节点插入，导致二叉树不平衡。
- 旋转方式：先在右子树对应的节点位置进行右旋，然后再对整体进行左旋
- 4、红黑树
- 每一个节点可以是【红】或者是【黑】
- 红黑树不是高度平衡的，它的平衡是通过自己的【红黑规则】来实现的
- 红黑规则：
- 1、每一个节点要么是红色的，要么是黑色的。
- 2、根节点必须是黑色的。
- 3、如果一个节点没有子节点(叶子节点)或者没有父节点(根节点)，
- 那么该节点相应的指针属性值为Nil，这些Nil是为叶子节点，每个叶子节点是黑色的。
- 4、如果一个节点是红色的，那么它的子节点必须是黑色的(不能出现两个红色节点相连的情况)
- 5、每一个节点，从该节点开始到后面的所有叶子节点的简单路径上，都要包含相同个数的黑色节点。
- 添加节点的时候，新节点的颜色可以是红色也可以是黑色。建议默认的颜色是红色，可以提高效率。
- 当我们添加节点后，为了保持红黑规则：
- 根节点位置，建议直接设置为黑色。
- 非根节点位置，
- |-如果父节点是黑色，那么不用做任何操作，子节点默认红色就行。
- |-如果父节点是红色，
- |-叔叔节点也为红色
- 把父节点设置为黑色，把叔叔节点设置为黑色
- 把祖父节点设置为红色
- 如果祖父节点是根节点，就再次把根节点设置为黑色
- |-叔叔节点为黑色
- 把父节点设置为黑色
- 把祖父节点设置为红色
- 再以祖父节点为支点进行旋转
|
