Suggest edit — binary search tree

Title

Name

Note

---
title: "binary search tree"
type: concept
related: [Keys, Red Black Tree, Quicksort, Binary Search Tree]
source: https://www.jemoka.com/posts/kbhbinary_search_tree/
confidence: high
status: active
---

constituents Assume keys are distinct.
node: elements in the tree key: each node has a key, which tags the node and is the key being sorted on root: the node with no parents leaves: the nodes with two nil children height: number of edges root to leaf (i.e. if there is a tree root-leaf directly, then the height is 1) Every node has 2, possibly-null, children. Every node has a parent except for the root.
requirements A binary search tree is a binary tree such that ever left descendant of a node has a key less than that node; every right descendant of a node has a key larger than that node.
additional information building a binary tree pick a random node partition list to the left and right and then pick random parts in the left and right You will note this is quicksort. which is true!
extract ordered list via binary search tree def traverse(x): if x is not None: traverse(x.left) print(x.key) traverse(x.right) searching for elements start at the root if your key is less than current node, go left&hellip; otherwise, go right Terminate at NIL/conventionally return the last element you found. This takes O(height), and if balanced is log(n). This is better. We ideally want of a self-balancing search tree, namely a red-black tree.
inserting new elements search (you won&rsquo;t find it), and then insert following the rules at the desired node.
deleting things there are three cases, handle all three, but generally takes a few steps once you find the node
motivation Suppose we have nodes with keys (algorithms). How can we store them?
array / sorted array linked list (i.e. not necessary sorted) What are some basic operations?
INSERT SEARCH DELETE How long would they typically take? For arrays:
INSERT: \(O\qty(n)\) DELETE: \(O\qty(n)\) SEARCH: \(O\qty(\log n)\) Unsorted linked lists:
INSERT: \(O\qty(1)\) SEARCH/DELETE: \(O\qty(n)\) Notice how existing structures have all some \(O\qty(n)\) operations, which is bad. Turns out, binary search trees have the property that all operations (INSERT, SEARCH, DELETE) are all \(O\qty(\log n)\).