TREE

Trees are the type of nonlinear data structure. A data structure accessed beginning at the root node. Each node is either a leaf or an internal node. An internal node has one or more child nodes and is called the parent of its child nodes. All children of the same node are siblings. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom. Height of Tree: The maximum distance of any leaf from the root of a tree. If a tree has only one node (the root), the height is zero. The height of a tree is also known as the order. The degree of a node is the number of subtrees associated with that node. For example, the degree of tree T is n. A node of degree zero has no subtrees. Such a node is called a leaf. Binary Tree: A binary tree T is defined as a finite set of elements, called nodes, such that T is empty (called the null tree or empty tree) T contains a distinguished node R called the root of T, and the remaining nodes of T form an ordered pair of disjoint binary tree T1 and T2. If T does contain a root R, than the two trees, T1 and T2 are called respectively the left and right subtrees or R. If T1 is non empty, than its root is called the left successor of R, similarly, if T2 is nonempty, than its root is called the right successor of R. Binary Search Tree: Binary Search tree is a binary tree in which each internal node T stores an element such that the element stored in the left subtree of T are less than or equal to T and elements stored in the right subtree of T are greater than or equal to T. T is called binary-search-tree property. Traversing Binary Trees: There are three standard ways of traversing a binary tree T with root R. These three algorithm are called preorder, inorder and postorder. Preorder: Process the root R. Traverse the left subtree of R in preorder. Traverse the right subtree of R in preorder. Inorder: Traverse the left subtree of R in inorder. Process the root R. Traverse the right subtree of R in inorder. Postorder: Traverse the left subtree of R in postorder. Traverse the right subtree of R in postorder. Process the root R. Breath-first Traversal: The breadth-first traversal of a tree visits the nodes in the order of their depth in the tree. Breadth-first traversal first visits all the nodes at depth zero (i.e., the root), then all the nodes at depth one, and so on. At each depth the nodes are visited from left to right. Depth-first Traversal: Depth-first traversal is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. Height Balanced Tree: A height-balanced tree which is also a binary search tree. It supports membership, insert, and delete operations in time logarithmic in the number of nodes in the tree. self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. AVL Trees: An AVL tree is a self-balancing binary search tree, and it is the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.