目录

一、数据结构的概述

 二、栈

 三、队列

 四、数组

 五、链表

链表种类

六、二叉树、二叉查找树

二叉查找树

 二叉查找树添加节点

七、平衡二叉树

 平衡二叉树的要求

 解决平衡二叉树添加元素导致不平衡问题

八、红黑树

 添加节点

---

一、数据结构的概述

• 数据结构是计算机底层存储、组织数据的方式。是指数据相互之间以什么方式排列在一起的。
• 通常情况下，精心选择的数据结构可以带来更高的运行或存储效率。

 

 二、栈

特点：后进先出，先进后出。

数据进入栈模型的过程称为：压/进栈

数据离开栈模型的过程称为：弹/出栈

 

 三、队列

特点：先进先出 ，两端开口

 四、数组

一块连续的存储空间

 五、链表

链表种类

 数组根据索引查元素速度快，而链表增删首位元素速度快。

六、二叉树、二叉查找树

 

•  二叉树只能有一个根节点，每个节点最多支持2个直接子节点(左节点、右节点)。
• 节点的度：节点拥有的子树的个数，因此二叉树的度不大于2，叶子节点是度为0的节点，也成为终端节点，例如12、6；
• 高度：叶子节点的高度为一，依次向上高度递增。根节点高度最高。树越矮搜索深度就越短系统性能提高
• 层：根节点在第一层，以此类推。
• 兄弟节点：拥有共同父节点的节点互称为兄弟节点  4和10，2、5和11

二叉查找树

二叉查找树又称二叉排序树或者二叉搜索树。对元素已经排好序。查找使用了二分查找法。

 二叉查找树添加节点

适用于增删改查的数据结构，相对比较完美。

 先将7作为根节点，4比7小放左边，10比7大放右边

七、平衡二叉树

二叉树查找存在的问题

二叉树在极端情况下会存在瘸子现象，例如7、10、11、12、13进行二叉树排序

 

 最终会变成链表的形式，查询效率会降低。

 

 平衡二叉树的要求

任意节点的左右两个子树的高度差不超过1，任意节点的左右两个子树都是一颗平衡二叉树

 

 解决平衡二叉树添加元素导致不平衡问题

基本策略是进行左旋或右旋来保证不平衡，树往哪边倒就往另一边旋转。

 1、当根节点左子树的左子树有节点插入，导致二叉树不平衡 

• 将整个二叉树右旋，将4旋转到根节点，再调整内部子树

 2、当根节点左子树的右子树有节点插入，导致二叉树不平衡

• 先对出问题的节点进行左旋，再对整体右旋

可以通过左旋右旋来解决实际问题，例如将1、2、3、4、5、6、7做成一个平衡二叉树，就需要通过依次添加元素再不断地进行左旋右旋最终实现平衡二叉树。

八、红黑树

 

 添加节点

• 添加的节点颜色可以是红色，也可以是黑色。
• 默认用红色效率高