二叉树
树
非线性表结构
父节点 子节点 兄弟节点:
节点 储存数据 同时储存 子节点的指针,同一节点下的 所有子节点 互为兄弟节点
根节点:没有父节点 的节点
叶子节点:没有子节点 的节点
节点的
高度(Height):当前节点到叶子节点的边数(叶子节点为0,根节点为 层数-1)
深度(Depth):根节点到这个节点的边数(根节点为0,叶子节点为 层数-1)
层(Level):节点的深度 +1(根节点为1,叶子节点为 深度+1)
深度 从上往下数(如水深),初始0; 高度 从下往上数(如楼房),初始0.
层数 同深度,但初始为1
树的高度:根节点的高度
二叉树
由一个空节点 或 两颗不相交二叉树组成(递归定义)
满二叉树 除了叶子节点 每个节点都有左右两个节点组成
完全二叉树 除了最后一层,其他层都是满节点,叶子节点都在左边.
如何储存一个二叉树
链式储存法 基于链表,每个节点三个字段,一个存数据,两个存左右节点的指针.
顺序储存法
完全二叉树:
1.基于数组,根节点放在i=1的位置,一层一层从左往下,依次放入数组.
2.此时,如果节点X在i位置,左子节点就是2 i,右子节点就是2 i + 1.
非完全二叉树:
按照上面 (2.)的方式放入数组,
平衡二叉树
平衡二叉树:任意一个节点左右子树高度相差不能大于1
平衡二叉树的初衷:解决普通二叉查找树树结构"不平衡"时,出现时间复杂度退化的情况
"近似平衡": 树看起来"比较对称","比较平衡",不出现左右子树一边高一边矮的情况.
从而避免性能退化得太严重
AVL树
最先被发明的平衡二叉树 AVL树,是严格符合定义,高度平衡的二叉查找树.
AVL树 增加和删除操作都可能进行一次或多次 "AVL旋转",实现树的重新平衡
AVL树 节点的左右子树高度差称为 平衡因子,1/0/-1被认为是平衡的.
Adelson-Velsky and Landis Tree 人名命名的
AVL树高度平衡,查找效率非常高,但是为了维持这种平衡付出了更多代价
每次 插入 删除都要做调整,复杂耗时.频繁进行插入删除的操作集合并不适用.
但很多平衡二叉树并没有严格符合 平衡二叉树的定义.例如,开篇中的后三种树.
无需完全符合二叉树定义,尽量平衡,保证高度仍是对数量级,
就仍可以说是合格平衡二叉树.
红黑树
BlackRedTree,一种不严格的平衡二叉树.
要求:
-
根节点黑色
-
叶子节点黑色空节点,不储存数据(简化代码)
-
红色节点不能相邻
-
任意节点 到达其可到达的 任意叶子节点 经过的黑色节点数目 相同
以上要求,使红黑树达到了下面的效果.
-
去掉红节点后的纯黑树高度低于 log2n(毕竟去掉了一些节点)
-
加上红节点,由于红节点不能连续,所以最长路径不超过 2log2n(一红一黑)
也就是说,红黑树高度近似不超过 2log2n.
红黑树高度 比高度平衡的 AVL树 仅仅大了一倍,所以性能上不差很多.
这样推导的结果不够精确,实际上红黑树性能更好
红黑树的插入 删除 查找 各项操作都相对 性能稳定,工业级应用更倾向.