A complete binary tree must have each level be completely occupied except the last level and have no gaps in the last level (so each node in the last level is as far to the left as it can be). 

Boston University

A tree is an abstract data structure that represents a hierarchical tree. A tree contains a root which is connected to subtrees through linked nodes. The tree data structure is inherently recursive, since a node's subtree is also a tree in and of itself.
A node that has a subtree is the "parent" node of the subtree. The nodes within the subtree of the parent node are called "child" nodes. Child nodes that have the same parent are known as "sibling" nodes.

There are many types of tree data structures. A few of them include:
- Binary Tree (Binary Search Tree)
     1. AVL Tree
     2. Red-Black Tree
     3. Splay Tree
     4. Treap
- B-Tree
- N-ary Tree

Tree

https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html#:~:text=A%20full%20binary%20tree%20(sometimes,as%20far%20left%20as%20possible.

Full and Complete Binary Tree

A binary search tree is a specific type of tree that orders its subtrees based on the value of the node. For every node in the tree, the left sub tree must have a value less than the node (or parent) and the right sub tree must have a value greater than or equal to the node.

Binary Search Tree

A B - tree is a self balancing search tree. They are used to lower the amount of times that a disk is accessed - which is how the data from the tree is read. As a result, the number of keys (or values) in a given node of the tree is maximized to lower the height of a B - Tree.

B - Trees

A N - Ary Tree is a tree data structure where every node does not have more than N children. For example, every node in a 3 - Ary tree has either 0, 1, 2, or 3 children nodes. 

N - Ary Tree

A full binary tree is a binary tree where each node must have either zero or two children. In effect, each node has two children except for the leaf nodes.

Full Binary Tree

A k-d tree (k-dimensional tree) is a space-partitioning binary tree data structure used for organizing points in a k-dimensional space. It is particularly useful for optimizing nearest neighbor searches, significantly improving the prediction time complexity of algorithms like k-nearest neighbors (k-NN) by continuously dividing the vector space using a divide-and-conquer approach. Each internal node represents a vector sub-space, recording a division along the $$r^{th}$$ dimension with a fixed threshold value and containing pointers to its two child nodes. To build the tree, a common approach is to compute the median and variance for each feature, select the feature with the largest variance, and recursively divide the dataset into two subsets based on that feature's median. For nearest neighbor retrieval, the algorithm traverses the tree to find the appropriate branch, drastically reducing the number of distance comparisons needed.

Learn Before

Related

Related