Java笔记（数据结构与算法[树、栈、列表、队列、数组]）
链表
栈 , 队列 , 数组
树
- 易错点 : 二叉树的插入 , 数据往二叉树里面插入的时候 , 每一个数据都要和每一个节点相比较 , 不可能插入到某两个节点中间 , 最后一定是挂(添加)到二叉树的最后一排的某个节点上
- 度 : 每个结点子节点的数量
- 二叉树 : 任意结点的度小于等于2
- 树高 : 数的总层数
- 根节点 : 最顶层的节点
- 左子节点 : 左下方的节点
- 普通结点也可以有左子树和右子树
二叉查找树
定义
- 又称二叉查找树或者二叉搜索树或者二叉排序树
添加结点
- 规则 :
- 小的存左边
- 大的存右边
- 一样的不存
查找节点
- 上面的树查找5
- 5先和7比较 ,小 ,那么应该在7左边 ,之后跟4比较 ,大 ,那么应该在右边 ,找到5
- 上面的树查找12
- 12先和7比较 ,大 ,再和10比较 ,大 ,再和11比较 ,大 ,和12比较 ,找到
- 上面的树查找30
- 一直查找发现到底层之后没有节点了 ,那么断定这棵树中没有30
二叉查找树的弊端
-
如果数据比较有规律 , 都是从小到大或者从大到小排列 , 那么空间上排列方式有些不妥
-
所以就有平衡二叉树
平衡二叉树
- 定义 : 任意节点的左右子树的高度差不超过一
- 注意任意两个字 , 不能只看根节点
- 例如下图 , 10结点 , 没有左子树 , 左子树高度是0 , 右子树高度是3
平衡二叉树的旋转机制
- 平衡二叉树如何保持平衡 ? ------旋转机制
- 首先要确定支点 : 从添加的结点开始 , 不断往父节点找不平衡的点
左旋
例子一:
-
旋转之前
-
旋转之后
例子二:
-
旋转之前
-
旋转之后
右旋
例子一:
- 旋转之前
- 旋转之后
例子二:
- 旋转之前
- 旋转之后
平衡二叉树需要旋转的四种情况
左左—一次右旋
左右—先局部左旋 , 再整体右旋
- 只进行了一次右旋 , 发现仍然不平衡, 所以这种方法舍弃
- 正确解法 : 先把树进行局部左旋,注意左旋的部分并没有不平衡
- 将左右的情况变成左左
- 然后进行整体右旋
右右—一次左旋
右左—先局部右旋 , 在整体左旋
二叉树
二叉树的遍历
- 前序遍历(根遍历) , 中序遍历 , 后序遍历: 深度优先
- 层序遍历 : 广度优先
前序遍历
中序遍历(最常用)
-
相当于把整个树压扁成一条线，这条线从前往后的顺序遍历
-
先看跟结点有没有左子树 , 有 , 就从20走到18 , 然后在跟结点的左子树当中 , 是根据左中右遍历的
-
最终结果
-
这种方式的结果是从小到大排列的 , 所以也比较常用
后序遍历
层序遍历
红黑树
- 是一种自平衡的二叉查找树 , 是计算机科学中用到的一种数据结构
红黑规则
- 左根右，根叶黑，不红红，黑路同
- 每一个节点是红色或者黑色
- 根节点必须是黑色
- 叶节点必须是黑色的
- 两个红色结点不能相连
- 任意结点到所有后代叶节点的简单路径上, 黑色结点数量相同
-
叶节点(叶子结点) : 被标为Nil的黑色结点 , ,用于判断当前红黑树是否满足规则
-
某结点所有后代结点 : 就是这个节点的子树(左子树及右子树)上的所有节点(包括叶子结点)
- 后代叶节点 : 就是后代(该节点的子树上的)的所有Nil
-
简单路径 : 从某结点开始走 , 不能回头 , 一路走到底 , 只能往前
红黑树添加结点的规则
-
默认颜色 : 添加结点默认颜色是红色的(效率高)
-
以下为验证
-
案例 : 添加以下三个黑色结点
- 下图违背了第五条规则
- 案例 : 添加下面三个红色结点
- 因为第二条规定根节点必须是黑色的 , 所以这里直接把20变成黑色的
- 接下来比较18和20 , 发现18小于20 , 所以添加在20左子节点 , 发现这个操作并没有违背规则 , 那么继续添加23 , 发现添加在右子结点 , 整体也没有违背规则
- 第一个坑 : 叔叔是红色的 , 如果祖父非根 , 需要把祖父设置为当前结点在进行其他判断
- 第二个坑 : 当前结点是父的右孩子 , 叔叔是黑色的 , 那么需要把父设置为当前结点 , 再进行判断
小结
-
叔叔结点是同一个爷爷的子树上的节点 , 别的爷爷的子树上的节点和当前结点无关 , 例如下面的15, 19是叔叔 , 但是右边的22和24就不是
-
同时注意旋转的时候不需要考虑叶子结点 , 先把叶子结点忽略 , 然后直接转
