Sign in Join
Wiki copytemporary

AVL Tree: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: AVL Tree

OldNewLine
1+# TAVLTree
2+
3+Implemented in the FCL unit **avl_tree**. This is the predecessor of TAvgLvlTree.
4+
5+# TAvgLvlTree
6+
7+Where to get: Unit AvgLvlTree of Lazarus package **LazUtils** of the Lazarus sources.
8+
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:
10+
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.
22+
23+## Creating a tree
24+
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
28+uses 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);
40+```
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
45+uses 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;
69+```
70+
71+## Enumerating all items of a tree
72+
73+### Enumerate from lowest to highest
74+
75+``` pascal
76+var
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;
84+```
85+
86+Notes:
87+
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.
90+
91+### Enumerate from highest to lowest
92+
93+``` pascal
94+var
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;
102+```
103+
104+### Delete all nodes that fits a condition
105+
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
109+var
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+```
121+
122+Note:
123+
124+- TMyData.Flag is just an example property. You can check whatever you want.
125+
126+## Searching items
127+
128+You can search an item with the same key:
129+
130+``` pascal
131+var
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;
139+```
140+
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:
144+
145+``` pascal
146+function 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;
160+```
161+
162+## Resorting, changing the order
163+
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
167+type
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;
208+```
209+
210+Output:
211+
212+ sorted case sensitive:
213+ ABC
214+ Test
215+ abc
216+ test
217+ sorted case insensitive:
218+ ABC
219+ abc
220+ Test
221+ test
222+
223+# Associative arrays using AVL trees
224+
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
229+
230+Here is an example demonstrating how to use a TStringToStringTree:
231+
232+``` pascal
233+uses
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;
262+```
263+
264+# Indexed AVL Tree
265+
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
269+uses
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;
314+```
315+
316+# See also
317+
318+- [[Data Structures, Containers, Collections]] Alternative data structures
319+
320+---
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