AATree

AATree是一个小作品，欢迎帮助扩充这个条目。

AATree是一种平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1993年由Arne Andersson发明的。它不仅实现简单，而且它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除操作，这里的n 是树中元素的数目。它可以被看作是红黑树和BB-tree的一种特例。

性质

Make sure that only right edges are horizontal before you check the size of the pseudo-node.

操作

插入Insert

Insertion begins with the normal binary tree search and insertion procedure. Then, as the call stack unwinds (assuming a recursive implementation of the search), it's easy to check the validity of the tree and perform any rotations as necessary. If a horizontal left link arises, a skew will be performed, and if two horizontal right links arise, a split will be performed, possibly incrementing the level of the new root node of the current subtree. Note, in the code as given above, the increment of level(T). This makes it necessary to continue checking the validity of the tree as the modifications bubble up from the leaves.

function insert is

   input: X, the value to be inserted, and T, the root of the tree to insert it into.
   output: A balanced version T including X.

   Do the normal binary tree insertion procedure. Set the result of the
   recursive call to the correct child in case a new node was created or the
   root of the subtree changes.
   if nil(T) then
       Create a new leaf node with X.
       return node(X, 1, Nil, Nil)
   else if X < value(T) then
       left(T) := insert(X, left(T))
   else if X > value(T) then
       right(T) := insert(X, right(T))
   end if
   Note that the case of X == value(T) is unspecified. As given, an insert
   will have no effect. The implementor may desire different behavior.

   Perform skew and then split. The conditionals that determine whether or
   not a rotation will occur or not are inside of the procedures, as given
   above.
   T := skew(T)
   T := split(T)

   return T

end function

删除Delete

As in most balanced binary trees, the deletion of an internal node can be turned into the deletion of a leaf node by swapping the internal node with either its closest predecessor or successor, depending on which are in the tree or on the implementor's whims. Retrieving a predecessor is simply a matter of following one left link and then all of the remaining right links. Similarly, the successor can be found by going right once and left until a null pointer is found. Because of the AA property of all nodes of level greater than one having two children, the successor or predecessor node will be in level 1, making their removal trivial. To re-balance a tree, there are a few approaches. The one described by Andersson in his original paper is the simplest, and it is described here, although actual implementations may opt for a more optimized approach. After a removal, the first step to maintaining tree validity is to lower the level of any nodes whose children are two levels below them, or who are missing children. Then, the entire level must be skewed and split. This approach was favored, because when laid down conceptually, it has three easily understood separate steps: Decrease the level, if appropriate. Skew the level. Split the level. However, we have to skew and split the entire level this time instead of just a node, complicating our code.

function delete is

   input: X, the value to delete, and T, the root of the tree from which it should be deleted.
   output: T, balanced, without the value X.
  
   if nil(T) then
       return T
   else if X > value(T) then
       right(T) := delete(X, right(T))
   else if X < value(T) then
       left(T) := delete(X, left(T))
   else
       If we're a leaf, easy, otherwise reduce to leaf case. 
       if leaf(T) then
           return Nil
       else if nil(left(T)) then
           L := successor(T)
           right(T) := delete(value(L), right(T))
           value(T) := value(L)
       else
           L := predecessor(T)
           left(T) := delete(value(L), left(T))
           value(T) := value(L)
       end if
   end if

   Rebalance the tree. Decrease the level of all nodes in this level if
   necessary, and then skew and split all nodes in the new level.
   T := decrease_level(T)
   T := skew(T)
   right(T) := skew(right(T))
   right(right(T)) := skew(right(right(T)))
   T := split(T)
   right(T) := split(right(T))
   return T

end function

function decrease_level is

   input: T, a tree for which we want to remove links that skip levels.
   output: T with its level decreased.

   should_be = min(level(left(T)), level(right(T))) + 1
   if should_be < level(T) then
       level(T) := should_be
       if should_be < level(right(T)) then
           level(right(T)) := should_be
       end if
   end if
   return T

end function A good example of deletion by this algorithm is present in the Andersson paper.

参考程序

• code in C
• code in Pascal

参见

• B-tree
• BB-tree
• 红黑树

外部链接

• Balanced Search Trees Made Simple, Arne Andersson