ocaml实现平衡二叉树算法的代码
时间: 2023-01-11 18:55:36 浏览: 96
OCaml 是一门函数式编程语言,它的平衡二叉树的实现方式可能与其他语言略有不同。下面是一个使用 OCaml 的简单平衡二叉树的实现代码:
```
type 'a tree =
| Empty
| Node of 'a tree * 'a * 'a tree * int
let height = function
| Empty -> 0
| Node(_, _, _, h) -> h
let create l x r =
let hl = height l and hr = height r in
Node(l, x, r, (if hl >= hr then hl + 1 else hr + 1))
let bal l x r =
let hl = height l and hr = height r in
if hl > hr + 2 then
match l with
| Node(ll, lv, lr, _) ->
if height ll >= height lr then
create ll lv (create lr x r)
else
(match lr with
| Node(lrl, lrv, lrr, _) ->
create (create ll lv lrl) lrv (create lrr x r)
| Empty -> assert false)
| Empty -> assert false
else if hr > hl + 2 then
match r with
| Node(rl, rv, rr, _) ->
if height rr >= height rl then
create (create l x rl) rv rr
else
(match rl with
| Node(rll, rlv, rlr, _) ->
create (create l x rll) rlv (create rlr rv rr)
| Empty -> assert false)
| Empty -> assert false
else
Node(l, x, r, (if hl >= hr then hl + 1 else hr + 1))
let rec add_leftmost x = function
| Node(l, v, r, h) -> bal (add_leftmost x l) v r
| Empty -> Node(Empty, x, Empty, 1)
let rec add_rightmost x = function
| Node(l, v, r, h) -> bal l v (add_rightmost x r)
| Empty -> Node(Empty, x, Empty, 1)
let rec join l v r =
match (l, r) with
| (Empty, _) -> add_leftmost v r
| (_, Empty) -> add_rightmost v l
| (Node(ll, lv, lr, lh), Node(rl, rv, rr, rh)) ->
if lh > rh + 2 then bal ll lv (join lr v r) else
if rh > lh + 2 then bal (join l v rl) rv rr else
create l v r
let rec split x = function
| Empty ->
(Empty, None, Empty)
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)