左偏树
左偏树是一种类似小根堆的二叉树,它的根节点总是树中的最小值。左偏树的每次取出/加入操作的时间复杂度为O(log2n),与小根堆相同。与堆不同的是,合并两个数量为n的堆的时间复杂度为O(n×log2n)(因为合并两个堆需要从其中一个取出元素加入另一个,重复n次),而合并两个数量为n的左偏树的时间复杂度为O(log2n)。
左偏树的主要操作有:(1) 合并两个左偏树;(2) 插入新节点;(3) 查找最值;(4) 删除最值。其中(2)−(4)的实现依赖于(1),合并操作是左偏树的核心。
左偏树中的节点的距离d是该节点到最右下叶子节点的距离。左偏树具有以下性质:
(1) 父节点的值小于等于其左右孩子节点的值,即valuefather≤valueleft,valuefather≤valueright。最小的值在根节点类似小根堆的头节点;
(2) 父节点的左孩子节点的距离大于等于右孩子节点的距离,即dleft≥dright;
(3) 父节点的距离等于其右孩子节点的距离加1,即dfather=dright+1;
(4) 具有n个节点的左偏树的根节点的距离小于等于log2(n+1)−1,即droot≤log2(n+1)−1;
下图中每个节点上,上面的数字代表节点的值,下面的数字代表距离。合并两个左偏树的操作,分为两步:
(1) 从根节点开始递归向下合并两个左偏树。每次合并时比较两个子树根节点的值valuea和valueb,总是用根节点较大的子树valueb(设valueb>valuea)替换根节点较小的子树valuea的右孩子节点valuea−left,替换后valuea−left成为新的子树。然后递归的,继续考虑valuea−left作为根节点的子树与valueb作为根节点的子树;
(2) 从叶子节点开始递归向上更新所有节点的距离。对于每个节点,首先若不满足dleft≥dright则将左右孩子子树交换,其次若不满足dfather=dright+1则更新父结点的距离dfather;
下图是合并两个左偏树的过程:
(1) 比较两树的根节点6<7,节点7沿着节点6向右下寻找第1个满足7<x的节点x,替换x作为节点6的新右孩子节点。该节点为节点8(7<8),节点6的原右孩子节点8暂时脱离;
(2) 节点8沿着节点7向右下寻找第1个满足8<x的节点x,替换x作为节点7的新右孩子节点。该节点为节点12(8<12),节点7的原右孩子节点12暂时脱离;
(3) 节点12沿着节点8向右下寻找第1个满足12<x的节点x,替换x作为节点8的新右孩子节点。该节点为节点13(12<13),节点8的原右孩子节点13暂时脱离;
(4) 节点13沿着节点12向右下寻找第1个满足13<x的节点x,替换x作为节点12的新右孩子节点。该节点为节点26(13<26),节点12的原右孩子节点26暂时脱离;
(5) 节点26沿着节点13向右下寻找第1个满足26<x的节点x,节点13没有右孩子节点,因此节点26直接成为节点13的右孩子节点,不再需要替换,合并操作结束;
向右下插入节点的操作会影响到左偏树的平衡性,右子树变得越来越庞大。而且所有节点的距离也是错的(没有更新)。实际上每一步合并操作后还需要检查左右子树的距离属性:(1)对于dleft<dright的情况,交换左右子树;(2)对于droot=dright+1的情况,更新droot。
节点距离的更新必须从叶子节点开始向上进行,对于之前步骤中修改过的节点,重新遍历计算其距离(其中dnil=−1):
(6) 对于节点26,d27=0≥dnil=−1,不需要交换左右子树,更新d26=dnil+1=−1+1=0;
(7) 对于节点13,d28=0≥d26=0,不需要交换左右子树,更新d13=d26+1=0+1=1;
(8) 对于节点12,d31=1≥d26=1,不需要交换左右子树,更新d12=d13+1=1+1=2;
(9) 对于节点8,d10=1<d12=2,需要交换子树10和子树12,更新d8=d10+1=1+1=2;
(10) 对于节点7,d9=1<d8=2,需要交换子树9和子树8,更新d7=d9+1=1+1=2;
(11)对于节点6,d11=2≥d7=2,不需要交换左右子树,更新d6=d7+1=2+1=3;
编码时通过递归的方式将合并和更新距离两个操作放在同一个递归函数中,合并函数Merge返回合并后左偏树的根节点的距离d,在Merge中调用左右孩子的合并操作,获取左右孩子的距离,然后再决定是否交换左右子树,并更新父节点的距离。本文的将两个步骤分开是为了方便理解算法。
左偏树的插入操作,可以看作左偏树与一个只有根节点的左偏树的合并操作;删除最值的操作,可以看作删除根节点后,合并左右子树的操作。
左偏树的合并操作、插入节点操作、删除根节点操作的时间复杂度都为O(log2n)。
源码
LeftistTree.h
LeftistTree.cpp
测试
LeftistTreeTest.cpp