目录
8、红黑树
1、栈
特点：先进后出，后进先出
数据进入栈模型的过程称为:压/进栈
数据离开栈模型的过程称为:弹/出栈
2、队列
特点：先进先出，后进后出
数据从后端进入队列模型的过程称为:入队列
数据从前端离开队列模型的过程称为:出队列
3、数组
特点：1、查询速度快:查询数据通过地址值和索引定位，查询任意数据耗时相同。(元素在内存中
是连续存储的)
2、删除效率低:要将原始数据删除，同时后面每个数据前移。
3、添加效率极低:添加位置后的每个数据后移，再添加元素。
4、链表
特点：链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地
址链表查询慢，无论查询哪个数据都要从头开始找。链表增删相对快。
5、树
度：每一个节点的子节点数量
二叉树中，任意节点的度<=2
6、二叉树
二叉查找树，又称二叉排序树或者二叉搜索树
特点：
1、每一个节点上最多有两个子节点
2、任意节点左子树上的值都小于当前节点
3、任意节点右子树上的值都大于当前节点
二叉树添加规则
小的存左边，大的存右边，一样的不存
二叉树的遍历
前序遍历：从根结点开始，然后按照当前结点，左子结点，右子结点的顺序遍历
后序遍历：从最左边的子节点开始，然后按照左子结点，右子结点，当前结点的顺序遍历
层序遍历：从根节点开始一层一层遍历
7、平衡二叉树
规则:任意节点左右子树高度差不超过1
数据结构（平衡二叉树)旋转机制
规则1:左旋
规则2:右旋
触发时机:当添加一个节点之后，该树不再是一颗平衡二叉树
左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
1、以不平衡的点作为支点
2、将根节点的右侧往左拉
3、原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
右旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
1、以不平衡的点作为支点
2、就是将根节点的左侧往右拉
3、原先的左子节点变成新的父节点,并把多余的右子节点出让，给已经降级的根节点当左子节点
插入节点导致二叉树不平衡
左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡
左右:当根节点左子树的右子树有节点插入，导致二叉树不平衡
右右:当根节点右子树的右子树有节点插入，导致二叉树不平衡
右左:当根节点右子树的左子树有节点插入，导致二叉树不平衡
左左：一次右旋
左右：先局部左旋，再整体右旋
右右：一次左旋
右左：先局部右旋，再整体左旋
8、红黑树
红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
1972年出现，当时被称之为平衡二叉B树。后来，1978年被修改为如今的”红黑树”。
它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，
每一个节点可以是红或者黑;红黑树不是高度平衡的，它的平衡是通过”红黑规则”进行实现的
红黑树：是一个二叉查找树，但是不是高度平衡的条件，特有的红黑规则
（红黑树）添加节点的规则—红黑树在添加节点的时候，添加的节点默认是红色的
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/93333.html
