符合直觉的完美平衡树？AVL树(自平衡二叉查找树)的Lua实现与测试场景实例

AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log {n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

一、AVL树是什么？如何维持自身平衡性？

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。
AVL树在插入节点的过程中如何保证树的平衡性（并不是每次调整所有的节点），在插入时检查树的叶子节点，找到第一个失去平衡的节点(最小失衡子树), 调整该节点(子树)，整棵树就达到平衡了。

二、AVL树中的节点旋转概念：

AVL树维持平衡的四种Case：LL, RR, LR, RL （子节点-父节点-祖父节点） 三个节点的关系可以通过自己绘图来整理
LL (Left Node of Left Child 左孩子的左节点) 右旋
RR (Right Node of Right Child 右孩子的右节点) 左旋
LR (Left Node of Right Child 右孩子的左节点) 先左旋再右旋
RL (Right Node of Left Child 左孩子的右节点) 先右旋再左旋

三、代码实现部分：

1.Node节点类

代码如下（示例）：

-- Node class
local Node = {}
Node.__index = Nodefunction Node.new(key, value)-- create a new node with key and valuelocal self = setmetatable({}, Node)self.key = keyself.value = valueself.left = nilself.right = nilself.height = 1return self
endfunction Node:get_balance()-- get the balance factor of the nodelocal left_height = self.left and self.left.height or 0local right_height = self.right and self.right.height or 0return left_height - right_height
endfunction Node:update_height()-- update the height of the nodelocal left_height = self.left and self.left.height or 0local right_height = self.right and self.right.height or 0self.height = 1 + math.max(left_height, right_height)
endfunction Node:rotate_right()-- rotate the node to the rightlocal y = self.leftself.left = y.righty.right = selfself:update_height()y:update_height()return y
endfunction Node:rotate_left()-- rotate the node to the leftlocal y = self.rightself.right = y.lefty.left = selfself:update_height()y:update_height()return y
endfunction Node:rebalance()-- rebalance the node if necessaryself:update_height()local balance = self:get_balance()if balance > 1 thenif self.left:get_balance() < 0 thenself.left = self.left:rotate_left()endreturn self:rotate_right()elseif balance < -1 thenif self.right:get_balance() > 0 thenself.right = self.right:rotate_right()endreturn self:rotate_left()elsereturn selfend
end

2.AVLTree类

代码如下（示例）：

-- AVLTree class
local AVLTree = {}
AVLTree.__index = AVLTreefunction AVLTree:new()-- create a new AVL treelocal self = setmetatable({}, AVLTree)self.root = nilreturn self
endfunction AVLTree:insert(key, value)-- insert a key-value pair into the treeself.root = self:_insert(self.root, key, value)
endfunction AVLTree:_insert(node, key, value)-- recursive insert functionif not node thenreturn Node.new(key, value)elseif key < node.key thennode.left = self:_insert(node.left, key, value)elseif key > node.key thennode.right = self:_insert(node.right, key, value)elsenode.value = valueendreturn node:rebalance()
endfunction AVLTree:remove(key)-- remove a key from the treeself.root = self:_remove(self.root, key)
endfunction AVLTree:_remove(node, key)-- recursive remove functionif not node thenreturn nilelseif key < node.key thennode.left = self:_remove(node.left, key)elseif key > node.key thennode.right = self:_remove(node.right, key)elseif not node.left and not node.right thenreturn nilelseif not node.left thenreturn node.rightelseif not node.right thenreturn node.leftelselocal successor = self:_find_min(node.right)node.key = successor.keynode.value = successor.valuenode.right = self:_remove(node.right, successor.key)endendreturn node:rebalance()
endfunction AVLTree:find(key)-- find the value for a given key in the treelocal node = self:_find(self.root, key)return node and node.value or nil
endfunction AVLTree:_find(node, key)-- recursive find functionif not node thenreturn nilelseif key < node.key thenreturn self:_find(node.left, key)elseif key > node.key thenreturn self:_find(node.right, key)elsereturn nodeend
endfunction AVLTree:_find_min(node)-- find the minimum key in the treewhile node.left donode = node.leftendreturn node
endfunction AVLTree:traverse(visit)-- traverse the tree in-order and apply the visit function to each nodeself:_traverse(self.root, visit)
endfunction AVLTree:_traverse(node, visit)-- recursive in-order traversalif node thenself:_traverse(node.left, visit)visit(node.key, node.value)self:_traverse(node.right, visit)end
endreturn AVLTree

测试场景实例

按照惯例测试场景实例代码不放出，我是在Unity环境中建立的Canvas上绘制的节点图。期间遇到了一些小麻烦，本应该是一颗"完美的平衡二叉树"，绘制起来却显得有些丑陋，尤其是树的高度越大，整棵树底部越显得"臃肿"…， 在Canvas中的排版下看起来并不体面。

不过整棵树建立的结构还是很正确的，下图所示：