1// SPDX-License-Identifier: ISC
2// Copyright (c) 2014-2020 Bitmark Inc.
3// Use of this source code is governed by an ISC
4// license that can be found in the LICENSE file.
5
6package avl
7
8// Search - find a specific item
9func (tree *Tree) Search(key Item) (*Node, int) {
10	return search(key, tree.root, 0)
11}
12
13func search(key Item, tree *Node, index int) (*Node, int) {
14	if nil == tree {
15		return nil, -1
16	}
17
18	switch tree.key.Compare(key) {
19	case +1: // tree.key > key
20		return search(key, tree.left, index)
21	case -1: // tree.key < key
22		return search(key, tree.right, index+tree.leftNodes+1)
23	default:
24		return tree, index + tree.leftNodes
25	}
26}
27