Sign in Join
Wiki copytemporary

AVL Tree: what changed

Revision 1 to 2. 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+
116# TAVLTree
217
3-Implemented in the FCL unit **avl_tree**. This is the predecessor of TAvgLvlTree.
18+Implemented in the FCL unit **avl_tree**. This is the predecessor of TAvgLvlTree.
419
520# TAvgLvlTree
621
7-Where to get: Unit AvgLvlTree of Lazarus package **LazUtils** of the Lazarus sources.
22+Where to get: Unit AvgLvlTree of Lazarus package **LazUtils** of the Lazarus sources.
823
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:
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:
1025
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.
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.
2237
2338## Creating a tree
2439
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
40+By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects:
41+```
2842uses AvgLvlTree; // in package lazutils
29-
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);
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);
4054```
4155
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
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:
57+```
4558uses AvgLvlTree; // in package lazutils
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;
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;
6982```
7083
7184## Enumerating all items of a tree
7285
7386### Enumerate from lowest to highest
74-
75-``` pascal
87+```
7688var
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;
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;
8496```
8597
86-Notes:
98+Notes:
8799
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.
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.
90102
91103### Enumerate from highest to lowest
92-
93-``` pascal
104+```
94105var
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;
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;
102113```
103114
104115### Delete all nodes that fits a condition
105116
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
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+```
109119var
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;
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;
120130```
121131
122-Note:
132+Note:
123133
124-- TMyData.Flag is just an example property. You can check whatever you want.
134+ * TMyData.Flag is just an example property. You can check whatever you want.
125135
126136## Searching items
127137
128-You can search an item with the same key:
129-
130-``` pascal
138+You can search an item with the same key:
139+```
131140var
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;
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;
139148```
140149
141-**Note:** **Find** will find a node where your compare function returns 0.
142-
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:
150+**Note:** **Find** will find a node where your compare function returns 0.
144151
145-``` pascal
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+```
146154function CompareFilenameWithMyData(Filename, MyData: Pointer): integer;
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;
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;
160168```
161169
162170## Resorting, changing the order
163171
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
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+```
167174type
168- TMyData = class
169- public
170- Name: string;
171- constructor Create(aName: string);
172- end;
173-
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;
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;
208215```
209216
210-Output:
211-
212- sorted case sensitive:
217+Output:
218+```
219+sorted case sensitive:
213220 ABC
214221 Test
215222 abc
216223 test
217224 sorted case insensitive:
218225 ABC
219226 abc
220227 Test
221228 test
229+```
222230
223231# Associative arrays using AVL trees
224232
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:
226-
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
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:
229234
230-Here is an example demonstrating how to use a TStringToStringTree:
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
231237
232-``` pascal
238+Here is an example demonstrating how to use a TStringToStringTree:
239+```
233240uses
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;
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;
262269```
263270
264271# Indexed AVL Tree
265272
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
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+```
269275uses
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;
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;
314320```
315321
316322# See also
317323
318-- [[Data Structures, Containers, Collections]] Alternative data structures
324+ * [[Data Structures, Containers, Collections]] Alternative data structures
319325
320326---
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
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).*

Back to history