AVL树-cis_orcad 本地数据库配置方法

【文件属性】：

文件名称：AVL树-cis_orcad 本地数据库配置方法

文件大小：5.89MB

文件格式：PDF

更新时间：2024-06-28 07:12:11

数据结构 邓俊辉

§7.4 AVL树 在适当放宽“平衡”的标准并借助以上介绍的等价变换之后，AVL树（AVL tree） ② 可 以实现二叉搜索树近乎理想的平衡。在渐进复杂度的意义下，AVL树可始终将其高度控制在 O(logn)以内，从而保证每次查找、插入或删除操作均可在O(logn)的时间内完成。 7.4.1 定义及性质  平衡因子 任一节点v的平衡因子（balance factor）定义为“其左、右子树的高度差”，即 balFac(v) = height(lc(v)) - height(rc(v)) 请注意，本书中空树高度取-1，单节点子树（叶节点）高度取0，与以上定义没有冲突。  接口定义 AVL树即平衡因子受限的二叉搜索树其中所有节点平衡因子的绝对值均不超过1。 基于BST模板类（203页代码7.2），可直接派生出AVL模板类如代码7.8所示。 1 #include "../BST/BST.h" //基二BST实现AVL树 2 template class AVL : public BST { //由BST派生AVL树模板类 3 public: 4 BinNodePosi(T) insert(const T& e); //揑入（重写） 5 bool remove(const T& e); //初除（重写） 6 // BST::search()等其余接口可直接沿用 7 }; 代码7.8 基二BST定丿癿AVL树接口 可见，这里直接沿用了BST模板类的search()等接口，并根据AVL树的重平衡规则与算 法，重写了insert()和remove()接口，其具体实现将在后续数节陆续给出。 ② 由G. M. Adelson-Velsky和E. M. Landis不1962年収明 [35] ，幵以他们名字癿首字殎命名