AVL Tree in a pattern matching way
Larry, LIU Xinyu
刚刚用pattern matching实现了一个AVL tree。
AVL tree也是一种balanced BST，它在保持平衡的方法上也是利用旋转，这点和红黑树类似。
具体请参见http://en.wikipedia.org/wiki/AVL_tree
这里不再赘述。我大致搜了下目前的纯函数式AVL tree实现，Haskell的和CAML的。都是插入前判断属于哪个case，然后进行旋转，这样
的代码长度很大，case也比较多。需要特别仔细的编程，比较复杂。
参见：
http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/src/Data-Tree-AVL-Push.html#pushL
以及
BOOK： the functional approach to programming pp173 ~ 186
收到Chris Okasaki的红黑树实现的启发，我用pattern matching的方法实现了AVL树，相比前面的两个例子，简化了很多。现
在分享代码如下：
-- 首先是定义：
data AVLTree a = Empty
| Br (AVLTree a) a (AVLTree a) Int
-- 可以看到AVL树和BST比起来，仅仅多了一个delta域，它用来记录一个节点的右侧高度和左侧高度的差，
-- AVL tree规定delta <=1，通过这个规定来确保树的平衡。
-- 下面是插入函数，将一个有序元素插入AVL tree
-- 我们实际就是调用一个内部函数ins，每次插入ins返回一对值：（插入结果树，和树高度的增加值）
insert::(Ord a)=>AVLTree a -> a -> AVLTree a
insert t x = fst $ ins t where
-- result of ins is a pair (t, d), t: tree, d: increment of height
ins Empty = (Br Empty x Empty 0, 1) -- 平凡情况
ins (Br l k r d)
| x < k = node (ins l) k (r, 0) d
| x == k = (Br l k r d, 0)
| otherwise = node (l, 0) k (ins r) d
-- params: (left, increment on left) key (right, increment on right)
node::(AVLTree a, Int) -> a -> (AVLTree a, Int) -> Int -> (AVLTree a,
Int)
node (l, dl) k (r, dr) d = balance (Br l k r d', delta) where
d' = d + dr - dl
delta = deltaH d d' dl dr
-- delta(Height) = max(|R'|, |L'|) - max (|R|, |L|)
-- where we denote height(R) as |R|
deltaH :: Int -> Int -> Int -> Int -> Int
deltaH d d' dl dr
| d >=0 && d' >=0 = dr
| d <=0 && d' >=0 = d+dr
| d >=0 && d' <=0 = dl - d
| otherwise = dl
-- 最重要的pattern matching部分，简化后，只有4个case
balance :: (AVLTree a, Int) -> (AVLTree a, Int)
balance (Br (Br (Br a x b dx) y c (-1)) z d (-2), _) = (Br (Br a x b
dx) y (Br c z d 0) 0, 0)
balance (Br a x (Br b y (Br c z d dz) 1) 2, _) = (Br (Br a x b
0) y (Br c z d dz) 0, 0)
balance (Br (Br a x (Br b y c dy) 1) z d (-2), _) = (Br (Br a x b
dx') y (Br c z d dz') 0, 0) where
dx' = if dy == 1 then -1 else 0
dz' = if dy == -1 then 1 else 0
balance (Br a x (Br (Br b y c dy) z d (-1)) 2, _) = (Br (Br a x b
dx') y (Br c z d dz') 0, 0) where
dx' = if dy == 1 then -1 else 0
dz' = if dy == -1 then 1 else 0
balance (t, d) = (t, d)
-- 下面的函数用于测试：
-- check if a AVLTree is valid
isAVL :: (AVLTree a) -> Bool
isAVL Empty = True
isAVL (Br l _ r d) = and [isAVL l, isAVL r, d == (height r - height
l), abs d <= 1]
height :: (AVLTree a) -> Int
height Empty = 0
height (Br l _ r _) = 1 + max (height l) (height r)
-- Auxiliary functions to build tree from a list, as same as BST
fromList::(Ord a)=>[a] -> AVLTree a
fromList = foldl insert Empty
toList :: (AVLTree a) -> [a]
toList Empty = []
toList (Br l k r _) = toList l ++ [k] ++ toList r
-- test
prop_bst :: (Ord a, Num a) => [a] -> Bool
prop_bst xs = (L.sort $ L.nub xs) == (toList $ fromList xs)
prop_avl :: (Ord a, Num a) => [a] -> Bool
prop_avl = isAVL . fromList . L.nub
下面是测试结果：
*AVLTree> test prop_avl
OK, passed 100 tests.
代码已经push到github上，感兴趣的各位可以参考：
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/tree/AVL-tree/src/AVLTree.hs
open audio
Larry, LIU Xinyu
http://groups.google.com/group/haskell-cafe/browse_thread/thread/35d6229c41a02ea9
On May 12, 11:31 am, open audio <openau...@gmail.com> wrote:
> 真是肯钻研，只可惜这里应者寥寥无几，不知道是否在哪个E文技术社区中有张贴，能不能贴出来，如果没有的话，
> 应该考虑一下。
>
> 在 2011年5月12日 上午10:38，Larry, LIU Xinyu <liuxiny...@gmail.com>写道：
>
>
>
>
>
>
>
> > Hi,
>
> > 刚刚用pattern matching实现了一个AVL tree。
> > AVL tree也是一种balanced BST，它在保持平衡的方法上也是利用旋转，这点和红黑树类似。
> > 具体请参见http://en.wikipedia.org/wiki/AVL_tree
> > 这里不再赘述。我大致搜了下目前的纯函数式AVL tree实现，Haskell的和CAML的。都是插入前判断属于哪个case，然后进行旋转，这样
> > 的代码长度很大，case也比较多。需要特别仔细的编程，比较复杂。
> > 参见：
>
> >http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/src/...
> >https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/tree/AVL-...
>
> > --
> > LIU
> >https://github.com/liuxinyu95/AlgoXY
Wang Fei
----
Wang Fei
M.Eng. in Telecommunications Engineering
Larry, LIU Xinyu
C的可以参考这个：
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
对比下就能看到化简的程度了。
--
LIU
On May 12, 6:24 pm, Wang Fei <pytho...@gmail.com> wrote:
> 支持啊
>
> 以前上课的时候要用C/C++编，现在都不敢想了
>
> ----
> Wang Fei
> M.Eng. in Telecommunications Engineering
>
> 2011/5/12 Larry, LIU Xinyu <liuxiny...@gmail.com>
>
>
>
>
>
>
>
> > 也贴了一份在Haskell-Cafe:
>
> >http://groups.google.com/group/haskell-cafe/browse_thread/thread/35d6...
Larry, LIU Xinyu
AVL tree一文大纲：
1. 介绍，包括定义，问题解决思路等；
2. 类比Red-black tree的思路；
3. 解：
3.1 解的形式， Pattern matching
3.2 子问题1： 如何更新delta和height
3.3 子问题2： 4个case的分析，并给出其中delta'如何变化的推导和证明；
4. 验证
5. 略去删除的理由，以及练习题；
6. 对比一下传统的解法（基于树旋转），给出传统解法的pseudo code算法描述；
7. 对比和红黑树的差异，并得出AVL和红黑树应用上的差异，应用一些评论。
--
LIU
https://github.com/liuxinyu95/AlgoXY
Larry, LIU Xinyu
今天想证明AVL tree的高度和节点数的关系
1. WIKI给出的结论是： h is strictly less than log_{\phi}(n+2)-1. 其中\phi是黄金分割率
(\sqrt(5)+1)/2
2. The functional approach to programing给出的是h is bound to 1.44 log_2(n
+2)
3. 某大学的open course lecture给出的结论是h < 1.44 log n
CLRS上 problem 13.3 要求读者证明height是O(lg N)
到底哪个是正确的？首先无论1， 2， 3都是O(lg N).
我们试着证明下：
denote N(h) 为高度为h的AVL树的最少节点个数；我们很容易得出平凡情况：
N(0) = 0 (空树)
N(1) = 1 (一个根节点)
现在考虑一般情况，一个高度为h的数，它分为3个部分：根节点，子树A，和子树B；这里A可以是左子树，也可以是右子树。
不妨设A的高度为h-1，然后考虑B的高度，根据AVL数的定义|height(A) - height(B)| <= 1；
所以B的高度height(B)>=h-2。
于是我们有
N(h) = 1 + N(h-1) + N(h-2)
也就是说，高度为H的AVL树的最小节点个数，为1个根节点，加上高度为h-1的AVL数最小节点个数和高度为h-2的AVL树的最小节点个数。
这个公式看起来眼熟，似乎有点想Fibonacci数列。如果我们定义N'(h) = N(h) + 1则这个公式就变化为：
N'(h) = N'(h-1) + N'(h-2)
这就是Fibonacci数列了。
我们可以直接利用Fibonacci数列的性质，也可以自己证明一把： N'(h) >= \phi^h
使用数学归纳法：
h = 0 的时候， N'(0) = 1 >= \phi^0
h = 1 的时候， N'(1) = 2 > \phi^1 = (\sqrt(5)+1)/2 = 1.618
假设N'(h) >= \phi^h
有 N'(h+1) = N'(h) + N'(h-1) >= \phi^h + \phi^{h-1}
= \phi^{h-1}*(\phi+1)
注意到\phi+1 = (\sqrt(5)+3)/2 = \phi^2
故 N'(h+1) >= \phi^{h-1}*\phi^2 = \phi^{h+1}
证明完毕。
于是有N'(h) = N(h)+1 >= \phi^h
故 h <= log_{\phi}(N(h)+1) 而N(h)<=N，所以有
h <= log_{\phi}(N+1)
这个结论似乎和1, 2, 3都不一样，事实上。我们可以证明1。
我们前面证明了N'(h)>=\phi^h, 事实上，还可以证明N'(h)>\phi^{h+1}-1
仍然用数学归纳法：
N'(0)=1 > \phi^1-1=0.618
N'(1)=2 > \phi^2-1=1.618
N'(h+1) = N'(h)+N'(h-1) > \phi^{h+1}-\phi^{h} = \phi^h(1-\phi) =
\phi^{h+2} > \phi^{h+2} - 1
证明完毕
所以直接可以得到 h < log_{\phi}(n+2)-1
所以1得证，由于这里是严格小于，考虑h是整数，故 h <= log_{\phi}(n+2) = log_{2}(n+2)/log_{2}
(\phi) = 1.44 log_{2}(n+2)
所以2得证。
事实上，还可以证明N(h) > \phi^h。方法也是数学归纳法。这里不赘述了。
于是有 h < log_{\phi}(N) = 1.44 log_{2}(N)
这就证明了3。
--
LIU
https://github.com/liuxinyu95/AlgoXY
--
[1]. http://en.wikipedia.org/wiki/AVL_tree
On May 17, 9:40 am, "Larry, LIU Xinyu" <liuxiny...@gmail.com> wrote:
> 列了个提纲，争取秋天前写完：
>
> AVL tree一文大纲：
>
> 1. 介绍，包括定义，问题解决思路等；
> 2. 类比Red-black tree的思路；
> 3. 解：
> 3.1 解的形式， Pattern matching
> 3.2 子问题1： 如何更新delta和height
> 3.3 子问题2： 4个case的分析，并给出其中delta'如何变化的推导和证明；
> 4. 验证
> 5. 略去删除的理由，以及练习题；
> 6. 对比一下传统的解法（基于树旋转），给出传统解法的pseudo code算法描述；
> 7. 对比和红黑树的差异，并得出AVL和红黑树应用上的差异，应用一些评论。
>
> --
> LIUhttps://github.com/liuxinyu95/AlgoXY
Larry, LIU Xinyu
五一节时，我说用3个月把AVL树写好，今天总算完成了。
AVL树发明于上世纪60年代，比红黑树早了近十年。
上一章里，我展示了用pattern matching实现的红黑树。本章我展示同样策略实现的AVL tree。相比于传统的基于旋转的解法，这一解法再次展示了简单一致的特点。
本章内容如下：
- 简单介绍；给出AVL树的高度与节点数的证明；
- 类比红黑树的思路；
- 解：
- pattern matching 的形式分析
- 子问题一： 如何更新平衡因子和增加的高度？
- 子问题二； 4个case中的平衡因子如何变化的推导和证明；
- Haskell实现
- 验证
- 删除算法作为习题留给读者
- 和传统旋转解法的对比，给出了算法描述和Python实现
- 对比和红黑树的差异。
原文
https://sites.google.com/site/algoxy/avltree
PDF我放了一份在github，省得读者翻墙了：
https://github.com/downloads/liuxinyu95/AlgoXY/avltree-en.pdf
还有一份在iteye:
http://liuxinyu95.iteye.com/admin/blogs/1149602
源代码：
https://github.com/liuxinyu95/AlgoXY
Xinyu LIU
https://github.com/downloads/liuxinyu95/AlgoXY/preface-en.pdf
https://github.com/downloads/liuxinyu95/AlgoXY/bstree-en.pdf
https://github.com/downloads/liuxinyu95/AlgoXY/rbtree-en.pdf
--
Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY
linux JHON
收下了，慢慢研究～
error right
Xinyu LIU
https://sites.google.com/site/algoxy/btree
其实简单来说，B树就是把平衡二叉树扩展到K-ary的情形。