数据结构与算法分析第四章

第四章讲的是树这种结构，这种结构的大部分操作的运行时间平均为logN，其中重点是二叉搜索树（代码实现）。本章的主要内容：

• 了解树是如何实现文件系统的
• 树如何来计算表达式的值
• 如何利用树支持一O（logN）平均时间进行的各种搜索操作，以及如何细化到最坏情况下时间界O（logN）的。

简单介绍一下树这种数据结构，树这种结构可以联想到家谱，一层一层的向下传递，树的一些属性：

• 一棵树的最上层的一个节点为根（root）
• 一个节点与下一层节点相连，则这个节点称作下一层相连节点的父节点（parent）
• 除去根节点外，每个节点都有一个父节点
• 具有同一个父节点的一组节点互称兄弟节点（brother）
• 没有儿子的节点称为树叶（leaf）
• 一个节点的深度（depth）为从根节点到该节点的唯一路径长，因此根的深度为0
• 一个节点的高（height）为该节点到一个树叶最长路径，因此树叶的高为0
• 一棵树的深度为最深的树叶的深度

一些特殊的树：

• 二叉查找树√
• AVL树√
• 伸展树？
• B-树（非二叉的查找树）

我们使用二叉树的原因是希望它的大部分操作消耗平均能在logN，但是有些情况（这些情况很常见），比如删除操作，会使得二叉树左子树比右子树深度深得多，原因在于上述的删除算法有助于左子树比右子树深，那样的话二叉树的深度就不能保持在logN左右，这样的树是不平衡的，所以我们用AVL树来填补这种不平衡；

AVL树是带有平衡条件的树，也就是说，在检测到左右子树深度相差大于1时，会自动平衡各个节点来使得树保持平衡，这样我们可以保持大部分操作的平均消耗在logN