Data Structures: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 20: | Line 20: | ||
[[Trees]] | [[Trees]] | ||
* [[Binary Trees]] | * Tree structures are nonlinear data structures that extend the idea of a linked list node and data pointer organization. | ||
* A tree is a directed acyclic graph consisting of parent nodes and child nodes, such that all nodes have one parent (except the top-level root node). Typically number of children n is fixed. | |||
* Nodes without children are leaf nodes/external nodes. Nodes with one or more children are internal nodes. | |||
* [[Binary Trees]] are a tree structure where each node has a maximum of two children: | |||
** Each node has a maximum of two children | |||
** Each child node is labeled as left or right | |||
* Left precedes right in order of children of a node | |||
** Proper/full - each node has 0 or 2 children | |||
** Improper - one or more nodes have 1 child | |||
* Recursive binary tree definition: | |||
** A node r, called root of T, stores an element | |||
** A binary tree, possibly empty, called left subtree of T | |||
** A binary tree, possibly empty, called right subtree of T | |||
* [[Binary Trees/Python]] | * [[Binary Trees/Python]] | ||
* [[Binary Search Trees]] | * [[Binary Search Trees]] | ||
[[Dictionaries]] | [[Dictionaries]] | ||
Revision as of 23:58, 6 June 2017
List of pages of notes on the wiki related to data structures:
Elementary Data Structures
- array-based data structures, storage, and algorithms
- lower-level structure that can be implemented by many higher-level data structures
- Python has a built-in array-based list() type, everything (including integers) is reference-based - Arrays/Python
- Java has Array type, size must be known at creation time - Arrays/Java
- Can implement a Python list type in Java - see Arrays/Java/PythonList
- Many data structures below can be implemented under the hood as array-based or linked structure based
- Stacks, queues, and deques are important structures for O(1) access to front/back, order in determines order out
- Lists have two main implementations - array-based lists (in Python, this is a natural place to start, due to Python's built-in list type) or object- and link-based (in Java, this is more natural due to the way the language principally focuses on objects).
- Linked Lists can be implemented in either Python or Java - see Linked Lists/Python or Linked Lists/Java
- ArrayLists are a type in Java but are also similar to the array-based list data structure built into Python
- Tree structures are nonlinear data structures that extend the idea of a linked list node and data pointer organization.
- A tree is a directed acyclic graph consisting of parent nodes and child nodes, such that all nodes have one parent (except the top-level root node). Typically number of children n is fixed.
- Nodes without children are leaf nodes/external nodes. Nodes with one or more children are internal nodes.
- Binary Trees are a tree structure where each node has a maximum of two children:
- Each node has a maximum of two children
- Each child node is labeled as left or right
- Left precedes right in order of children of a node
- Proper/full - each node has 0 or 2 children
- Improper - one or more nodes have 1 child
- Recursive binary tree definition:
- A node r, called root of T, stores an element
- A binary tree, possibly empty, called left subtree of T
- A binary tree, possibly empty, called right subtree of T
- Binary Trees/Python
- Binary Search Trees