binary search && tree

22. Binary Search && Tree

22.1 Binary Search

22.1.1 Recursive code implementation

22.1.2 Time Complexity

• Optimal - O(1)
• Worst - O(logn)

22.2 Tree

22.2.1 Features

• Each node has 0 or more child nodes
• A node without a parent is called a root node
• Each non-root node has one and only one parent
• In addition to the root node, each child node can be divided into multiple subtrees that do not want to intersect

22.2.2 Related Terms

• The degree of a node
  The number of child nodes a node contains is called the degree of the node
• Degree of the tree
  In a tree, the degree of the largest node is called the degree of the tree
• Leaf nodes (terminal nodes)
  Nodes with degree 0
• Parent Node (Parent Node)
  If a node has child nodes, this node is called the parent node of its child nodes
• Child node (child node)
  The root node of the subtree contained in a node is called the child node of the node
• Sibling nodes
  Nodes with the same parent are called siblings
• The hierarchy of nodes
  Starting from the definition of the root node, the root is the first level, and so on
• The height or depth of the tree
  The maximum level of nodes in the tree
• Cousin Nodes
  Nodes whose parent nodes are in the same layer are cousins ​​of each other
• Ancestors of the node
  From the root to all nodes on the branch that this node goes through
• Descendants
  Any node in the subtree rooted at a node is called the descendant of the node
• Forest
  A collection of m(m >= 0) disjoint trees is called a forest

22.2.3 Types

• Ordered tree
  • Hoffman Tree
  • B-tree
  • Binary tree
    • Complete binary tree
    • Full binary tree
    • Non-complete binary tree
    • Balanced binary tree AVL tree
    • sorted binary tree BST tree - including empty tree
• Unordered tree

22.2.4 Binary tree storage

• Sequential storage
• Chain Storage

22.2.5 Application Scenario

Database Index

22.2.6 Binary Tree

• Nature

  

• Traverse

  • Breadth first
    • Find the shortest path
  • depth first
    • Preorder - root left and right
    • Middle order - left root right
    • Postorder - left and right roots