Sign in Join
Wiki copytemporary

AVL Tree: what changed

Revision 2 to 3. Removed lines have a minus sign; added lines have a plus sign.

OldNewLine
1-## Contents
2-
3- * 1 TAVLTree
4- * 2 TAvgLvlTree
5- * 2.1 Creating a tree
6- * 2.2 Enumerating all items of a tree
7- * 2.2.1 Enumerate from lowest to highest
8- * 2.2.2 Enumerate from highest to lowest
9- * 2.2.3 Delete all nodes that fits a condition
10- * 2.3 Searching items
11- * 2.4 Resorting, changing the order
12- * 3 Associative arrays using AVL trees
13- * 4 Indexed AVL Tree
14- * 5 See also
15-
161# TAVLTree
172
18-Implemented in the FCL unit **avl_tree**. This is the predecessor of TAvgLvlTree.
3+Implemented in the FCL unit **avl_tree**. This is the predecessor of TAvgLvlTree.
194
205# TAvgLvlTree
216
22-Where to get: Unit AvgLvlTree of Lazarus package **LazUtils** of the Lazarus sources.
7+Where to get: Unit AvgLvlTree of Lazarus package **LazUtils** of the Lazarus sources.
238
24-The AVL trees - Average Level Trees are sorted self balancing binary trees. Similar to a list like TPFList a TAvgLvlTree can store arbitrary data (Pointer), but contrary to TFPList the tree is always sorted and balanced. Therefore searching is very fast. Features:
9+The AVL trees - Average Level Trees are sorted self balancing binary trees. Similar to a list like TPFList a TAvgLvlTree can store arbitrary data (Pointer), but contrary to TFPList the tree is always sorted and balanced. Therefore searching is very fast. Features:
2510
26- * You can define your own compare function or method.
27- * Searching an item or key takes O(log(n))
28- * Inserting an item takes O(log(n))
29- * Deleting an item takes O(log(n))
30- * Finding the lowest or highest item takes log(n)
31- * Finding the sucessor or predecessor item takes O(log(n))
32- * Iterating through all items in order takes O(n)
33- * Enumerators for running from lowest to highest and highest to lowest
34- * Supports duplicates
35- * Keeps duplicates order stable.
36- * It is not thread safe, but it does not use any global variables. So it can be used in threads just like TFPList.
11+- You can define your own compare function or method.
12+- Searching an item or key takes O(log(n))
13+- Inserting an item takes O(log(n))
14+- Deleting an item takes O(log(n))
15+- Finding the lowest or highest item takes log(n)
16+- Finding the sucessor or predecessor item takes O(log(n))
17+- Iterating through all items in order takes O(n)
18+- Enumerators for running from lowest to highest and highest to lowest
19+- Supports duplicates
20+- Keeps duplicates order stable.
21+- It is not thread safe, but it does not use any global variables. So it can be used in threads just like TFPList.
3722
3823## Creating a tree
3924
40-By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects:
41-```
25+By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects:
26+
27+``` pascal
4228uses AvgLvlTree; // in package lazutils
43-
44- Tree:=TAvgLvlTree.Create;
45- Tree.Add(AnObject1);
46- Tree.Add(AnObject2);
47- ...
48- // If you want to know if an item is already in the tree use Find:
49- if Tree.Find(AnObject1)<>nil then
50- writeln('AnObject is in the tree');
51- ...
52- // To remove an item from the tree use:
53- Tree.Remove(AnObject1);
54-```
5529
56-To create a tree for your custom data you only need a compare function. The following example demonstrates how to sort TMyData objects via their Filenames:
30+Tree:=TAvgLvlTree.Create;
31+Tree.Add(AnObject1);
32+Tree.Add(AnObject2);
33+...
34+// If you want to know if an item is already in the tree use Find:
35+if Tree.Find(AnObject1)<>nil then
36+ writeln('AnObject is in the tree');
37+...
38+// To remove an item from the tree use:
39+Tree.Remove(AnObject1);
5740```
41+
42+To create a tree for your custom data you only need a compare function. The following example demonstrates how to sort TMyData objects via their Filenames:
43+
44+``` pascal
5845uses AvgLvlTree; // in package lazutils
59- type
60- TMyData = class
61- public
62- Filename: string;
63- Content: string;
64- end;
65-
66- function CompareMyData(Data1, Data2: Pointer): integer;
67- begin
68- Result:=CompareFilenames(TMyData(d1).Filename,TMyData(d2).Filename);
69- end;
70-
71- ...
72- var
73- MyData1: TMyData;
74- Tree: TAvgLvlTree;
75- begin
76- Tree:=TAvgLvlTree.Create(@CompareMyData);
77-
78- MyData1:=TMyData.Create;
79- MyData1.Filename:='SomeFile';
80- Tree.Add(MyData1);
81- end;
46+type
47+ TMyData = class
48+ public
49+ Filename: string;
50+ Content: string;
51+ end;
52+
53+function CompareMyData(Data1, Data2: Pointer): integer;
54+begin
55+ Result:=CompareFilenames(TMyData(d1).Filename,TMyData(d2).Filename);
56+end;
57+
58+...
59+var
60+ MyData1: TMyData;
61+ Tree: TAvgLvlTree;
62+begin
63+ Tree:=TAvgLvlTree.Create(@CompareMyData);
64+
65+ MyData1:=TMyData.Create;
66+ MyData1.Filename:='SomeFile';
67+ Tree.Add(MyData1);
68+end;
8269```
8370
8471## Enumerating all items of a tree
8572
8673### Enumerate from lowest to highest
87-```
74+
75+``` pascal
8876var
89- MyData: TMyData;
90- begin
91- for Node in Tree do begin
92- MyData:=TMyData(Node.Data);
93- writeln(MyData.Filename);
94- end;
95- end;
77+ MyData: TMyData;
78+begin
79+ for Node in Tree do begin
80+ MyData:=TMyData(Node.Data);
81+ writeln(MyData.Filename);
82+ end;
83+end;
9684```
9785
98-Notes:
86+Notes:
9987
100- * You can insert new nodes while enumerating with this enumerator.
101- * You must not delete the Node, nor change the Node.Data using this enumerator.
88+- You can insert new nodes while enumerating with this enumerator.
89+- You must not delete the Node, nor change the Node.Data using this enumerator.
10290
10391### Enumerate from highest to lowest
104-```
92+
93+``` pascal
10594var
106- MyData: TMyData;
107- begin
108- for Node in Tree.GetEnumeratorHighToLow do begin
109- MyData:=TMyData(Node.Data);
110- writeln(MyData.Filename);
111- end;
112- end;
95+ MyData: TMyData;
96+begin
97+ for Node in Tree.GetEnumeratorHighToLow do begin
98+ MyData:=TMyData(Node.Data);
99+ writeln(MyData.Filename);
100+ end;
101+end;
113102```
114103
115104### Delete all nodes that fits a condition
116105
117-If you need full control over the enumeration you can use Node.**Sucessor** and Node.**Precessor**. Here is an example how to delete all nodes that fits a filter:
118-```
106+If you need full control over the enumeration you can use Node.**Sucessor** and Node.**Precessor**. Here is an example how to delete all nodes that fits a filter:
107+
108+``` pascal
119109var
120- Node: TAvgLvlTreeNode;
121- begin
122- Node:=Tree.FindLowest;
123- while Node<>nil do begin
124- NextNode:=Node.Successor;
125- if TMyData(Node.Data).Flag=true then
126- Tree.Delete(Node); // Note: this frees the Node, not the Node.Data. Use Tree.FreeAndDelete(Node) to free the Data.
127- Node:=NextNode;
128- end;
129- end;
110+ Node: TAvgLvlTreeNode;
111+begin
112+ Node:=Tree.FindLowest;
113+ while Node<>nil do begin
114+ NextNode:=Node.Successor;
115+ if TMyData(Node.Data).Flag=true then
116+ Tree.Delete(Node); // Note: this frees the Node, not the Node.Data. Use Tree.FreeAndDelete(Node) to free the Data.
117+ Node:=NextNode;
118+ end;
119+end;
130120```
131121
132-Note:
122+Note:
133123
134- * TMyData.Flag is just an example property. You can check whatever you want.
124+- TMyData.Flag is just an example property. You can check whatever you want.
135125
136126## Searching items
137127
138-You can search an item with the same key:
139-```
128+You can search an item with the same key:
129+
130+``` pascal
140131var
141- Node: TAvgLvlTreeNode;
142- begin
143- MyData.Filename:='test';
144- Node:=Tree.Find(MyData); // finds a node with a Filename = 'test'
145- // Note: The above function CompareFilenames works case insensitive under Windows
146- // so under Windows it can find a node with Filename 'TEST'
147- end;
132+ Node: TAvgLvlTreeNode;
133+begin
134+ MyData.Filename:='test';
135+ Node:=Tree.Find(MyData); // finds a node with a Filename = 'test'
136+ // Note: The above function CompareFilenames works case insensitive under Windows
137+ // so under Windows it can find a node with Filename 'TEST'
138+end;
148139```
149140
150-**Note:** **Find** will find a node where your compare function returns 0.
141+**Note:** **Find** will find a node where your compare function returns 0.
151142
152-You can also search directly with a filename, without creating a TMyData. The function FindKey takes as arguments a key (here: the filename) and a special compare function:
153-```
143+You can also search directly with a filename, without creating a TMyData. The function FindKey takes as arguments a key (here: the filename) and a special compare function:
144+
145+``` pascal
154146function CompareFilenameWithMyData(Filename, MyData: Pointer): integer;
155- begin
156- Result:=CompareFilenames(String(Filename),TMyData(MyData).Filename);
157- end;
158-
159- ...
160- var
161- Filename: string;
162- Node: TAvgLvlTreeNode;
163- begin
164- Filename:='Test';
165- Node:=Tree.FindKey(Pointer(Filename),@CompareFilenameWithMyData);
166-
167- end;
147+begin
148+ Result:=CompareFilenames(String(Filename),TMyData(MyData).Filename);
149+end;
150+
151+...
152+var
153+ Filename: string;
154+ Node: TAvgLvlTreeNode;
155+begin
156+ Filename:='Test';
157+ Node:=Tree.FindKey(Pointer(Filename),@CompareFilenameWithMyData);
158+
159+end;
168160```
169161
170162## Resorting, changing the order
171163
172-You can change the compare function. The tree will automatically rebuild itself. The Nodes will be destroyed and all Data will be added into new nodes. For example you can switch from comparing case sensitive to case insensitive:
173-```
164+You can change the compare function. The tree will automatically rebuild itself. The Nodes will be destroyed and all Data will be added into new nodes. For example you can switch from comparing case sensitive to case insensitive:
165+
166+``` pascal
174167type
175- TMyData = class
176- public
177- Name: string;
178- constructor Create(aName: string);
179- end;
180-
181- constructor TMyData.Create(aName: string);
182- begin
183- Name:=aName;
184- end;
185-
186- function CompareMyDataCaseSensitive(Data1, Data2: Pointer): integer;
187- begin
188- Result:=CompareStr(TMyData(Data1).Name,TMyData(Data2).Name);
189- end;
190-
191- function CompareMyDataCaseInsensitive(Data1, Data2: Pointer): integer;
192- begin
193- Result:=AnsiCompareText(TMyData(Data1).Name,TMyData(Data2).Name);
194- end;
195-
196- procedure Demo;
197- var
198- Tree: TAvgLvlTree;
199- Node: TAvgLvlTreeNode;
200- begin
201- Tree:=TAvgLvlTree.Create(@CompareMyDataCaseSensitive);
202- Tree.Add(TMyData.Create('ABC'));
203- Tree.Add(TMyData.Create('Test'));
204- Tree.Add(TMyData.Create('abc'));
205- Tree.Add(TMyData.Create('test'));
206- writeln('sorted case sensitive:');
207- for Node in Tree do
208- writeln(' ',TMyData(Node.Data).Name);
209- // sort case insensitivie
210- Tree.OnCompare:=@CompareMyDataCaseInsensitive;
211- writeln('sorted case insensitive:');
212- for Node in Tree do
213- writeln(' ',TMyData(Node.Data).Name);
214- end;
215-```
168+ TMyData = class
169+ public
170+ Name: string;
171+ constructor Create(aName: string);
172+ end;
216173
217-Output:
174+constructor TMyData.Create(aName: string);
175+begin
176+ Name:=aName;
177+end;
178+
179+function CompareMyDataCaseSensitive(Data1, Data2: Pointer): integer;
180+begin
181+ Result:=CompareStr(TMyData(Data1).Name,TMyData(Data2).Name);
182+end;
183+
184+function CompareMyDataCaseInsensitive(Data1, Data2: Pointer): integer;
185+begin
186+ Result:=AnsiCompareText(TMyData(Data1).Name,TMyData(Data2).Name);
187+end;
188+
189+procedure Demo;
190+var
191+ Tree: TAvgLvlTree;
192+ Node: TAvgLvlTreeNode;
193+begin
194+ Tree:=TAvgLvlTree.Create(@CompareMyDataCaseSensitive);
195+ Tree.Add(TMyData.Create('ABC'));
196+ Tree.Add(TMyData.Create('Test'));
197+ Tree.Add(TMyData.Create('abc'));
198+ Tree.Add(TMyData.Create('test'));
199+ writeln('sorted case sensitive:');
200+ for Node in Tree do
201+ writeln(' ',TMyData(Node.Data).Name);
202+ // sort case insensitivie
203+ Tree.OnCompare:=@CompareMyDataCaseInsensitive;
204+ writeln('sorted case insensitive:');
205+ for Node in Tree do
206+ writeln(' ',TMyData(Node.Data).Name);
207+end;
218208```
219-sorted case sensitive:
209+
210+Output:
211+
212+ sorted case sensitive:
220213 ABC
221214 Test
222215 abc
223216 test
224217 sorted case insensitive:
225218 ABC
226219 abc
227220 Test
228221 test
229-```
230222
231223# Associative arrays using AVL trees
232224
233-An associative array is an array where instead of a the position an arbitrary key is used to find an item. For example a string. The unit AvgLvlTree implements several associative arrays using AVL trees:
225+An associative array is an array where instead of a the position an arbitrary key is used to find an item. For example a string. The unit AvgLvlTree implements several associative arrays using AVL trees:
234226
235- * TStringToStringTree: string to string, you can choose case sensitive or case insensitive or provide your own string comparison function
236- * TStringToPointerTree: As TStringToStringTree but to arbitrary pointers, which might be objects
227+- TStringToStringTree: string to string, you can choose case sensitive or case insensitive or provide your own string comparison function
228+- TStringToPointerTree: As TStringToStringTree but to arbitrary pointers, which might be objects
237229
238-Here is an example demonstrating how to use a TStringToStringTree:
239-```
230+Here is an example demonstrating how to use a TStringToStringTree:
231+
232+``` pascal
240233uses
241- AvgLvlTree;
242- var
243- NameToValue: TStringToStringTree;
244- S2SItem: PStringToStringItem;
245- begin
246- // create
247- NameToValue:=TStringToStringTree.Create(false); // false = Names are compared case insensitive via ''AnsiCompareText''
248-
249- // set values
250- NameToValue['First'] := 'One';
251- NameToValue['Second'] := 'Two';
252-
253- // get values
254- writeln('First=',NameToValue['first']); // writes One
255- writeln('Second=',NameToValue['second']); // writes Two
256- writeln('Third=',NameToValue['third']); // third is not yet set, it writes the empty string
257-
258- // check if a key is defined
259- writeln('First exists: ',NameToValue.Contains('first')); // gives true
260- writeln('Third exists: ',NameToValue.Contains('third')); // gives false
261-
262- // enumerate all values
263- for S2SItem in NameToValue do
264- writeln('Name=',S2SItem^.Name,' Value=',S2SItem^.Value);
265-
266- // free
267- NameToValue.Free;
268- end;
234+ AvgLvlTree;
235+var
236+ NameToValue: TStringToStringTree;
237+ S2SItem: PStringToStringItem;
238+begin
239+ // create
240+ NameToValue:=TStringToStringTree.Create(false); // false = Names are compared case insensitive via ''AnsiCompareText''
241+
242+ // set values
243+ NameToValue['First'] := 'One';
244+ NameToValue['Second'] := 'Two';
245+
246+ // get values
247+ writeln('First=',NameToValue['first']); // writes One
248+ writeln('Second=',NameToValue['second']); // writes Two
249+ writeln('Third=',NameToValue['third']); // third is not yet set, it writes the empty string
250+
251+ // check if a key is defined
252+ writeln('First exists: ',NameToValue.Contains('first')); // gives true
253+ writeln('Third exists: ',NameToValue.Contains('third')); // gives false
254+
255+ // enumerate all values
256+ for S2SItem in NameToValue do
257+ writeln('Name=',S2SItem^.Name,' Value=',S2SItem^.Value);
258+
259+ // free
260+ NameToValue.Free;
261+end;
269262```
270263
271264# Indexed AVL Tree
272265
273-TIndexedAVLTree extends TAvgLvlTree with the ability to access the nodes via their index (0=lowest, Count-1=highest) similar to an array. In other words it is like an array that is always sorted.
274-```
266+TIndexedAVLTree extends TAvgLvlTree with the ability to access the nodes via their index (0=lowest, Count-1=highest) similar to an array. In other words it is like an array that is always sorted.
267+
268+``` pascal
275269uses
276- AvgLvlTree;
277- type
278- TMyData = class
279- public
280- Name: string;
281- constructor Create(aName: string);
282- end;
283-
284- constructor TMyData.Create(aName: string);
285- begin
286- Name:=aName;
287- end;
288-
289- function CompareMyDataCaseInsensitive(Data1, Data2: Pointer): integer;
290- begin
291- Result:=AnsiCompareText(TMyData(Data1).Name,TMyData(Data2).Name);
292- end;
293-
294- var
295- SortedArray: TIndexedAVLTree;
296- Node: TIndexedAVLTreeNode;
297- begin
298- // create
299- SortedArray:=TIndexedAVLTree.Create(@CompareMyDataCaseInsensitive);
300- SortedArray.Add(TMyData.Create('Mars'));
301- SortedArray.Add(TMyData.Create('Earth'));
302- SortedArray.Add(TMyData.Create('Venus'));
303-
304- // access items via index
305- for i:=0 to SortedArray.Count-1 do
306- writeln(i,': ',TMyData(SortedArray[i]).Name);
307-
308- // access nodes via GetNodeAtIndex
309- for i:=0 to SortedArray.Count-1 do
310- writeln(i,': ',TMyData(SortedArray.GetNodeAtIndex(i).Data).Name);
311-
312- // get the index of a node
313- i:=2;
314- Node:=SortedArray.GetNodeAtIndex(i);
315- writeln(i,'=',SortedArray.NodeToIndex(Node));
316-
317- SortedArray.FreeAndClear; // free nodes and objects
318- SortedArray.Free; // free the tree
319- end;
270+ AvgLvlTree;
271+type
272+ TMyData = class
273+ public
274+ Name: string;
275+ constructor Create(aName: string);
276+ end;
277+
278+constructor TMyData.Create(aName: string);
279+begin
280+ Name:=aName;
281+end;
282+
283+function CompareMyDataCaseInsensitive(Data1, Data2: Pointer): integer;
284+begin
285+ Result:=AnsiCompareText(TMyData(Data1).Name,TMyData(Data2).Name);
286+end;
287+
288+var
289+ SortedArray: TIndexedAVLTree;
290+ Node: TIndexedAVLTreeNode;
291+begin
292+ // create
293+ SortedArray:=TIndexedAVLTree.Create(@CompareMyDataCaseInsensitive);
294+ SortedArray.Add(TMyData.Create('Mars'));
295+ SortedArray.Add(TMyData.Create('Earth'));
296+ SortedArray.Add(TMyData.Create('Venus'));
297+
298+ // access items via index
299+ for i:=0 to SortedArray.Count-1 do
300+ writeln(i,': ',TMyData(SortedArray[i]).Name);
301+
302+ // access nodes via GetNodeAtIndex
303+ for i:=0 to SortedArray.Count-1 do
304+ writeln(i,': ',TMyData(SortedArray.GetNodeAtIndex(i).Data).Name);
305+
306+ // get the index of a node
307+ i:=2;
308+ Node:=SortedArray.GetNodeAtIndex(i);
309+ writeln(i,'=',SortedArray.NodeToIndex(Node));
310+
311+ SortedArray.FreeAndClear; // free nodes and objects
312+ SortedArray.Free; // free the tree
313+end;
320314```
321315
322316# See also
323317
324- * [[Data Structures, Containers, Collections]] Alternative data structures
318+- [[Data Structures, Containers, Collections]] Alternative data structures
325319
326320---
327-*From the Free Pascal wiki, page "AVL Tree", as the Internet Archive kept it on 2024-03-04. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*
321+*From the Free Pascal wiki, page "AVL Tree", as it stood on 2022-02-09 after a change by Mark Paley, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*
322+Category: FCL
323+Category: FPC
324+Category: Lazarus

Back to history