fbpx
维基百科

AVL树

一月 06, 2023

AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的時間複雜度都是。增加和删除元素的操作则可能需要藉由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis（英语：E. M. Landis），他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

AVL樹
类型樹
发明时间1962
发明者格奥尔吉·阿杰尔松-韦利斯基及E. M. Landis（英语：Evgenii Landis）
用大O符号表示的时间复杂度
算法 平均 最差
空间 O(n) O(n)
搜索 O(log n) O(log n)
插入 O(log n) O(log n)
删除 O(log n) O(log n)
非AVL树的例子

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有時相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

同一个树在高度平衡之后的样子

操作

 
此动画演示了不断将节点插入AVL树时的情况，并且演示了左旋（Left Rotation）、右旋（Right Rotation）、右左旋转（Right-Left Rotation）、左右旋转（Left-Right Rotation）以及带子树的右旋（Right Rotation with children）。

AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。

以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。

 

删除

从AVL树中删除，可以通过把要删除的节点向下旋转成一个葉子節點，接着直接移除这个叶子节点来完成。因为在旋转成葉子節點期间最多有log n个节点被旋转，而每次AVL旋转耗费固定的时间，所以删除处理在整体上耗费O(log n) 时间。

搜尋

可以像普通二叉查找树一样的进行，所以耗费O(log n)时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展樹搜尋相对立的，它会因为搜尋而变更树结构。）

实现描述

假設平衡因子是左子樹的高度減去右子樹的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：

  1. 单向右旋平衡处理LL：由于在*a的左子树根节点的左子树上插入节点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
  2. 单向左旋平衡处理RR：由于在*a的右子树根节点的右子树上插入节点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
  3. 双向旋转（先左后右）平衡处理LR：由于在*a的左子树根节点的右子树上插入节点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
  4. 双向旋转（先右后左）平衡处理RL：由于在*a的右子树根节点的左子树上插入节点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

在平衡的二叉排序树BBST (Balancing Binary Search Tree)上插入一个新的数据元素e的递归算法可描述如下：

  1. 若BBST为空树，则插入一个数据元素为e的新节点作为BBST的根节点，树的深度增1；
  2. 若e的关键字和BBST的根节点的关键字相等，则不进行；
  3. 若e的关键字小于BBST的根节点的关键字，而且在BBST的左子树中不存在和e有相同关键字的节点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：
    1. BBST的根节点的平衡因子为-1（右子树的深度大于左子树的深度，则将根节点的平衡因子更改为0，BBST的深度不变；
    2. BBST的根节点的平衡因子为0（左、右子树的深度相等）：则将根节点的平衡因子更改为1，BBST的深度增1；
    3. BBST的根节点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根节点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；
  4. 若e的关键字大于BBST的根节点的关键字，而且在BBST的右子树中不存在和e有相同关键字的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

AVL树的调平（Erlang的实现） 

balance(null) -> null; balance({null, _, null}=Tree) -> Tree; balance({Left, Value, Right}=Tree) ->  Diff = count(Left)-count(Right),  if (Diff < 2) and (Diff > -2) -> {balance(Left), Value, balance(Right)};  (Diff > 1) -> balance(rotate_right(Tree));  (Diff< -1) -> balance(rotate_left(Tree));  true -> exit('This is impossible!')  end.  rotate_right({Left, Value, Right}) ->  merge_max(Left, {null, Value, Right}).  rotate_left({Left, Value, Right}) ->  merge_min(Right, {Left, Value, null}).  merge_min({null, Value, Right}, Tree2) ->  {Tree2, Value, Right}; merge_min({Left, _, _}, Tree2) ->  merge_min(Left, Tree2).  merge_max({Left , Value, null}, Tree2) ->  {Left, Value, Tree2}; merge_max({_, _, Right}, Tree2) ->  merge_max(Right, Tree2).

AVL節點數計算

高度為h的AVL樹，總節點數N最多 ； 最少節點數 如以斐波那契數列可以用數學歸納法證明：
  =   - 1 ( 是斐波那契数列的第h+2项，根据斐波那契多项式得来)。
即:
  = 0 (表示AVL Tree高度為0的節點總數)
  = 1 (表示AVL Tree高度為1的節點總數)
  = 2 (表示AVL Tree高度為2的節點總數)
  =   +   + 1 (表示AVL Tree高度為h的節點總數)
換句話說，當節點數為N時，高度h最多為 。

参见

引用

  • G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962（Russian）. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.

外部链接

一月 06, 2023
avl树, adelson, velsky, landis, tree, 是计算机科学中最早被发明的自平衡二叉查找树, 在中, 任一节点对应的两棵子树的最大高度差为1, 因此它也被称为高度平衡树, 查找, 插入和删除在平均和最坏情况下的時間複雜度都是o, displaystyle, 增加和删除元素的操作则可能需要藉由一次或多次树旋转, 以实现树的重新平衡, 得名于它的发明者g, adelson, velsky和evgenii, landis, 英语, landis, 他们在1962年的论文, algorithm, . AVL树 Adelson Velsky and Landis Tree 是计算机科学中最早被发明的自平衡二叉查找树 在AVL树中 任一节点对应的两棵子树的最大高度差为1 因此它也被称为高度平衡树 查找 插入和删除在平均和最坏情况下的時間複雜度都是O log n displaystyle O log n 增加和删除元素的操作则可能需要藉由一次或多次树旋转 以实现树的重新平衡 AVL树得名于它的发明者G M Adelson Velsky和Evgenii Landis 英语 E M Landis 他们在1962年的论文 An algorithm for the organization of information 中公开了这一数据结构 AVL樹类型樹发明时间1962发明者格奥尔吉 阿杰尔松 韦利斯基及E M Landis 英语 Evgenii Landis 用大O符号表示的时间复杂度算法平均最差空间O n O n 搜索O log n O log n 插入O log n O log n 删除O log n O log n 非AVL树的例子 节点的平衡因子是它的左子树的高度减去它的右子树的高度 有時相反 带有平衡因子1 0或 1的节点被认为是平衡的 带有平衡因子 2或2的节点被认为是不平衡的 并需要重新平衡这个树 平衡因子可以直接存储在每个节点中 或从可能存储在节点中的子树高度计算出来 同一个树在高度平衡之后的样子 目录 1 操作 1 1 删除 1 2 搜尋 2 实现描述 3 AVL節點數計算 4 参见 5 引用 6 外部链接操作 编辑 此动画演示了不断将节点插入AVL树时的情况 并且演示了左旋 Left Rotation 右旋 Right Rotation 右左旋转 Right Left Rotation 左右旋转 Left Right Rotation 以及带子树的右旋 Right Rotation with children AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法 但是要进行预先或随后做一次或多次所谓的 AVL旋转 以下图表以四列表示四种情况 每行表示在该种情况下要进行的操作 在左左和右右的情况下 只需要进行一次旋转操作 在左右和右左的情况下 需要进行两次旋转操作 删除 编辑 从AVL树中删除 可以通过把要删除的节点向下旋转成一个葉子節點 接着直接移除这个叶子节点来完成 因为在旋转成葉子節點期间最多有log n个节点被旋转 而每次AVL旋转耗费固定的时间 所以删除处理在整体上耗费O log n 时间 搜尋 编辑 可以像普通二叉查找树一样的进行 所以耗费O log n 时间 因为AVL树总是保持平衡的 不需要特殊的准备 树的结构不会由于查找而改变 这是与伸展樹搜尋相对立的 它会因为搜尋而变更树结构 实现描述 编辑假設平衡因子是左子樹的高度減去右子樹的高度所得到的值 又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a 即a是离插入点最近 且平衡因子绝对值超过1的祖先节点 则失去平衡后进行的规律可归纳为下列四种情况 单向右旋平衡处理LL 由于在 a的左子树根节点的左子树上插入节点 a的平衡因子由1增至2 致使以 a为根的子树失去平衡 则需进行一次右旋转操作 单向左旋平衡处理RR 由于在 a的右子树根节点的右子树上插入节点 a的平衡因子由 1变为 2 致使以 a为根的子树失去平衡 则需进行一次左旋转操作 双向旋转 先左后右 平衡处理LR 由于在 a的左子树根节点的右子树上插入节点 a的平衡因子由1增至2 致使以 a为根的子树失去平衡 则需进行两次旋转 先左旋后右旋 操作 双向旋转 先右后左 平衡处理RL 由于在 a的右子树根节点的左子树上插入节点 a的平衡因子由 1变为 2 致使以 a为根的子树失去平衡 则需进行两次旋转 先右旋后左旋 操作 在平衡的二叉排序树BBST Balancing Binary Search Tree 上插入一个新的数据元素e的递归算法可描述如下 若BBST为空树 则插入一个数据元素为e的新节点作为BBST的根节点 树的深度增1 若e的关键字和BBST的根节点的关键字相等 则不进行 若e的关键字小于BBST的根节点的关键字 而且在BBST的左子树中不存在和e有相同关键字的节点 则将e插入在BBST的左子树上 并且当插入之后的左子树深度增加 1 时 分别就下列不同情况处理之 BBST的根节点的平衡因子为 1 右子树的深度大于左子树的深度 则将根节点的平衡因子更改为0 BBST的深度不变 BBST的根节点的平衡因子为0 左 右子树的深度相等 则将根节点的平衡因子更改为1 BBST的深度增1 BBST的根节点的平衡因子为1 左子树的深度大于右子树的深度 则若BBST的左子树根节点的平衡因子为1 则需进行单向右旋平衡处理 并且在右旋处理之后 将根节点和其右子树根节点的平衡因子更改为0 树的深度不变 若e的关键字大于BBST的根节点的关键字 而且在BBST的右子树中不存在和e有相同关键字的节点 则将e插入在BBST的右子树上 并且当插入之后的右子树深度增加 1 时 分别就不同情况处理之 AVL树的调平 Erlang的实现 balance null gt null balance null null Tree gt Tree balance Left Value Right Tree gt Diff count Left count Right if Diff lt 2 and Diff gt 2 gt balance Left Value balance Right Diff gt 1 gt balance rotate right Tree Diff lt 1 gt balance rotate left Tree true gt exit This is impossible end rotate right Left Value Right gt merge max Left null Value Right rotate left Left Value Right gt merge min Right Left Value null merge min null Value Right Tree2 gt Tree2 Value Right merge min Left Tree2 gt merge min Left Tree2 merge max Left Value null Tree2 gt Left Value Tree2 merge max Right Tree2 gt merge max Right Tree2 AVL節點數計算 编辑高度為h的AVL樹 總節點數N最多2 h 1 1 displaystyle 2 h 1 1 最少節點數N h displaystyle N h 如以斐波那契數列可以用數學歸納法證明 N h displaystyle N h F h 2 displaystyle F h 2 1 F h 2 displaystyle F h 2 是斐波那契数列的第h 2项 根据斐波那契多项式得来 即 N 0 displaystyle N 0 0 表示AVL Tree高度為0的節點總數 N 1 displaystyle N 1 1 表示AVL Tree高度為1的節點總數 N 2 displaystyle N 2 2 表示AVL Tree高度為2的節點總數 N h displaystyle N h N h 1 displaystyle N h 1 N h 2 displaystyle N h 2 1 表示AVL Tree高度為h的節點總數 換句話說 當節點數為N時 高度h最多為l o g F 5 N 1 2 displaystyle log Phi sqrt 5 N 1 2 参见 编辑樹旋轉 伸展樹 紅黑樹 B樹引用 编辑G Adelson Velskii and E M Landis An algorithm for the organization of information Doklady Akademii Nauk SSSR 146 263 266 1962 Russian English translation by Myron J Ricci in Soviet Math Doklady 3 1259 1263 1962 外部链接 编辑Description from the Dictionary of Algorithms and Data Structures 页面存档备份 存于互联网档案馆 AVL Tree Traversal 页面存档备份 存于互联网档案馆 Linked AVL tree C AVL Tree Template and C AVL TREE Generic Package by Walt Karas A Visual Basic AVL Tree Container Class 页面存档备份 存于互联网档案馆 by Jim Harris AVL Trees Tutorial and C Implementation 页面存档备份 存于互联网档案馆 by Brad Appleton Ulm s Oberon Library AVLTrees 页面存档备份 存于互联网档案馆 The AVL TREE Data Type CNAVLTree Class Reference 永久失效連結 GNU libavl 页面存档备份 存于互联网档案馆 AVL trees balanced binary trees by Alex Konshin Simulation of AVL Trees AVL tree applet 页面存档备份 存于互联网档案馆 Simulation of AVL Trees DYNAMIC AVL Splay and Red Black Applet 取自 https zh wikipedia org w index php title AVL树 amp oldid 71757969, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。