File: AVL_TREE_NODE.html

package info (click to toggle)
lisaac 1%3A0.13.1-2
  • links: PTS
  • area: main
  • in suites: lenny
  • size: 15,232 kB
  • ctags: 6,386
  • sloc: ansic: 242,479; xml: 635; lisp: 333; makefile: 119; sh: 73; asm: 38
file content (99 lines) | stat: -rwxr-xr-x 6,915 bytes parent folder | download | duplicates (2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
<!DOCTYPE HTML SYSTEM>
<!-- Generated by Lisaac shorter / html style -->
<html>
<head>
<title>
Lisaac prototype interface
</title>
</head>
<body BGCOLOR="#FFFFFF">

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Header</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">name</font></strong> := <a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>];
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">comment</font></strong> := <font color="#BC8F8F">"Auxiliary class to implement AVL_SET."</font>;
	
  <br><font FACE="Sans-serif" color="#000000"><B> This a classic implementation of an AVL tree (balanced tree first designed </B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> by Adelson-Velskii and Landis (hence A.V.L.), 1960)</B></font>

<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Insert</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">parent_avl_constants</font></strong>:<a href="AVL_CONSTANTS.html"><font color="#008000">AVL_CONSTANTS</font></a> := 

<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">out_in_tagged_out_memory</font></strong> <-
  
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong> 
  <br><font FACE="Sans-serif" color="#000000"><B>AVL_TREE_NODE, AVL_TREE</B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">left</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>];

  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">right</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>];

  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">item</font></strong>:<font color="#008000">E</font>;

  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">balance</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a>;
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Balance factor; either `balanced' (the tree is balanced),</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  `imbalanced_left' (the left branch is the longer) or</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  `imbalanced_right' (the right branch is the longer)</font></strong></em>

  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">count</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">height</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">map_in</font></strong> map:<a href="COLLECTION.html"><font color="#008000">COLLECTION</font></a>[<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>]] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">has</font></strong> e:<font color="#008000">E</font> :<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Is element `e' in the tree?</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_has</font></strong> e:<font color="#008000">E</font> :<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Is element `e' in the tree?</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">at</font></strong> e:<font color="#008000">E</font> :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Is element `e' in the tree?</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">set_item</font></strong> i:<font color="#008000">E</font> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">set_left</font></strong> l:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">set_right</font></strong> r:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">set_balance</font></strong> b:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> <-
  
<br><br><strong><font color="#A020F0">Section</font></strong> <a href="AVL_TREE.html"><font color="#008000">AVL_TREE</font></a>, <a href="AVL_DICTIONARY.html"><font color="#008000">AVL_DICTIONARY</font></a>, <a href="AVL_SET.html"><font color="#008000">AVL_SET</font></a>
  
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Rotations:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">rotate_right</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Proceeds to some reorganisation and returns the upper node.</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">rotate_left</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Proceeds to some reorganisation and returns the upper node.</font></strong></em>
    
</body>
</html>