高度平衡树 -- AVL 树

2024-06-14 15:48
文章标签 平衡 avl 高度

本文主要是介绍高度平衡树 -- AVL 树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Scheme 的表达, 优雅.


#lang scheme


( define nil '() )
( define ( root tree )( car tree ) )
( define ( left-tree tree )( cadr tree ) )
( define ( right-tree tree )( caddr tree ) )
( define ( height tree )
   ( cond [ ( null? tree ) 0 ]
          [ else ( cadddr tree ) ] ) )


( define ( make-leaf elem )( list elem nil nil 1 ) )


( define ( make-avl-tree root left right )
   ( list root left right ( + 1 ( max ( height left )
                                      ( height right ) ) ) ) )

( define ( contains-elem? elem tree )
   ( cond [ ( null? tree ) false ]
          [ ( = elem ( root tree ) ) true ]
          [ ( < elem ( root tree ) )
            ( contains-elem? elem ( left-tree tree ) ) ]
          [ ( > elem ( root tree ) )
            ( contains-elem? elem ( right-tree tree ) ) ] ) )

( define ( rotate-left-left tree )
   ( cond [ ( null? tree ) tree ]
          [ else ( make-avl-tree ( root ( left-tree tree ) )
                                 ( left-tree ( left-tree tree ) )
                                 ( make-avl-tree ( root tree )
                                                 ( right-tree ( left-tree tree ) )
                                                 ( right-tree tree ) )  ) ] ) )

( define ( rotate-right-right tree )
   ( cond [ ( null? tree ) tree ]
          [ else ( make-avl-tree ( root ( right-tree tree ) )
                                 ( make-avl-tree ( root tree )
                                                 ( left-tree tree )
                                                 ( left-tree ( right-tree tree ) ) ) 
                                 ( right-tree ( right-tree tree ) ) ) ] ) )

( define ( rotate-right-left tree )
   ( cond [ ( null? tree ) tree ]
          [ else ( make-avl-tree ( left-tree ( right-tree tree ) )
                                 ( make-avl-tree ( root tree )
                                                 ( left-tree tree )
                                                 ( left-tree ( left-tree ( right-tree tree ) ) ) )
                                 ( make-avl-tree ( root ( right-tree tree ) )
                                                 ( right-tree ( left-tree ( right-tree tree ) ) )
                                                 ( right-tree ( right-tree tree ) ) ) ) ] ) )

( define ( rotate-left-right tree )
   ( cond [ ( null? tree ) tree ]
          [ else ( make-avl-tree ( root ( right-tree ( left-tree tree ) ) )
                                 ( make-avl-tree ( root ( left-tree tree ) )
                                                 ( left-tree ( left-tree tree ) )
                                                 ( left-tree ( right-tree ( left-tree tree ) ) ) )
                                 ( make-avl-tree ( root tree )
                                                 ( right-tree ( right-tree ( left-tree tree ) ) )
                                                 ( right-tree tree ) ) ) ] ) )

( define ( balance-avl-tree tree )
   ( define ( factor tree )
      ( - ( height ( right-tree tree ) )
          ( height ( left-tree tree ) ) ) )
   ( let ( [ f ( factor tree ) ] )
      ( cond [ ( = f 2 )
               ( cond [ ( < ( factor ( right-tree tree ) ) 0 )
                        ( rotate-right-left tree ) ]
                      [ else ( rotate-right-right tree ) ] ) ]
             [ ( = f -2 )
               ( cond [ ( > ( factor ( left-tree tree ) ) 0 )
                        ( rotate-left-right tree ) ]
                      [ else ( rotate-left-left tree ) ] ) ]
             [ else tree ] ) ) )

( define ( insert-elem elem tree )
   ( define ( insert-in-son elem tree )
      ( cond [ ( null? tree )
               ( make-leaf elem ) ]
             [ ( < elem ( root tree ) )
               ( let* ( [ newLeftTree ( insert-in-son elem ( left-tree tree ) ) ]
                        [ newAVLTree ( make-avl-tree ( root tree )
                                                     newLeftTree
                                                     ( right-tree tree ) ) ] )
                  ( balance-avl-tree newAVLTree ) ) ]
             [ ( > elem ( root tree ) )
               ( let* ( [ newRightTree ( insert-in-son elem ( right-tree tree ) ) ]
                        [ newAVLTree ( make-avl-tree ( root tree )
                                                     ( left-tree tree )
                                                     newRightTree ) ] )
                  ( balance-avl-tree newAVLTree ) ) ]
             [ else tree ] ) )
   ( cond [ ( contains-elem? elem tree ) tree ]
          [ else ( insert-in-son elem tree ) ] ) )

( define ( delete-elem elem tree )
   ( define ( delete-left-most tree )
      ( cond [ ( left-empty? tree ) tree ]
             [ else ( let* ( [ leftMost ( delete-left-most ( left-tree tree ) ) ]
                             [ newRightTree ( make-avl-tree ( root tree )
                                                            ( right-tree leftMost )
                                                            ( right-tree tree ) ) ] )
                       ( make-avl-tree ( root leftMost )
                                       nil
                                       ( balance-avl-tree newRightTree ) ) ) ] ) )
   ( define ( delete-in-son elem tree )
      ( cond [ ( < elem ( root tree ) )
               ( let* ( [ newLeftTree ( delete-in-son elem ( left-tree tree ) ) ]
                        [ newAVLTree ( make-avl-tree ( root tree )
                                                     newLeftTree
                                                     ( right-tree tree ) ) ] )
                  ( balance-avl-tree newAVLTree ) ) ]
             [ ( > elem ( root tree ) )
               ( let* ( [ newRightTree ( delete-in-son elem ( right-tree tree ) ) ]
                        [ newAVLTree ( make-avl-tree ( root tree )
                                                     ( left-tree tree )
                                                     newRightTree ) ] )
                  ( balance-avl-tree newAVLTree ) ) ]
             [ ( = elem ( root tree ) )
               ( cond [ ( and ( right-empty? tree )
                              ( left-empty? tree ) )
                        nil ]
                      [ ( right-empty? tree )
                        ( left-tree tree ) ]
                      [ ( left-empty? tree )
                        ( right-tree tree ) ]
                      [ else ( let ( [ leftMost ( delete-left-most ( right-tree tree ) ) ] )
                                ( make-avl-tree ( root leftMost )
                                                ( left-tree tree )
                                                ( right-tree leftMost ) ) ) ] ) ] ) )
   ( define ( left-empty? tree )( null? ( left-tree tree ) ) )
   ( define ( right-empty? tree )( null? ( right-tree tree ) ) )
   ( cond [ ( contains-elem? elem tree )
            ( delete-in-son elem tree ) ]
          [ else tree ] ) )

( define ( list->avl elems )
   ( define ( iter elems tree )
      ( cond [ ( null? elems ) tree ]
             [ else ( iter ( cdr elems ) 
                           ( insert-elem ( car elems ) tree ) ) ] ) )
   ( cond [ ( null? elems ) '() ]
          [ else ( let( [ avl ( make-leaf ( car elems ) ) ] )

                    ( iter ( cdr elems ) avl ) ) ] ) )





这篇关于高度平衡树 -- AVL 树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1060841

相关文章

Weex入门教程之4,获取当前全局环境变量和配置信息(屏幕高度、宽度等)

$getConfig() 获取当前全局环境变量和配置信息。 Returns: config (object): 配置对象;bundleUrl (string): bundle 的 url;debug (boolean): 是否是调试模式;env (object): 环境对象; weexVersion (string): Weex sdk 版本;appName (string): 应用名字;

240907-Gradio插入Mermaid流程图并自适应浏览器高度

A. 最终效果 B. 示例代码 import gradio as grmermaid_code = """<iframe srcdoc='<!DOCTYPE html><html><head><meta charset="utf-8" /><meta name="viewport" content="width=device-width" /><title>My static Spa

写给大数据开发:你真的“慢“了吗?揭秘技术与职场的平衡艺术

你是否曾经在深夜里,面对着一个棘手的数据处理问题,感到无比沮丧?或者在一次重要的项目汇报中,突然语塞,无法清晰地表达你的技术方案?作为一名大数据开发者,这些场景可能再熟悉不过。但别担心,因为你并不孤单。让我们一起探讨如何在这个瞬息万变的行业中,既磨练技术利刃,又培养职场软实力。 目录 技术与时间的赛跑1. 长远视角的重要性2. 复利效应在技能学习中的应用 跨界思维:数据结构教我们的职场智

代码随想录 -- 二叉树 -- 平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode) 思路:仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数:如果传入根节点为空返回真;如果根节点 | 左子树的层数 - 右子树的层数 | 大于1,返回假;最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root

兔子--计算listview的高度,解决listview与scrollview控件冲突

/** * 计算ListView的高度 * * @param listView */ public void setListViewHeightBasedOnChildren(ListView listView) { // 获取ListView对应的Adapter OrderGoodsAdapter listAdapter = (OrderGoodsAdapter) listView.getAda

智能匹配新高度:相亲交友系统如何运用AI技术提升用户体验

在数字化时代,相亲交友系统正逐渐融入人工智能(AI)技术,以提升用户体验和匹配效率。AI的引入不仅改变了传统的交友方式,还为用户带来了更加个性化和精准的交友体验。以下是一篇关于如何运用AI技术提升相亲交友系统用户体验的文章。 智能匹配新高度:相亲交友系统如何运用AI技术提升用户体验 随着人工智能技术的飞速发展,相亲交友系统正迎来一场革命。AI的引入不仅提高了匹配的精准度,还极大地丰富了

AVL 树的旋转

什么是 AVL 树? AVL 树是一种自平衡二叉搜索树(Binary Search Tree, BST),以其发明者 G. M. Adelson-Velsky 和 E. M. Landis 的名字命名。它的特点是对于任意一个节点,其左右子树的高度差(平衡因子)不超过 1,这确保了 AVL 树的高度在 O(log n) 的范围内,从而保证了插入、删除和查找操作的时间复杂度都是 O(log n)。

cesium 使用异步函数 getHeightAtPoint,获取指定经纬度点的地形高度。

这个函数使用 CesiumJS 库的 sampleTerrain 方法来获取地形数据。下面是代码的详细解释: async getHeightAtPoint(LngLat) {// 将经纬度转为 Cartographic 对象let cartographics = [Cesium.Cartographic.fromDegrees(LngLat[0], LngLat[1])];// console.

构建STM32智能平衡车项目:PID控制算法与蓝牙通信技术

一、项目概述 项目目标和用途 本项目旨在设计和实现一款基于STM32单片机的平衡车。平衡车是一种新型的个人交通工具,广泛应用于短途出行、休闲娱乐等场景。通过本项目,我们希望能够实现一款具备良好稳定性和操控性的平衡车,能够在不同的地形上自如行驶。 解决的问题和带来的价值 平衡车的核心问题在于如何保持其平衡。传统的平衡车往往依赖于复杂的控制算法和高精度的传感器。通过本项目,我们将利用STM32

二叉搜索树、平衡二叉树、B树、B+树、B*树

二叉查找树 二叉查找树,由于不平衡,如果连续插入的数据是有顺序的、会导致如下图B的所示,此时搜索会退化到O(N)   二叉查找树,也称二叉搜索树,或二叉排序树。其定义也比较简单,要么是一颗空树,要么就是具有如下性质的二叉树: (1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2) 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3) 任