Tree
🌲

Tree

Tag
Last Edited Time
Dec 20, 2021 08:56 PM
Created
Jan 18, 2021 03:11 PM

Jargon

leaf (leaves)

Node without subtrees
self._subtrees == []

internal value

  • _Nodes is not leaf

children / parent

  • Nodes immediately beneath / above self

descendants / ancestors

  • children / parent 's children / parent recursively
  • 子子孙孙召唤 / 先祖召唤

predecessor / successor

  • predecessor is the maximum value in its left subtree
  • successor is the minimum value in its right subtree

height

  • max length from root to leaf

branching factor

  • number of children at each node
  • 分支系数

arity (binary / 3-ary)

  • max branching factor in the tree
  • 一个tree最多有多少分支, 一个3分支的tree就叫3ary tree

depth / level

  • distance between itself and the root of the tree
  • convention: root at depth 0 (sometimes at 1)

width

  • maximum number of Nodes at a fixed depth

edge

  • the relationship between Nodes
  • 就是连接node的线, 一条线就是一个edge

Pathlength

  • number of edges
  • 一个node下面有多少关系线

full binary tree / complete binary tree

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Tree Traversals

notion image
 
notion image

Binary Search Tree

notion image
 
 
 

Loading Comments...