📄 alta_avl.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0052)http://mailweb.udlap.mx/~ingrid/Clases/Alta_AVL.html -->
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2800.1170" name=GENERATOR></HEAD>
<BODY><B>Alta en un 醨bol AVL</B>
<HR>
Pseudocode 4.8: AVL tree insertion. This algorithm inserts a key <B>K</B> into
an AVL-tree T with a root called <B>T_root</B>. Each node in the AVL tree has a
field for the <B>key</B>, another for the <B>balance</B> information and
pointers to the <B>left</B> and the <B>right child</B>. The recursive function
<B>insert(K, p, parent) </B>uses a counter <B>'increment'</B> for the
calculation of the balance and a flag <B>'insert'</B> to signalize a successful
insertion.The calls to <B>rotate-left(p) </B>and <B>rotate-right(p) </B>are
different than those for the red-black trees, as an example the algorithm for
rotate-left(p) is presented below. In some cases a<B> double rotation</B> is
necessary, this is expressed as two calls to a single rotation. For example, to
do a double rotation to the left of node p, first a right-rotation of node p's
right child is performed, followed by a left-rotation of node p itself, as can
be seen in step H2.27. <BR><PRE>Step H1.1 : [Initialize] Set p <- T_root.
Step H1.2 : [Call function] insert(K, p, p.parent).
<BR>
<BR>
<B>Algorithm for the recursive function insert(K, p, parent): </B>
<BR>
Step H2.1 : [Initialize] Set insert <- 0, increment <- 0.
Step H2.2 : [Empty tree] If p = nil then
Step H2.3 : [New node] set p <- new-node,
Step H2.4 : [Link new node] If parent <> nil
Step H2.5 : [Which child?] If K > parent.key
Step H2.6 : parent.right-child = p,
Step H2.7 : otherwise
Step H2.8 : parent.left-child = p.
Step H2.9 : [Balance] Set p.balance <- 0,
Step H2.10 : [Insert key] set p<- K,
Step H2.11 : [Set flag] set insert <- 1.
Step H2.12 : Otherwise (of H2.2)
Step H2.13 : [Found key] If p.key = K then
Step H2.14 : [Quit insertion] algorithm terminates (key already exists).
Step H2.15 : Otherwise
Step H2.16 : [Key is larger] If K > p.key then
Step H2.17 : [Try right subtree] increment <- insert(K, p.right-child, p),
Step H2.18 : [Key is smaller] otherwise
Step H2.19 : [Try left subtree] increment<- - (insert(K, p.left-child, p)).
Step H2.20 : [Update balance] Set p.balance <- p.balance + increment.
Step H2.21 : [Unbalanced?] If increment <> 0 AND p.balance <> 0 then
Step H2.22 : [Left subtree too tall] If p.balance < -1 then
Step H2.23 : [Auxilary pointer] set r <- p.left-child.
Step H2.24 : [Right rotation] If r.balance < 0 then
Step H2.25 : rotate-right(p)
Step H2.26 : [Double right rotation] otherwise
Step H2.27 : rotate-left(r),
Step H2.28 : rotate-right(p).
Step H2.29 : Otherwise
Step H2.30 : [Right subtree too tall] If p.balance > 1 then
Step H2.31 : [Auxilary pointer] set r <- p.right-child.
Step H2.32 : [Left rotation] If r.balance > 0 then
Step H2.33 : rotate-left(p).
Step H2.34 : [Double left rotation] otherwise
Step H2.35 : rotate-right(r),
Step H2.36 : rotate-left(p).
Step H2.37 : [Update flag] Otherwise
Step H2.38 : set insert <- 1.
Step H2.39 : [Return flag] Return (insert).
Step H2.40 : [END] END
<BR>
<BR>
<BR>
<B>Algorithm for the function rotate-left(p): </B>
(u is an auxilary pointer and w is a integer variable; max() returns the larger of its parameters and min() the smallest of them)
Step H3.1 : [Initialize] Set u <- p.
Step H3.2 : [Right child] Set t <-p.right-child.
Step H3.3 : [Re-link] Set u.right-child <-t.left-child.
Step H3.4 : [New left child] Set t.left-child <-u.
Step H3.5 : Set w <- u.balance.
Step H3.6 : [Adjust balance] Set u.balance <- w - 1 - max(t.balance, 0).
Step H3.7 : Set t.balance <- min(w-2, w+t.balance-2, t.balance-1).
Step H3.8 : [End] END
<BR>
</PRE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -