Binary search tree
http://dbpedia.org/resource/Binary_search_tree an entity of type: Thing
En ciències de la computació, un arbre binari de cerca (BST, de l'anglès Binary Search Tree) és un tipus particular d'arbre binari que presenta una estructura de dades en forma d'arbre.
rdf:langString
En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
rdf:langString
Un árbol binario de búsqueda también llamado BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.
rdf:langString
Dalam ilmu komputer, sebuah pohon biner terurut (binary search tree atau BST) adalah sebuah pohon biner struktur data yang memiliki sifat-sifat sebagai berikut:
* Setiap simpul memiliki sebuah nilai.
* Sebuah ditentukan dalam nilai ini.
* Sub pohon kiri dari sebuah simpul hanya memuat nilai lebih kecil dari nilai simpul.
* Sub pohon kanan dari sebuah simpul hanya memuat nilai lebih besar atau sama dengan nilai dari simpul.
* l
*
* s
rdf:langString
Un albero binario di ricerca (meglio noto come BST, dall'inglese Binary Search Tree), in informatica, è un particolare tipo di struttura dati. Permette di effettuare in maniera efficiente operazioni come: ricerca, inserimento e cancellazione di elementi.
rdf:langString
二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。
rdf:langString
컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.
* 각 노드에 값이 있다.
* 값들은 전순서가 있다.
* 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
* 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
* 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
rdf:langString
Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação). O objetivo desta árvore é estruturar os dados de forma a permitir busca binária.
rdf:langString
Ett binärt sökträd är ett binärträd (dvs varje nod har högst två barn) med följande egenskaper:
* varje nod har ett värde.
* det högra delträdet till en nod innehåller bara värden som är högre än värdet i noden.
* det vänstra delträdet till en nod innehåller bara värden som är lägre än värdet i noden. Binära sökträd är användbara eftersom det finns effektiva sökalgoritmer som kan användas på dem. I genomsnitt är algoritmen av ordning Θ(log n) och i värsta fall Θ(n).
rdf:langString
二叉查找树（英語：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1.
* 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2.
* 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 3.
* 任意节点的左、右子树也分别为二叉查找树； 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 二叉查找树的查找过程和类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透過建構一棵二叉查找树变成一个有序序列，建構树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望，最坏退化為偏斜二元樹。對於可能形成偏斜二元樹的問題可以經由樹高改良後的平衡樹將搜尋、插入、刪除的時間複雜度都維持在，如AVL树、红黑树等。
rdf:langString
في علم الحاسوب، شجرة بحث ثنائية (بالإنجليزية: Binary Search Tree) اختصارًا (BST)، والتي يطلق عليها أيضًا أحيانًا شجرة بحث ثنائية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية:
* الشجرة الجزئية اليسرى لعقدة ما تحتوي فقط على عقد مع قيم أقل من قمية العقدة نفسها.
* الشجرة الجزئية اليمنى لعقدة ما تحتوي فقط على عقد مع قيم أكبر من قمية العقدة نفسها.
* كلتا الشجرتين الجزئيتين اليمنى واليسرى هما شجرتا بحث ثنائيتان. بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية.
rdf:langString
Binární vyhledávací strom (BST – z angl. Binary Search Tree) je datová struktura založená na binárním stromu, v němž jsou jednotlivé prvky (uzly) uspořádány tak, aby v tomto stromu bylo možné rychle vyhledávat danou hodnotu. To zajišťují tyto vlastnosti:
* Jedná se o binární strom, každý uzel tedy má nanejvýš dva potomky – levého a pravého.
* Každému uzlu je přiřazen určitý klíč. Podle hodnot těchto klíčů jsou uzly uspořádány.
* Levý podstrom uzlu obsahuje pouze klíče menší než je klíč tohoto uzlu.
* Pravý podstrom uzlu obsahuje pouze klíče větší než je klíč tohoto uzlu.
rdf:langString
In der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch Binary Search Tree), ist ein binärer Baum, bei dem die Knoten „Schlüssel“ tragen, und die Schlüssel des linken Teilbaums eines Knotens nur kleiner (oder gleich) und die des rechten Teilbaums nur größer (oder gleich) als der Schlüssel des Knotens selbst sind.
rdf:langString
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree. Binary search trees can be used to implement abstract data types such as dynamic sets, lookup tables and priority queues, and used in sorting algorithms such as tree sort.
rdf:langString
Binarne drzewo poszukiwań (ang. Binary Search Tree, BST) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach mniejszych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości kluczy posortowanych niemalejąco.
rdf:langString
Een binaire zoekboom is een binaire boom met eigenschappen die ervoor zorgen dat een waarde snel gevonden kan worden. In een binaire zoekboom verwijst elke knoop naar maximaal twee andere knopen. Verder heeft elke knoop in de boom de eigenschap dat alle waarden in de linker subboom kleiner of gelijk zijn dan de waarde in de knoop en alle waarden in de rechtersubboom groter of gelijk dan de waarde in de knoop.
rdf:langString
Двоичное дерево поиска (англ. binary search tree, BST) — двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
* оба поддерева — левое и правое — являются двоичными деревьями поиска;
* у всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X;
* у всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных самого узла X. Для целей реализации двоичное дерево поиска можно определить так:
rdf:langString
Двійкове (або Бінарне) дéрево пóшуку (англ. binary search tree, BST) в інформатиці — двійкове дерево, в якому кожній вершині x зіставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:
* нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].
* Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x]. Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева.
rdf:langString
rdf:langString
Binary search tree
rdf:langString
شجرة بحث ثنائية
rdf:langString
Arbre binari de cerca
rdf:langString
Binární vyhledávací strom
rdf:langString
Binärer Suchbaum
rdf:langString
Árbol binario de búsqueda
rdf:langString
Pohon biner terurut
rdf:langString
Albero binario di ricerca
rdf:langString
Arbre binaire de recherche
rdf:langString
二分探索木
rdf:langString
이진 탐색 트리
rdf:langString
Binaire zoekboom
rdf:langString
Binarne drzewo poszukiwań
rdf:langString
Árvore binária de busca
rdf:langString
Двоичное дерево поиска
rdf:langString
Binärt sökträd
rdf:langString
Двійкове дерево пошуку
rdf:langString
二元搜尋樹
rdf:langString
Binary search tree
xsd:integer
4320
xsd:integer
1124514801
rdf:langString
tree
rdf:langString
En ciències de la computació, un arbre binari de cerca (BST, de l'anglès Binary Search Tree) és un tipus particular d'arbre binari que presenta una estructura de dades en forma d'arbre.
rdf:langString
Binární vyhledávací strom (BST – z angl. Binary Search Tree) je datová struktura založená na binárním stromu, v němž jsou jednotlivé prvky (uzly) uspořádány tak, aby v tomto stromu bylo možné rychle vyhledávat danou hodnotu. To zajišťují tyto vlastnosti:
* Jedná se o binární strom, každý uzel tedy má nanejvýš dva potomky – levého a pravého.
* Každému uzlu je přiřazen určitý klíč. Podle hodnot těchto klíčů jsou uzly uspořádány.
* Levý podstrom uzlu obsahuje pouze klíče menší než je klíč tohoto uzlu.
* Pravý podstrom uzlu obsahuje pouze klíče větší než je klíč tohoto uzlu. Hlavní výhodou binárních vyhledávacích stromů je vysoká efektivita vyhledávání hodnot v nich, byť proti hašovací tabulce je pomalejší. Lze je využít při dobré implementaci také k efektivnímu řazení hodnot – in-order průchod binárním vyhledávacím stromem vydá seznam uložených hodnot uspořádaný podle velikosti. Ale důležitější jsou na tom postavené a průběžné udržování uspořádaných klíčů, protože řadit na místě, tj. efektivněji, umí spousta jiných algoritmů. Binární vyhledávací stromy jsou zásadní datovou strukturou při konstrukci daleko abstraktnějších datových struktur jako jsou množiny, multimnožiny a asociativní pole. Pokud BST neumožňuje duplicity hodnot, pak se jedná o strom s unikátními hodnotami, stejně jako matematická množina. Stromy bez duplicit využívají ostrou nerovnost, tedy hodnoty uzlů levého podstromu jsou menší než je hodnota uzlu a pravý podstrom obsahuje pouze hodnoty větší než je hodnota uzlu. Pokud BST umožňuje duplicity hodnot, pak představuje multimnožinu. Tento typ stromu využívá neostrou nerovnost. Všechny hodnoty uzlů v levém podstromu uzlu jsou menší než je hodnota uzlu, ale všechny hodnoty v pravém podstromu jsou buď větší, nebo shodné s hodnotou uzlu. Uložení duplicitních hodnot právě v pravém podstromu není povinné. Stejně tak je lze uchovávat i v levém podstromu. Lze též užít neostrou nerovnost v obou podstromech, což usnadní vyvážení stromu obsahujícího mnoho duplicit, ale utrpí efektivita vyhledávání. Strom se mnohem častěji než na množiny a multimnožiny používá pro asociativní paměť (nepřesně asociativní pole), kde se podle klíče hledá přidružená hodnota. (včetně nebinárních) mají mnoho implementačních variant (majících vlastní jména a články) případně i s lepšími vlastnostmi. Na druhé straně pro asociativní pole se dají použít i jiné . BST Vyhledávací stromy slouží jako ideový základ pro konstrukci složitějších , konkrétně pro složené klíče a dotazy s částečně zadanými klíči. Složitost operací je, zjednodušeně řečeno, při dobré implementaci logaritmická a obecně lineární vzhledem k počtu reprezentovaných prvků.
rdf:langString
في علم الحاسوب، شجرة بحث ثنائية (بالإنجليزية: Binary Search Tree) اختصارًا (BST)، والتي يطلق عليها أيضًا أحيانًا شجرة بحث ثنائية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية:
* الشجرة الجزئية اليسرى لعقدة ما تحتوي فقط على عقد مع قيم أقل من قمية العقدة نفسها.
* الشجرة الجزئية اليمنى لعقدة ما تحتوي فقط على عقد مع قيم أكبر من قمية العقدة نفسها.
* كلتا الشجرتين الجزئيتين اليمنى واليسرى هما شجرتا بحث ثنائيتان. بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية. الميزة الرئيسية لأشجار البحث الثنائيين على بنى بيانات هي أن خوارزميات الترتيب وخوارزميات البحث المتعلقة بالإمكان أن تكون كفؤ جدا.
rdf:langString
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree. Binary search trees allow binary search for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to Conway Berners-Lee and David Wheeler. The performance of a binary search tree is dependent on the order of insertion of the nodes into the tree since arbitrary insertions may lead to degeneracy; several variations of the binary search tree can be built with guaranteed worst-case performance. The basic operations include: search, traversal, insert and delete. BSTs with guaranteed worst-case complexities perform better than an unsorted array, which would require linear search time. The complexity analysis of BST shows that, on average, the insert, delete and search takes for nodes. In the worst case, they degrade to that of a singly linked list: . To address the boundless increase of the tree height with arbitrary insertions and deletions, self-balancing variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm. AVL trees were the first self-balancing binary search trees, invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis. Binary search trees can be used to implement abstract data types such as dynamic sets, lookup tables and priority queues, and used in sorting algorithms such as tree sort.
rdf:langString
In der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch Binary Search Tree), ist ein binärer Baum, bei dem die Knoten „Schlüssel“ tragen, und die Schlüssel des linken Teilbaums eines Knotens nur kleiner (oder gleich) und die des rechten Teilbaums nur größer (oder gleich) als der Schlüssel des Knotens selbst sind. Was die Begriffe „kleiner gleich“ und „größer gleich“ bedeuten, ist völlig dem Anwender überlassen; sie müssen nur eine Totalordnung (genauer: eine totale Quasiordnung ) etablieren. Am flexibelsten wird die Ordnungsrelation durch eine vom Anwender zur Verfügung zu stellende realisiert. Auch ob es sich um ein einziges Schlüsselfeld oder eine Kombination von Feldern handelt, ist Sache des Anwenders; ferner ob Duplikate (unterschiedliche Elemente, die beim Vergleich aber nicht als „ungleich“ herauskommen) zulässig sein sollen oder nicht. Über Suchfunktionen für diesen Fall . Ein in-order-Durchlauf durch einen binären Suchbaum ist äquivalent zum Wandern durch eine sortierte Liste (bei im Wesentlichen gleichem Laufzeitverhalten). Mit anderen Worten: ein binärer Suchbaum bietet ggf. wesentlich mehr Funktionalität (zum Beispiel Durchlauf in der Gegenrichtung und/oder einen „direkten Zugriff“ mit potentiell logarithmischem Laufzeitverhalten – erzielt durch das Prinzip „Teile und herrsche“, das auf der Fernwirkung des Transitivitätsgesetzes beruht) bei einem gleichen oder nur unwesentlich höheren Speicherbedarf.
rdf:langString
En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
rdf:langString
Un árbol binario de búsqueda también llamado BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.
rdf:langString
Dalam ilmu komputer, sebuah pohon biner terurut (binary search tree atau BST) adalah sebuah pohon biner struktur data yang memiliki sifat-sifat sebagai berikut:
* Setiap simpul memiliki sebuah nilai.
* Sebuah ditentukan dalam nilai ini.
* Sub pohon kiri dari sebuah simpul hanya memuat nilai lebih kecil dari nilai simpul.
* Sub pohon kanan dari sebuah simpul hanya memuat nilai lebih besar atau sama dengan nilai dari simpul.
* l
*
* s
rdf:langString
Un albero binario di ricerca (meglio noto come BST, dall'inglese Binary Search Tree), in informatica, è un particolare tipo di struttura dati. Permette di effettuare in maniera efficiente operazioni come: ricerca, inserimento e cancellazione di elementi.
rdf:langString
二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。
rdf:langString
컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.
* 각 노드에 값이 있다.
* 값들은 전순서가 있다.
* 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
* 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
* 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
rdf:langString
Een binaire zoekboom is een binaire boom met eigenschappen die ervoor zorgen dat een waarde snel gevonden kan worden. In een binaire zoekboom verwijst elke knoop naar maximaal twee andere knopen. Verder heeft elke knoop in de boom de eigenschap dat alle waarden in de linker subboom kleiner of gelijk zijn dan de waarde in de knoop en alle waarden in de rechtersubboom groter of gelijk dan de waarde in de knoop. Om efficiënt te kunnen zoeken dient de boom ook gebalanceerd te zijn; dit wil zeggen dat de subbomen van een knoop zo veel mogelijk even diep zijn. Bij een scheefgegroeide boom (niet gebalanceerde boom) is de tijdwinst voor bewerkingen kleiner dan een gebalanceerde boom aangezien er (veel) meer waarden in knopen bekeken moet worden om te weten of een waarde in de boom te vinden is.
rdf:langString
Binarne drzewo poszukiwań (ang. Binary Search Tree, BST) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach mniejszych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Koszt wykonania podstawowych operacji w drzewie BST (wstawienie, wyszukanie, usunięcie węzła) jest proporcjonalny do wysokości drzewa ponieważ operacje wykonywane są wzdłuż drzewa. Fakt ten w notacji Landaua zapisuje się Jeżeli drzewo jest zrównoważone, to jego wysokość bliska jest logarytmowi dwójkowemu liczby węzłów zatem dla drzewa o węzłach optymistyczny koszt każdej z podstawowych operacji wynosi Z drugiej strony drzewo skrajnie niezrównoważone ma wysokość porównywalną z liczbą węzłów (w skrajnym przypadku drzewa zdegenerowanego do listy wartości te są równe: ), z tego powodu koszt pesymistyczny wzrasta do Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości kluczy posortowanych niemalejąco. Binarne drzewa wyszukiwań często stosuje się w zadaniach, w których wymagane jest względnie szybkie sortowanie lub wyszukiwanie elementów, na przykład różnego rodzaju słowniki, kolejki priorytetowe.
rdf:langString
Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação). O objetivo desta árvore é estruturar os dados de forma a permitir busca binária.
rdf:langString
Ett binärt sökträd är ett binärträd (dvs varje nod har högst två barn) med följande egenskaper:
* varje nod har ett värde.
* det högra delträdet till en nod innehåller bara värden som är högre än värdet i noden.
* det vänstra delträdet till en nod innehåller bara värden som är lägre än värdet i noden. Binära sökträd är användbara eftersom det finns effektiva sökalgoritmer som kan användas på dem. I genomsnitt är algoritmen av ordning Θ(log n) och i värsta fall Θ(n).
rdf:langString
Двійкове (або Бінарне) дéрево пóшуку (англ. binary search tree, BST) в інформатиці — двійкове дерево, в якому кожній вершині x зіставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:
* нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].
* Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x]. Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева. Представляється таке дерево вузлами наступного вигляду: *Node = (element, key, left, right, parent).Доступ до дерева T здійснюється за допомогою посилання root. Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n — розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h — висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими в алгоритмах пошуку, аніж прості бінарні дерева пошуку).[джерело?]
rdf:langString
Двоичное дерево поиска (англ. binary search tree, BST) — двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
* оба поддерева — левое и правое — являются двоичными деревьями поиска;
* у всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X;
* у всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных самого узла X. Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше. Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако это касается реализации, а не природы двоичного дерева поиска. Для целей реализации двоичное дерево поиска можно определить так:
* Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.
* Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
* Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого. Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам. Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки. Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы.
rdf:langString
二叉查找树（英語：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1.
* 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2.
* 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 3.
* 任意节点的左、右子树也分别为二叉查找树； 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 二叉查找树的查找过程和类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透過建構一棵二叉查找树变成一个有序序列，建構树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望，最坏退化為偏斜二元樹。對於可能形成偏斜二元樹的問題可以經由樹高改良後的平衡樹將搜尋、插入、刪除的時間複雜度都維持在，如AVL树、红黑树等。
rdf:langString
P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard
xsd:integer
1960
xsd:nonNegativeInteger
31093
