Tree Problem

Types of Tree: Any acyclic connected graph is tree

Binary Tree: a tree in which each node has up to two children

Binary Search Tree: a binary Tree in which every node fits a specific ordering property: all left descendants <= n < all right descendants. Duplicate! allow or left or right?

AVL Tree: is a self-balancing binary search tree. AVL trees maintain a more rigid balance than red-black trees. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1). Loop up fast, insert and delete slow due to more rotation

Red Black Tree: a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.(not rigid balanced). Look up slow, insert and delete fast

B tree : a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. B-trees are a good example of a data structure for external memory. It is commonly used in databases and filesystems. B-tree when you're managing more than thousands of items and you're paging them from a disk or some slow storage medium.

Types of Binary Tree

Balanced Tree: left and right subtrees of every node differ in height by no more than 1

Full Tree: a tree in which every node in the tree has either 0 or 2 children. No nodes have only one child.

Complete Tree: (perfect tree except bottom level)every level of tree is fully filled, except for perhaps the last level. Last level is filled left to right.

Perfect Tree: All leaf nodes will be at the same level, and this level has the maximum number of nodes.

Degenerate Tree : each parent node has only one associated child node == linked List

Terminology used in Trees

Leaf: the node has no children

Height of Tree: The height of a tree is the height of its root node.

Height of Node: The height of a node is the number of edges on the longest path between that node and a leaf.

Depth of Node: The depth of a node is the number of edges from the tree's root node to the node.

Level: the number of connections between the node and the root

Edge: The connection between one node and another.

Degree: The number of sub trees of a node.