Mesh Generation
Including coverage of mesh modification tools, evaluation criteria, optimization, and more, this book provides a comprehensive survey of the different algorithms and data structures for triangulation and meshing construction.
TABLE OF CONTENTS Mesh Generation
2.5: One-Dimensional Data Structures
2.5 One-Dimensional Data Structures
One-dimensional data structures for handling (one-dimensional) objects are considered amongst the most fundamental since they are the building blocks on which more involved algorithms and data structures are based. In Section 2.2, we saw how to store unordered objects. In this section, we shall see how to define dictionaries and priority queues. As for the data structures already described, these can easily carry out operations such as "is this element contained in", "insert" or "delete" an element and, moreover, these are more geared to handling requests such as "find the min", "find the max".
Binary Tree
In Section 2.4, we used a Divide-and-Conquer paradigm to search a sorted array. We noticed the running time improvement over the naive algorithm of Section 2.3.
In this section, we do the same in a dynamic context based on a Binary Search Tree (referred to hereafter as BST) that improves the complexity of any searching operation on linked lists. We start with a definition.
Definition 2.1
A binary tree is a data structure whose node contains, in addition to the information field (the value), two pointers; the left and the right children. If the information field obeys some ordering relationship, such a tree is called a Binary Search Tree (BST).
The topmost node is called the root of the tree. A distinction is made between a node that has children, called internal, and a node without children, called terminal or a leaf
Copyright ISTE Ltd 2008 under license agreement with Books24x7
