# 树
- 节点的高度:节点到子节点的**最长路径**(边数)
- 节点的深度:根节点到这个节点所经历的**边的个数**
- 节点的层数:节点的深度 + 1
- 树的高度:根节点的高度
高度、层数类比楼层,从下往上数;深度类比鱼塘,从上往下数
## 二叉树
- 满二叉树
- 完全二叉树
## 二叉树的遍历
- 前序遍历(对于任意节点,先打印这个节点,再打印它的左子树,最后打印它的右子树)
- 中序遍历(对于任意节点,先打印它的左子树、再打印它本身,最后打印它的右子树)
- 后序遍历(对于任意节点,先打印它的左子,再打印它的右子树,最后打印它本身)
**二叉树的前、中、后序遍历就是一个递归的过程**
## 二叉查找树
在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值
## 对比散列表
1. 散列表的数据无序存储,二叉查找树只需要中序遍历
2. 散列表扩容耗时多,遇到散列冲突时不稳定,平衡二叉查找树性能非常稳定,时间复杂度稳定在 O(logn)
3. 散列表查找复杂度是常量级,但因为哈希冲突,这个常量不一定比 logn 小
4. 散列表的构造比二叉查找树复杂,考虑的东西多,如散列函数的设计、冲突解决办法、扩容、缩容等,平衡二叉查找树只需要考虑平衡性
## 平衡二叉树
二叉树中任意一个节点的左右子树的高度相差不大于 1
平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些
## 红黑树
红黑树中的节点一类被标记为黑色,一类被标记为红色
- 根节点是黑色的;
- 每个叶子节点都是黑色的空节点,也就是说,叶子节点不存储数据
- 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
- 每个节点,从该节点到达其可达叶子节点的所有路径,都包含享同数目的黑色节点;
AVL 树是一种高度平衡的二叉树,查找效率非常高,但是为了维持这种平衡,要付出更多代价,每次插入、删除都要做调整,复杂且耗时
红黑树只是近似平衡,不是严格平衡,所以维护平衡的成本上比 AVL 树要低,因此对于工程应用来说为了面对各种异常情况,支撑工业级应用,倾向于性能稳定的红黑树
红黑树实现困难,对平时开发帮助不大,不需要亲手写一个红黑树,对面试帮助也不大,有的放矢
![avatar](https://profile-avatar.csdnimg.cn/bc3c40a1700d40bc91a04af0dc7133fa_weixin_41883161.jpg!1)
九转成圣
- 粉丝: 3644
- 资源: 2956
最新资源
- Carsim Simulink联合仿真基于LQR 模糊PID 滑模控制的横摆稳定性控制系统 综合跟随理想横摆角速度的方法和抑制汽
- 江科大STM32学习笔记(上)
- 基于MFC实现ModbusRTU转ModbusTCP的源码
- 串联式、并联式、混联式混合动力系统simulink控制策略模型(串联式、并联式、混联式每个都是独立的需要单独说拿哪个,默认是混联
- NiceCat.zip
- svn客户端安装包 windows 环境
- 蒙特卡洛模拟两相流气泡pdp-sim-tbf-master.zip
- 30a4882db91186b8.png
- 蒙特卡洛五子棋typescript实现mcts-ts-main.zip
- 使用WinRAR打开RAR文件.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)