今日学习内容总结

• 数据结构
• 红黑树

---

数据结构

栈

• 特点：先进后出

---

队列

• 特点：先进先出

---

数组

• 特点：查询快（可以通过数组的索引快速查找某个元素）
  　　　　增删慢（长度固定，增删元素必须要创新个新数组，把原数组的数据复制过来）

---

链表

• 特点：查询慢（链表中的地址不是连续的，每次查询都要遍历所有元素）
  　　　　增删快（链表结构增加或删除一个元素，对链表的整体结构没有影响）
• 链表中的每一个元素也称之为一个节点，一个节点包含了一个数据源，两个指针域

• 结构：|自己的地址|数据|下一个节点的地址|

  
  链表结构

• 分类：
  　　　　单向链表：链表中只有一条链，不能保证元素的顺序（存取元素的顺序可能不一致）
  　　　　双向链表：链表中有两条链，有一条专门记录元素的顺序，是一个有序的集合

  
  单向与双向链表

• 增删元素只需更改下一个节点的地址即可

  
  增删元素

---

红黑树

• 二叉树：分支不能超过两个，左侧的分支叫左子树，右侧的叫右子树
• 排序树（查找树）：在二叉树的基础上，从小到大排序（左子树小，右子树大）
• 平衡二叉树：左子树和右子树数量相同

• 红黑树：
  　　　　特点：趋近于平衡二叉树，查询速度非常快，查询叶子节点的最大次数和最小次数不能超过2倍
  　　　　约束：
  　　　　　　1、节点可以是红色或者黑色的
  　　　　　　2、根节点是黑色的
  　　　　　　3、叶子节点是黑色的
  　　　　　　4、每个红色的节点子节点都是黑色的
  　　　　　　5、任何一个节点到其每个叶子节点所有路径上黑色的节点数相同

  
  红黑树举例