# Note

The `wasBinarySearchTreeSearch` function takes as arguments:

• a binary search tree (`BST`) as a flattened list as per binary_trees.
• the root of the binary search tree (`root`)
• the node (`node`) to search for in the binary search tree.

and returns the node in the binary search tree, or the empty string otherwise.

# Code

```// Ord() function, written by Pedro Oval, 2010-05-28
// Inlined by Wizardry and Steamworks
integer Ord(string chr) {
if (chr == "") return 0;
string hex = llEscapeURL(chr);
if (llGetSubString(hex, 0, 0) != "%")
return llBase64ToInteger("AAAA" +
llStringToBase64(llGetSubString(chr, 0, 0)));
integer b = (integer)("0x" + llGetSubString(hex, 1, 2));
if (b < 194 || b > 244) return b;
if (b < 224) return ((b & 0x1F) << 6) |
(integer)("0x" + llGetSubString(hex, 4, 5)) & 0x3F;
if (b < 240) return (b & 0x0F) << 12 +
((integer)("0x" + llGetSubString(hex, 4, 5)) & 0x3F) << 6 +
(integer)("0x" + llGetSubString(hex, 7, 8)) & 0x3F;
return (b & 0x07) << 18 +
((integer)("0x" + llGetSubString(hex, 4, 5)) & 0x3F) << 12 +
((integer)("0x" + llGetSubString(hex, 7, 8)) & 0x3F) << 6 +
(integer)("0x" + llGetSubString(hex, 10, 11)) & 0x3F;
}

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
integer wasOrdCompare(string chra, string chrb) {
// numerical
float fa = (float)chra;
float fb = (float)chrb;
if(fa != 0 && fb != 0) {
if(fa > fb) return 1;
if(fa < fb) return -1;
return 0;
}
// lexical
if(llStringLength(chra) == 0 && llStringLength(chrb) == 0) return 0;
if(llStringLength(chra) && llStringLength(chrb) == 0) return 1;
if(llStringLength(chra) == 0 && llStringLength(chrb)) return -1;
string a = llGetSubString(chra, 0, 0);
chra = llDeleteSubString(chra, 0, 0);
string b = llGetSubString(chrb, 0, 0);
chrb = llDeleteSubString(chrb, 0, 0);
integer oa = Ord(a);
integer ob = Ord(b);
if(oa > ob) return 1;
if(oa < ob) return -1;
return wasOrdCompare(chra, chrb);
}

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeSearch(list BST, string root, string node) {
integer i = llListFindList(BST, (list)root);
string pivotRoot = llList2String(BST, i);
string left = wasBinaryTreeLeft(BST, pivotRoot);
string right = wasBinaryTreeRight(BST, pivotRoot);
integer compare = wasOrdCompare(node, pivotRoot);;
if(compare > 0) {
if(right == "") return "";
return wasBinaryTreeSearch(BST, right, node);
}
if(compare < 0) {
if(left == "") return "";
return wasBinaryTreeSearch(BST, left, node);
}
return pivotRoot;
}```

secondlife/binary_trees/binary_search_trees/search.txt ยท Last modified: 2017/02/22 18:30 (external edit)

For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy, data protection and copyright compliance.