栈

队列

数组

特点：

• 查询快：数组的地址是连续的，可以通过找到数组首地址找到数组，通过数组索引快速找到某个元素
• 增删慢：数组的长度是固定的，增加/删除一个元素必须创建一个新数组，然后把源数组的数据复制过来

链表

特点

• 查询慢：链表中地址不连续，每次查询元素都必须从头开始查询

• 增删快：增加/删除一个元素对链表整体结构没有影响，所以增删快

  红黑树

  特点

• 趋近于平衡树，查询的速度非常快，查询叶子节点最大次数不能超过最小次数的两倍

约束

• 节点可以是红色的或者黑色的
• 根节点是黑色的
• 叶子结点（空节点）是黑色的
• 每个红色节点的子节点都是黑色的
• 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同