Binary search tree (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (ca) 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ů. (cs) في علم الحاسوب، شجرة بحث ثنائية (بالإنجليزية: Binary Search Tree) اختصارًا (BST)، والتي يطلق عليها أيضًا أحيانًا شجرة بحث ثنائية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية: * الشجرة الجزئية اليسرى لعقدة ما تحتوي فقط على عقد مع قيم أقل من قمية العقدة نفسها. * الشجرة الجزئية اليمنى لعقدة ما تحتوي فقط على عقد مع قيم أكبر من قمية العقدة نفسها. * كلتا الشجرتين الجزئيتين اليمنى واليسرى هما شجرتا بحث ثنائيتان. بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية. الميزة الرئيسية لأشجار البحث الثنائيين على بنى بيانات هي أن خوارزميات الترتيب وخوارزميات البحث المتعلقة بالإمكان أن تكون كفؤ جدا. (ar) 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. (en) 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. (de) 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é. (fr) 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. (es) 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 (in) 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. (it) 二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 (ja) 컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다. * 각 노드에 값이 있다. * 값들은 전순서가 있다. * 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. * 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. * 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. (ko) 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. (nl) 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. (pl) 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. (pt) 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). (sv) Двійкове (або Бінарне) дéрево пóшуку (англ. 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 можна лише для збалансованих дерев, які є ефективнішими в алгоритмах пошуку, аніж прості бінарні дерева пошуку).[джерело?] (uk) Двоичное дерево поиска (англ. 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]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого. Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам. Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки. Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы. (ru) 二叉查找树（英語：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1. * 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2. * 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 3. * 任意节点的左、右子树也分别为二叉查找树； 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 二叉查找树的查找过程和类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透過建構一棵二叉查找树变成一个有序序列，建構树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望，最坏退化為偏斜二元樹。對於可能形成偏斜二元樹的問題可以經由樹高改良後的平衡樹將搜尋、插入、刪除的時間複雜度都維持在，如AVL树、红黑树等。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Binary_search_tree.svg?width=300 |
| dbo:wikiPageExternalLink | http://cslibrary.stanford.edu/110/BinaryTrees.html http://nova.umuc.edu/~jarc/idsv/lesson1.html%7Ctitle=Binary https://web.archive.org/web/20140227082917/http:/nova.umuc.edu/~jarc/idsv/lesson1.html%7Curl-status=dead https://mitpress.mit.edu/books/introduction-algorithms-second-edition%7Ctitle=Introduction http://btv.melezinek.cz https://ghostarchive.org/archive/20220130/http:/cslibrary.stanford.edu/110/BinaryTrees.html http://employees.oneonta.edu/zhangs/PowerPointPlatform/resources/samples/binarysearchtree.ppt%7Ctitle=Binary http://ftp.gnu.org/gnu/avl/avl-2.0.3.pdf.gz |
| dbo:wikiPageID | 4320 (xsd:integer) |
| dbo:wikiPageLength | 31093 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124514801 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbr:Rooted_tree dbr:Binary_logarithm dbr:Binary_search_algorithm dbr:Binary_tree dbr:David_Wheeler_(computer_scientist) dbr:Andrew_Colin dbr:Best,_worst_and_average_case dbr:T-tree dbc:Search_trees dbr:Conway_Berners-Lee dbr:Thomas_N._Hibbard dbr:Labeled_data dbr:Optimal_binary_search_tree dbr:Red-black_tree dbr:Andrew_Donald_Booth dbr:Linear_time dbr:MIT_Press dbr:Magnetic_tape dbr:Stanford_University dbr:Computational_complexity_theory dbr:Computer_performance dbr:Computer_science dbr:Priority_queue dbr:B-tree dbr:Time_complexity dbr:Total_order dbr:Treap dbr:Tree_(data_structure) dbr:Tree_sort dbr:Tree_traversal dbr:Data_structure dbr:Join-based_tree_algorithms dbr:Leaf_node dbr:Linked_list dbr:Abstract_data_type dbr:2–3_tree dbr:Georgy_Adelson-Velsky dbr:Iteration dbr:AVL_tree dbc:Binary_trees dbc:Articles_with_example_C++_code dbc:Articles_with_example_Python_(programming_language)_code dbr:While_loop dbr:Red–black_tree dbr:Associative_array dbr:Sorting_algorithm dbr:Splay_tree dbr:Microsoft_PowerPoint dbr:Recursion_(computer_science) dbr:Red-Black_tree dbr:Search_algorithm dbr:Lookup_table dbr:Set_(abstract_data_type) dbr:Directly_proportional dbr:The_Art_of_Computer_Programming dbr:SUNY_Oneonta dbr:University_of_Maryland dbr:Evgenii_Landis dbr:Pseudocode dbr:Self-balancing_binary_search_tree dbr:Inorder_traversal dbr:Search_tree dbr:Singly_linked_list dbr:Set_(computer_science) dbr:Height-balanced_tree dbr:Helper_function dbr:Abstract_data_structures dbr:Leaf_nodes dbr:Priority_queues dbr:Post-order_traversal dbr:AVL_trees dbr:Binary_search dbr:Pre-order_traversal dbr:File:Binary_search_tree.svg dbr:File:Binary_search_tree_deletion_illustration.png |
| dbp:inventedBy | P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard (en) |
| dbp:inventedYear | 1960 (xsd:integer) |
| dbp:name | Binary search tree (en) |
| dbp:type | tree (en) |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:CS-Trees dbt:Cbignore dbt:Cite_book dbt:Cite_web dbt:Colend dbt:Commons_category dbt:DADS dbt:Div_col dbt:Good_article dbt:Main dbt:Main_article dbt:Math dbt:R dbt:Reflist dbt:Rp dbt:See_also dbt:Short_description dbt:Data_structures dbt:Infobox_data_structure |
| dct:subject | dbc:Search_trees dbc:Binary_trees dbc:Articles_with_example_C++_code dbc:Articles_with_example_Python_(programming_language)_code |
| gold:hypernym | dbr:Type |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | 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. (ca) 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é. (fr) 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. (es) 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 (in) 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. (it) 二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 (ja) 컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다. * 각 노드에 값이 있다. * 값들은 전순서가 있다. * 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. * 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. * 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. (ko) 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. (pt) 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). (sv) 二叉查找树（英語：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1. * 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2. * 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 3. * 任意节点的左、右子树也分别为二叉查找树； 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 二叉查找树的查找过程和类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透過建構一棵二叉查找树变成一个有序序列，建構树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望，最坏退化為偏斜二元樹。對於可能形成偏斜二元樹的問題可以經由樹高改良後的平衡樹將搜尋、插入、刪除的時間複雜度都維持在，如AVL树、红黑树等。 (zh) في علم الحاسوب، شجرة بحث ثنائية (بالإنجليزية: Binary Search Tree) اختصارًا (BST)، والتي يطلق عليها أيضًا أحيانًا شجرة بحث ثنائية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية: * الشجرة الجزئية اليسرى لعقدة ما تحتوي فقط على عقد مع قيم أقل من قمية العقدة نفسها. * الشجرة الجزئية اليمنى لعقدة ما تحتوي فقط على عقد مع قيم أكبر من قمية العقدة نفسها. * كلتا الشجرتين الجزئيتين اليمنى واليسرى هما شجرتا بحث ثنائيتان. بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية. (ar) 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. (cs) 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. (de) 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. (en) 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. (pl) 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. (nl) Двоичное дерево поиска (англ. binary search tree, BST) — двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска): * оба поддерева — левое и правое — являются двоичными деревьями поиска; * у всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X; * у всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных самого узла X. Для целей реализации двоичное дерево поиска можно определить так: (ru) Двійкове (або Бінарне) дéрево пóшуку (англ. binary search tree, BST) в інформатиці — двійкове дерево, в якому кожній вершині x зіставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості: * нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x]. * Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x]. Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева. (uk) |
| rdfs:label | Binary search tree (en) شجرة بحث ثنائية (ar) Arbre binari de cerca (ca) Binární vyhledávací strom (cs) Binärer Suchbaum (de) Árbol binario de búsqueda (es) Pohon biner terurut (in) Albero binario di ricerca (it) Arbre binaire de recherche (fr) 二分探索木 (ja) 이진 탐색 트리 (ko) Binaire zoekboom (nl) Binarne drzewo poszukiwań (pl) Árvore binária de busca (pt) Двоичное дерево поиска (ru) Binärt sökträd (sv) Двійкове дерево пошуку (uk) 二元搜尋樹 (zh) |
| rdfs:seeAlso | dbr:Threaded_binary_tree |
| owl:sameAs | freebase:Binary search tree yago-res:Binary search tree wikidata:Binary search tree dbpedia-ar:Binary search tree dbpedia-bg:Binary search tree http://bs.dbpedia.org/resource/Binarno_stablo_pretraživanja dbpedia-ca:Binary search tree dbpedia-cs:Binary search tree dbpedia-da:Binary search tree dbpedia-de:Binary search tree dbpedia-es:Binary search tree dbpedia-fa:Binary search tree dbpedia-fi:Binary search tree dbpedia-fr:Binary search tree dbpedia-he:Binary search tree dbpedia-id:Binary search tree dbpedia-it:Binary search tree dbpedia-ja:Binary search tree dbpedia-ko:Binary search tree dbpedia-lmo:Binary search tree dbpedia-nl:Binary search tree dbpedia-pl:Binary search tree dbpedia-pt:Binary search tree dbpedia-ro:Binary search tree dbpedia-ru:Binary search tree dbpedia-sh:Binary search tree dbpedia-sk:Binary search tree dbpedia-sr:Binary search tree dbpedia-sv:Binary search tree dbpedia-th:Binary search tree dbpedia-tr:Binary search tree dbpedia-uk:Binary search tree dbpedia-vi:Binary search tree dbpedia-zh:Binary search tree https://global.dbpedia.org/id/4oZ7G |
| prov:wasDerivedFrom | wikipedia-en:Binary_search_tree?oldid=1124514801&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Binary_search_tree.svg wiki-commons:Special:FilePath/Binary_search_tree_deletion_illustration.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Binary_search_tree |
| is dbo:wikiPageDisambiguates of | dbr:BST |
| is dbo:wikiPageRedirects of | dbr:Binary_Search_Tree dbr:Ordered_binary_tree dbr:Binary_search_trees |
| is dbo:wikiPageWikiLink of | dbr:Calkin–Wilf_tree dbr:BST dbr:Proxmap_sort dbr:Quicksort dbr:Scapegoat_tree dbr:List_of_acronyms:_B dbr:List_of_data_structures dbr:Priority_search_tree dbr:Binary_Search_Tree dbr:Binary_logarithm dbr:Binary_search_algorithm dbr:Binary_tree dbr:Best,_worst_and_average_case dbr:List_of_graph_theory_topics dbr:Persistent_data_structure dbr:Day–Stout–Warren_algorithm dbr:Double_compare-and-swap dbr:Interval_tree dbr:OSTree dbr:Geometry_of_binary_search_trees dbr:Range_tree dbr:Order_statistic_tree dbr:Pseudo-LRU dbr:Consistent_hashing dbr:Container_(abstract_data_type) dbr:Thomas_N._Hibbard dbr:Optimal_binary_search_tree dbr:WAVL_tree dbr:Bentley–Ottmann_algorithm dbr:Compare-and-swap dbr:John_Iacono dbr:Key-independent_optimality dbr:Ternary_search_tree dbr:Random_binary_tree dbr:B+_tree dbr:B-tree dbr:C++11 dbr:Cecilia_R._Aragon dbr:Threaded_binary_tree dbr:Treap dbr:Tree_(data_structure) dbr:Tree_sort dbr:Tree_traversal dbr:Trie dbr:Distributed_tree_search dbr:Garsia–Wachs_algorithm dbr:Heap_(data_structure) dbr:K-d_tree dbr:Load-link/store-conditional dbr:Potential_method dbr:American_Computer_Science_League dbr:2–3_tree dbr:Erik_Demaine dbr:Euclidean_algorithm dbr:Exponential_tree dbr:Fractal_tree_index dbr:Fortune's_algorithm dbr:Isolation_forest dbr:Kinetic_heater dbr:Tree_structure dbr:Left_rotation dbr:XOR_linked_list dbr:AA_tree dbr:AVL_tree dbr:Abstraction_(computer_science) dbr:Bit-reversal_permutation dbr:SystemVerilog dbr:Ternary_tree dbr:Reconfiguration dbr:Red–black_tree dbr:Relaxed_k-d_tree dbr:Association_list dbr:Associative_array dbr:CC_system dbr:Splay_tree dbr:Huffman_coding dbr:Cartesian_tree dbr:Recursion_(computer_science) dbr:Tree_rotation dbr:Sentinel_node dbr:Z-order_curve dbr:Implicit_data_structure dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Tango_tree dbr:Rotation_distance dbr:Finger_search dbr:Finger_search_tree dbr:Multiple_line_segment_intersection dbr:Multiplicative_binary_search dbr:Self-balancing_binary_search_tree dbr:Stern–Brocot_tree dbr:Right_rotation dbr:Ordered_binary_tree dbr:Tsearch dbr:Binary_search_trees |
| is foaf:primaryTopic of | wikipedia-en:Binary_search_tree |
