diff options
| author | Matthias Sohn <matthias.sohn@sap.com> | 2021-10-05 04:08:49 +0200 |
|---|---|---|
| committer | Matthias Sohn <matthias.sohn@sap.com> | 2023-01-04 23:51:23 +0100 |
| commit | 70b436b1b2de249c795035ca1c655c34bceaf01f (patch) | |
| tree | 972510444250fade02bf61f682f8cf76d0c369d6 /org.eclipse.jgit.test/META-INF/MANIFEST.MF | |
| parent | 414bfe05ff3c9fbca5767116348a4de1d7b95841 (diff) | |
| download | jgit-70b436b1b2de249c795035ca1c655c34bceaf01f.tar.gz jgit-70b436b1b2de249c795035ca1c655c34bceaf01f.zip | |
Add TernarySearchTree
A ternary search tree is a type of tree where nodes are arranged in a
manner similar to a binary search tree, but with up to three children
rather than the binary tree's limit of two.
Each node of a ternary search tree stores a single character, a
reference to a value object and references to its three children named
equal kid, lo kid and hi kid. The lo kid pointer must point to a node
whose character value is less than the current node. The hi kid pointer
must point to a node whose character is greater than the current
node.[1] The equal kid points to the next character in the word. Each
node in a ternary search tree represents a prefix of the stored strings.
All strings in the middle subtree of a node start with that prefix.
Like other prefix trees, a ternary search tree can be used as an
associative map with the ability for incremental string search. Ternary
search trees are more space efficient compared to standard prefix trees,
at the cost of speed.
They allow efficient prefix search which is important to implement
searching refs by prefix in a RefDatabase.
Searching by prefix returns all keys if the prefix is an empty string.
Bug: 576165
Change-Id: If160df70151a8e1c1bd6716ee4968e4c45b2c7ac
Diffstat (limited to 'org.eclipse.jgit.test/META-INF/MANIFEST.MF')
| -rw-r--r-- | org.eclipse.jgit.test/META-INF/MANIFEST.MF | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF index 23ce1dafa2..df4a39c883 100644 --- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF +++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF @@ -41,6 +41,7 @@ Import-Package: com.googlecode.javaewah;version="[1.1.6,2.0.0)", org.eclipse.jgit.internal.storage.dfs;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.file;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.io;version="[6.5.0,6.6.0)", + org.eclipse.jgit.internal.storage.memory;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.pack;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.reftable;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.transport.connectivity;version="[6.5.0,6.6.0)", |