12613959
Description
Mind Map by Eithne O'Sullivan, updated more than 1 year ago
|
Created by Eithne O'Sullivan
over 7 years ago
|
|
Binary Search Trees 1
- A tree is an ADT
- Stores elements
hierarchically as nodes:
think family tree
- has a ROOT node and
1 or more
subtrees
- a sub-tree of a node
consists of given node and
all its descendents(nodes
below it)
- ancestors of a node are
all those above
it(parent and parent's
parents etc
- a sub-tree of a node
consists of given node and
all its descendents(nodes
below it)
- each node except ROOT has a parent
- a node may/may
not have children
- a node with NO
children is
called a LEAF
NODE
- a node with NO
children is
called a LEAF
NODE
- is a natural organization
for data (ubiquitous use)
- allows algorithms to
be implemented
much faster than
linear ds
- allows algorithms to
be implemented
much faster than
linear ds
- features
- degree of node is no.
of children it has
- size of tree: number
of nodes in tree
- depth of a tree:
number of links of
longest path
- height of a
tree: no. of
levels
- height of node: no of
links to furthest
descendent
- depth of node:
no of links
from root
- degree of node is no.
of children it has
- Stores elements
hierarchically as nodes:
think family tree
- is an ordered binary tree
- order of children is
important
- used to store
data for quick
retrieval
- the tree structure + method if insertion
reduce search space when looking for an
element
- the tree structure + method if insertion
reduce search space when looking for an
element
- order of children is
important
- binary tree
- DEF- A binary tree is a finite collection of elements, one
of these( if any) is called the root, and the remaining(if
any) are partitioned into subtrees, that consist of
left-subtree, root and right-subtree
- degree of node is 2, 1, 0
- degree of node is 2, 1, 0
- all elements have max of 2 children
- Each node in Java contains: an
element(data), a reference to left child
node,a reference to right child
- maybe empty: no node
- all paths unique from
root to node
- a full of proper bt:
each node 0 or 2
children
- DEF- A binary tree is a finite collection of elements, one
of these( if any) is called the root, and the remaining(if
any) are partitioned into subtrees, that consist of
left-subtree, root and right-subtree
- For each node N, stores an element with a
key value K such that - 1. nodes in the left
subtree are less than K - 2. nodes in right
subtree are greater than K
0 comments
Want to create your own Mind Maps for free with GoConqr? Learn more.