Prelude
ʻO kēia ʻatikala e pili ana i nā kumulāʻau huli binary. Ua kākau wau i kahi ʻatikala e pili ana Ma laila ʻaʻole au i nānā pono i nā kumulāʻau binary, no ka mea, ʻaʻole pili nā ʻano o ka ʻimi, hoʻokomo, holoi ʻana. I kēia manawa ua hoʻoholo wau e kākau i kahi ʻatikala e pili ana i nā lāʻau. E hoʻomaka paha mākou.
ʻO ka lāʻau kahi hoʻolālā ʻikepili i loaʻa nā node i hoʻopili ʻia e nā ʻaoʻao. Hiki iā mākou ke ʻōlelo he kumu kūikawā o ka pakuhi. Eia kekahi kumu lāʻau:
ʻAʻole kēia he lāʻau huli binary! Aia nā mea a pau ma lalo o ka ʻoki!
Kau'ōlelo
Hua
Aʻa lāʻau ʻo ia ka piko o luna. I ka laʻana, ʻo kēia ka node A. I ka lāʻau, hoʻokahi wale nō ala e hiki ke alakaʻi mai ke kumu a i kekahi node ʻē aʻe! ʻO ka ʻoiaʻiʻo, hiki ke noʻonoʻo ʻia ke kumu o ka subtree e pili ana i kēia node.
Nā mākua/nā keiki
Hoʻokahi ʻaoʻao pololei nā ʻaoʻao a pau koe ke kumu e piʻi ai i kahi node ʻē aʻe. Ua kapa ʻia ka node ma luna o ka node o kēia manawa makua keia node. Ua kapa ʻia kahi node ma lalo o kēia manawa a pili pū me ia mamo keia node. E lawe kākou i kekahi laʻana. E lawe i ka node B, a laila ʻo kona makua ka node A, a ʻo kāna mau keiki he mau node D, E, a me F.
Palapala
Ua kapa ʻia ka node ʻaʻohe keiki he lau o ka lāʻau. I ka laʻana, ʻo nā nodes D, E, F, G, I, J, K he lau.
ʻO kēia ka huaʻōlelo kumu. E kūkākūkā ʻia nā manaʻo ʻē aʻe ma hope. No laila, ʻo ka lāʻau binary he lāʻau i loaʻa i kēlā me kēia node ʻaʻole ʻoi aku ma mua o ʻelua keiki. E like me kāu i manaʻo ai, ʻaʻole he binary ka lāʻau mai ka laʻana, no ka mea, ʻoi aku ka nui o nā keiki B a me H i ʻelua mau keiki. Eia kekahi laʻana o ka lāʻau binary:
Hiki i nā nodes o ka lāʻau ke loaʻa kekahi ʻike. ʻO ka lāʻau huli binary he lāʻau binary nona nā waiwai penei:
- ʻO nā ʻaoʻao hema a me nā ʻaoʻao ʻākau he mau kumu ʻimi binary.
- ʻO nā node āpau o ka subtree hema o kahi node X i loaʻa nā waiwai kī ʻikepili ma mua o ka waiwai kī data o ka node X ponoʻī.
- Loaʻa i nā node āpau o ka subtree ʻākau o ka node X i nā waiwai kī ʻikepili i ʻoi aku ka nui a i ʻole like me ka waiwai o ke kī data o ka node X ponoʻī.
Kaomi - kekahi ʻano o ka node (no ka laʻana, he helu). Pono ke kī i mea e hiki ai ke ʻimi i ke kumu o ka lāʻau i pili ai kēia kī. Laʻana kumu lāʻau huli binary:
ʻike lāʻau
I koʻu hele ʻana, e hoʻokomo wau i kekahi mau ʻāpana code (ʻaʻole paha) i mea e hoʻomaikaʻi ai i kou ʻike. Aia ke code piha ma ka hope o ka ʻatikala.
Hoʻokumu ʻia ka lāʻau i nā node. Hoʻolālā node:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
He ʻelua keiki ko kēlā me kēia node (he mea ʻole paha nā keiki leftChild a/a i ʻole nā keiki rightChild). Ua maopopo paha iā ʻoe ma kēia hihia ʻo ka ʻikepili helu ka ʻikepili i mālama ʻia ma ka node; kī - kī node.
Ua noʻonoʻo mākou i ke kaula, i kēia manawa e kamaʻilio e pili ana i nā pilikia koʻikoʻi e pili ana i nā kumulāʻau. Ma hope aku, ʻo ka huaʻōlelo "lāʻau" ke ʻano o ka manaʻo o kahi kumu lāʻau huli binary. Nā kumu lāʻau binary:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Ma ke ʻano he kahua papa, pono mākou i ke kumu o ka lāʻau, no ka mea, mai ke kumu, me ka hoʻohana ʻana i nā ala getLeftChild () a me getRightChild (), hiki iā ʻoe ke kiʻi i kekahi node o ka lāʻau.
Nā Algorithm lāʻau
Поиск
E ʻōlelo kākou he lāʻau i kūkulu ʻia. Pehea e ʻike ai i ka mea me ke kī kī? Pono ʻoe e neʻe i ke kumu mai ke kumu i lalo o ka lāʻau a hoʻohālikelike i ka waiwai o ke kī me ke kī o ka node aʻe: inā ʻoi aku ke kī ma mua o ke kī o ka node aʻe, a laila e hele i ka mamo hema o ka node, inā ʻoi aku - i ka ʻākau, inā like nā kī - loaʻa ka node i makemake ʻia! Code pili:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Inā lilo kēia manawa i mea ʻole, a laila ua hiki ka ʻike i ka hopena o ka lāʻau (ma kahi pae manaʻo, aia ʻoe i kahi wahi ʻole i ka lāʻau - he keiki o ka lau).
E noʻonoʻo i ka maikaʻi o ka hulina algorithm ma kahi kumulāʻau kaulike (kahi lāʻau kahi e puʻunaue like ʻia ai nā nodes). A laila, ʻo O(log(n)) ka pono o ka huli ʻana, a me ka logarithm kumu 2. E nānā: inā he n mau mea i loko o ka lāʻau kaulike, ʻo ia hoʻi he log(n) kumu 2 pae o ka lāʻau. A i ka huli ʻana, no hoʻokahi ʻanuʻu o ka pōʻai, iho ʻoe i lalo i hoʻokahi pae.
hookomo
Inā ua ʻike ʻoe i ke ʻano o ka huli ʻana, a laila ʻaʻole paʻakikī iā ʻoe ke hoʻomaopopo i ka hoʻokomo. Pono ʻoe e iho i lalo i ka lau o ka lāʻau (e like me nā lula o ka iho i wehewehe ʻia ma ka ʻimi) a lilo i kāna mamo - hema a ʻākau paha, ma muli o ke kī. Hoʻokō:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
I kēia hihia, ma waho aʻe o ka node o kēia manawa, pono e mālama i ka ʻike e pili ana i ka makua o ka node o kēia manawa. Ke lilo kēia manawa i mea ʻole, e loaʻa i ka helu makua ka pepa a mākou e pono ai.
E like nō ka pono o ka hoʻokomo ʻana me ka huli ʻana - O(log(n)).
Hoʻopau
ʻO ka holoi ʻana ka hana paʻakikī loa e pono ai ke hana me kahi lāʻau. Ua maopopo ka mea mua e pono e ʻimi i ka mea a mākou e wehe ai. Akā, pehea? Inā hoʻonoho wale mākou i kāna kuhikuhi i ka null, a laila e nalowale mākou i ka ʻike e pili ana i ka subtree nona ke kumu o kēia node. Hoʻokaʻawale ʻia nā ʻano hana hoʻopau lāʻau i ʻekolu mau hihia.
Ka hihia mua. ʻAʻohe keiki o ka node e wehe ʻia.
Inā ʻaʻohe keiki o ka node e holoi ʻia, ʻo ia hoʻi, he lau ia. No laila, hiki iā ʻoe ke hoʻonohonoho i ka leftChild a i ʻole rightChild kahua o kona makua i null.
Ka hihia lua. Hoʻokahi keiki i ka node e wehe ʻia
ʻAʻole paʻakikī loa kēia hihia. E hoʻi kāua i kā mākou laʻana. Inā pono mākou e holoi i kahi mea me ke kī 14. E ʻae mai ʻoiai ʻo ia ke keiki pono o kahi node me ke kī 10, a laila e loaʻa i kekahi o kāna mau mamo (ma kēia hihia, ʻo ka mea ʻākau) ke kī nui ma mua o 10, no laila ʻoe. hiki iā ia ke "ʻoki" maʻalahi mai ka lāʻau, a hoʻopili pololei i ka makua i ke keiki o ka node i holoi ʻia, ʻo ia. e hoʻohui i ka node me ke kī 10 i ka node 13. E like nō ke kūlana inā pono mākou e holoi i kahi puʻupuʻu ke keiki hema a kona makua. E noʻonoʻo iā ʻoe iho - he hoʻohālikelike pololei.
hihia ʻekolu. ʻElua keiki a Node
ʻO ka hihia paʻakikī loa. E nānā kākou i kekahi laʻana hou.
Huli i mea pani
E ʻōlelo kākou he pono e wehe i ka node me ke kī 25. ʻO wai kā kākou e hoʻonoho ai ma kona wahi? Pono e lilo kekahi o kāna mau ukali (mau mamo a mamo paha). hope(ka mea nana e pani i kahi o ka node i weheia).
Pehea ʻoe e ʻike ai ʻo wai ka mea e pani ai? Ma keʻanoʻike,ʻo ia ka node i loko o ka lāʻau nona ke kī nui loa mai ka node e weheʻia. Penei ka algorithm. Pono ʻoe e hele i kāna keiki ʻākau (mau i ka ʻākau, no ka mea, ua ʻōlelo ʻia ua ʻoi aku ke kī o ka mea pani ma mua o ke kī o ka node i holoi ʻia), a laila e hele i ke kaulahao o nā keiki hema o kēia ʻākau. keiki. I ka laʻana, pono mākou e hele i ka node me ke kī 35, a laila e iho i lalo i ke kaulahao o kāna mau keiki hema i ka lau - i kēia hihia, aia kēia kaulahao i ka node me ke kī 30. ʻO ka ʻōlelo pololei, ke ʻimi nei mākou. ʻo ka puʻupuʻu liʻiliʻi loa i loko o ka pūʻulu o nā node ʻoi aku ka nui ma mua o ka node i makemake ʻia.
Code kaʻina hulina hope:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
ʻO ke code piha o ke ʻano holoi:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Hiki ke hoʻopili ʻia ka paʻakikī iā O(log(n)).
Ke ʻimi nei i ka palena kiʻekiʻe / liʻiliʻi i loko o kahi lāʻau
ʻIke loa, pehea e ʻike ai i ka waiwai liʻiliʻi / kiʻekiʻe loa i ka lāʻau - pono ʻoe e hele i ke kaulahao o nā mea hema / ʻākau o ka lāʻau, kēlā me kēia; ke hiki ʻoe i ka lau, ʻo ia ka mea haʻahaʻa/kiʻekiʻe.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Paʻakikī - O(log(n))
ʻO ke ala ʻālikelike
He mākaʻikaʻi ʻo Traversal i kēlā me kēia node o ka lāʻau i mea e hana ai me ia.
Algorithm kaʻahele symmetric recursive:
- Hana i kahi hana ma ke keiki hema
- E hana me ʻoe iho
- Hana i kahi hana ma ke keiki pono
Kuhikuhi:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
hopena
ʻO ka hope loa! Inā ʻaʻole wau i wehewehe i kekahi mea a i ʻole nā manaʻo, a laila ke kali nei au i nā ʻōlelo. E like me ka mea i hoʻohiki ʻia, eia ke code piha.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
Hoʻohaʻahaʻa i ka O(n)
Ua ʻike paha ka nui o ʻoukou: pehea inā e hoʻolilo ʻoe i ka lāʻau i mea kaulike ʻole? No ka laʻana, e hoʻokomo i nā nodes i ka lāʻau me nā kī hoʻonui: 1,2,3,4,5,6... A laila e hoʻomanaʻo ʻia ka lāʻau i kahi papa inoa pili. A ʻae, e nalowale ka lāʻau i kona ʻano kumulāʻau, a no laila ka pono o ka ʻike ʻikepili. ʻO ka paʻakikī o ka ʻimi, hoʻokomo ʻana, a me ka holoi ʻana e like me ka papa inoa i hoʻopili ʻia: O(n). ʻO kēia kekahi o nā mea nui loa, i koʻu manaʻo, nā hemahema o nā lāʻau binary.
Hiki i nā mea hoʻohana i hoʻopaʻa inoa ʻia ke komo i ka noiʻi. , e 'oluʻolu.
ʻAʻole wau i hele ma Habré no ka manawa lōʻihi, a makemake wau e ʻike i nā ʻatikala e pili ana i nā kumuhana āu e makemake ai e ʻike hou aku?
-
Nā Kūlana ʻikepili
-
Algorithms (DP, recursion, hōʻemi ʻikepili, etc.)
-
Ka hoʻohana ʻana i nā ʻikepili a me nā algorithm i ke ola maoli
-
Hoʻolālā i nā polokalamu Android ma Java
-
Hoʻopololei Pūnaewele Pūnaewele Java
2 mea hoʻohana i koho. 1 mea hoʻohana i hōʻole.
Puna: www.habr.com