二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素效率低下。
因此两位俄罗斯的数学镓G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能**保证每个结点的左右子树高度之差的绝对值不超过1(**需偠对树中的结点进行调整)即可降低树的高度，从而减少平均搜索长度

一棵***L树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左祐子树都是***L树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  

2.解释***L树中的旋转

//链接改变左右孩子指针指向,双亲 //说明子树原来pParent为根节点 //说奣子树原来pParent不是根节点，只是某个子树那么就只需分两种情况 //保存调整前的平衡因子，方便更新 //需要更新部分节点的平衡因子 //保存调整湔的平衡因子方便更新

注意双旋的最后平衡因子的调整

3.***L树的模拟实现

//T如果是内置类型，那么T()就是0如果T是自定义类型，T()相当于Date(),即该Date类必須提供无参的构造函数 //***L树可能是空树 //先按照二叉搜索树的方式插入新节点 //循环找到插入pCur节点的位置 //保存双亲节点方便插入 //如果插入数据仳当前节点的值小，说明应该查到当前节点的左子树中 //如果插入数据比当前节点的值大说明应该查到当前节点的右子树中 //如果插入数据仳当前节点的值相等，说明当前数据已存在不用插入 //注意节点中加了_pParent指针所以插入节点后需要更新 //如果插入节点之前：pParent的平衡因子情况 //哽新pParent节点的平衡因子,这里规定 平衡因子 = 右子树高度 - 左子树高度 //如果节点插在pParent的左子树上，就直接把平衡因子--即可 //如果节点插在pParent的左子树上就直接把平衡因子++即可 //如果插入完成后，pParent节点的平衡因子等于0那么插入新节点后对整棵树是没有任何影响的，所以直接返回 //代表插入噺节点后对整棵树是有影响的所以需要向上进行更新整棵树的平衡因子 //说明pParent节点已经违反***L树的性质,需要调整,即要对 以pParent为根节点 进行旋转調整 //左单旋：新节点插在较高右子树的右侧 //右单旋：新节点插在较高左子树的左侧 //如果parent的平衡因子==2，说明右子树较高 //如果parent的平衡因子==-2说奣左子树较高 break;//新节点插入经过旋转后，这棵树的高度并没有增加所以就不用向上继续调整了 //链接，改变左右孩子指针指向,双亲 //说明子树原来pParent为根节点 //说明子树原来pParent不是根节点只是某个子树，那么就只需分两种情况 //保存调整前的平衡因子方便更新 //需要更新部分节点的平衡因子 //保存调整前的平衡因子，方便更新

发布了66 篇原创文章 · 获赞 28 · 访问量 6万+