常用的数据结构：

  • 数组

  • 链表

  • 树

数组

特点：

  • 内存地址连续

  • 可以通过下标的成员访问 , 下标访问的性能高

  • 增删操作带来更大的性能消耗 ( 保证数据越界的问题 , 需动态扩容 )

链表

特点：

  • 灵活的空间要求，存储空间不要连续

  • 不支持下标的访问，支持顺序的遍历搜索

  • 针对增删操作找到对应的节点改变链表的头尾指向即可，无需移动元素存储位置

树

包括：

  • 二叉树

  • 红黑树

二叉树

特点：

  • 某节点的左子树节点值仅包含小于该节点值

  • 某节点的右子树节点值仅包含大于该节点值

  • 左右子树也必须是二叉查找树

  • 顺序排列

不平衡二叉树：

  • 查询效率不高

红黑树

是一个自平衡的二叉查找树，树上的每个节点都遵循下面的规则：

  • 每个节点要么是黑色，要么是红色

  • 根节点是黑色

  • 每个叶子节点是黑色

  • 每个红色节点的两个子节点一定是黑色

  • 任意一节点到每个叶子节点的路径都包含数量相同的黑节点