Pontsho
Sehlooho sena se bua ka lifate tsa lipatlisiso tsa binary. Ke sa tsoa etsa sehlooho se buang ka Ha ke le moo ha kea ka ka ela hloko lifate tsa binary, hobane mekhoa ea ho batla, ho kenya le ho hlakola e ne e se ea bohlokoa. Joale ke ile ka etsa qeto ea ho ngola sehlooho se buang ka lifate. Ha re qaleng.
Sefate ke sebopeho sa data se nang le li-node tse kopantsoeng ka mathōko. Re ka re sefate ke nyeoe e khethehileng ea kerafo. Mohlala oa sefate ke ona:
Sena ha se sefate sa ho batla sa binary! Ntho e 'ngoe le e' ngoe e khaotsoe!
Terminology
Motso
Motso oa sefate - ena ke node ea eona e holimo-limo. Ka mohlala, sena ke node A. Sefateng, ke tsela e le 'ngoe feela e ka lebisang ho tloha motsong ho ea ho node leha e le efe! Ha e le hantle, node leha e le efe e ka nkoa e le motso oa subtree e lumellanang le node ena.
Batsoali/litloholo
Li-node tsohle ntle le motso li na le ntlha e le 'ngoe e lebisang sebakeng se seng. Node e kaholimo ho ea hajoale e bitsoa motsoadi node ena. Node e fumanehang ka tlase ho ea hajoale mme e hokahane le eona e bitsoa setloholo node ena. Ha re sebeliseng mohlala. Ha re nke node B, ebe motsoali oa eona e tla ba node A, 'me bana ba eona e be node D, E le F.
Leaf
Node e se nang bana e tla bitsoa lekhasi la sefate. Mohlala, makhasi e tla ba li-node D, E, F, G, I, J, K.
Ena ke mantsoe a motheo. Likhopolo tse ling li tla tšohloa ho ea pele. Kahoo, sefate sa binary ke sefate seo node e 'ngoe le e' ngoe e tla ba le bana ba fetang ba babeli. Joalokaha u nahanne, sefate se tsoang mohlaleng se ke ke sa e-ba binary, hobane li-node B le H li na le bana ba fetang ba babeli. Mona ke mohlala oa sefate sa binary:
Li-node tsa lifate li ka ba le boitsebiso leha e le bofe. Sefate sa lipatlisiso sa binary ke sefate sa binary se nang le thepa e latelang:
- Lifate tse ka ho le letšehali le tse ka ho le letona ke lifate tsa lipatlisiso tsa binary.
- Li-node tsohle tsa subtree e ka letsohong le letšehali la node e hanyetsanang X li na le lintlha tsa bohlokoa tsa data tse ka tlase ho boleng ba senotlolo sa data sa node X ka boeona.
- Li-node tsohle tse ka tlas'a sefate se nepahetseng sa node X li na le lintlha tsa bohlokoa tsa data tse kholo ho feta kapa tse lekanang le boleng ba senotlolo sa data sa node X ka boeona.
Senotlolo - tšobotsi efe kapa efe ea node (mohlala, palo). Ho hlokahala senotlolo e le hore u ka fumana ntho ea sefate eo senotlolo sena se lumellanang le sona. Mohlala oa sefate sa lipatlisiso sa binary:
Pono ea sefate
Ha re ntse re hatela pele, ke tla fana ka likarolo tse ling (mohlomong tse sa fellang) ho ntlafatsa kutloisiso ea hau. Khoutu e felletseng e tla ba qetellong ea sengoloa.
Sefate se na le li-node. Sebopeho sa 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;
}
//...остальные методы узла
}
Node e 'ngoe le e 'ngoe e na le bana ba babeli (ho ka etsahala hore ngoana ea letšehali le/kapa rightChild a be le boleng ba lefeela). Mohlomong u hlokometse hore tabeng ena lintlha tsa nomoro ke data e bolokiloeng node; key - senotlolo sa node.
Re lokisitse lefito, joale ha re bue ka mathata a hatellang ka lifate. Kamora mona, ka lentsoe "sefate" ke tla bolela mohopolo oa sefate sa lipatlisiso sa binary. Sebopeho sa sefate sa binary:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Re hloka feela motso oa sefate e le tšimo ea sehlopha, hobane ho tloha motsong, ho sebelisa mekhoa ea getLeftChild () le getRightChild (), u ka fihla node leha e le efe sefateng.
Algorithms sefateng
Поиск
A re re u na le sefate se entsoeng. Mokhoa oa ho fumana element e nang le senotlolo sa senotlolo? U hloka ho tsamaea ka tatellano ho tloha motsong ho theosa sefate 'me u bapise boleng ba senotlolo le senotlolo sa node e latelang: haeba senotlolo se ka tlase ho senotlolo sa node e latelang, joale u ee ho setloholo se letšehali sa node, haeba e le teng. e kholoanyane, ho ea ho le letona, haeba linotlolo li lekana, node e lakatsehang e fumanoa! Khouto e amanang:
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;
}
Haeba hona joale e fetoha lefeela, joale ho batla ho fihlile qetellong ea sefate (ka tekanyo ea maikutlo, u sebakeng se seng teng sefateng - setloholo sa lekhasi).
Ha re nahaneng ka katleho ea algorithm ea ho batla sefateng se leka-lekaneng (sefate seo li-node li abuoang ho feta kapa ka tlase ho lekana). Joale ts'ebetso ea ho batla e tla ba O(log(n)),' me logarithm ke motheo oa 2. Sheba: haeba ho na le likarolo tsa n sefateng se leka-lekaneng, joale sena se bolela hore ho tla ba le log(n) ho theha maemo a 2 a sefate. 'Me ha u ntse u batla, mohatong o le mong oa potoloho, u theohela boemong bo le bong.
kenya
Haeba u utloisisa moelelo oa ho batla, joale ho utloisisa ho kenya ho ke ke ha e-ba thata ho uena. U hloka feela ho theohela lekhasi la sefate (ho ea ka melao ea ho theoha e hlalositsoeng ho batla) 'me u be setloholo sa eona - ka ho le letšehali kapa ka ho le letona, ho itšetlehile ka senotlolo. Phethahatso:
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;
}
}
}
}
}
Tabeng ena, ho phaella ho node ea hona joale, ho hlokahala hore u boloke boitsebiso bo mabapi le motsoali oa node ea hona joale. Ha hona joale e se e lekana le lefeela, phapang ea motsoali e tla ba le leqephe leo re le hlokang.
Ho hlakile hore bokhoni ba ho kenya bo tla tšoana le ba ho batla - O(log(n)).
Tlosa
Ho tlosa ke ts'ebetso e thata ka ho fetisisa e tla hloka ho etsoa sefateng. Ho hlakile hore pele re tla hloka ho fumana element eo re tlo e hlakola. Empa joale ho thoe’ng? Haeba re ka beha moelelo oa eona ho lefeela, re tla lahleheloa ke tlhahisoleseding mabapi le subtree eo node ena e leng motso. Mekhoa ea ho tlosa lifate e arotsoe ka linyeoe tse tharo.
Taba ea pele. Node e hlakotsoeng ha e na bana
Haeba node e hlakotsoeng e se na bana, joale sena se bolela hore ke lekhasi. Ka hona, o ka seta feela karolo ea leftChild kapa rightChild ea motsoali oa eona hore e se ke ea sebetsa.
Taba ea bobeli. Node e lokelang ho hlakoloa e na le ngoana a le mong
Taba ena le eona ha e thata haholo. A re khutleleng mohlaleng oa rōna. Ha re re re hloka ho hlakola element ka senotlolo 14. Lumellana hore kaha ke setloholo se nepahetseng sa node e nang le senotlolo sa 10, joale leha e le efe ea litloholo tsa eona (tabeng ena e nepahetseng) e tla ba le senotlolo se seholo ho feta 10, kahoo u e ka "khaola" habonolo sefateng, 'me e kopanya motsoali ka ho toba le ngoana oa node e hlakotsoeng, i.e. kopanya node le senotlolo sa 10 ho node ea 13. Boemo bo ne bo tla tšoana haeba ho ne ho hlokahala ho tlosa node eo e leng ngoana ea letšehali oa motsoali oa eona. Nahana ka uena - papiso e tobileng.
Taba ea boraro. Node e na le bana ba babeli
Taba e thata ka ho fetisisa. Ha re shebeng mohlala o mocha.
Batla mohlahlami
Ha re re re hloka ho hlakola node ka senotlolo 25. Re lokela ho beha mang sebakeng sa eona? E mong oa balateli ba hae (litloholo kapa litloholo) e lokela ho ba mohlahlami(ea tla nka sebaka sa node e tlosoa).
Joang ho utloisisa hore na ke mang ea lokelang ho ba mohlahlami? Ka tlhaho, ena ke node sefateng seo senotlolo sa sona e leng sona se seholo ka ho fetisisa ho tloha node e hlakotsoeng. Algorithm e tjena. U hloka ho ea ho setloholo sa eona se nepahetseng (kamehla ho ea ho le letona, hobane ho se ho boletsoe hore senotlolo sa mohlahlami se seholo ho feta senotlolo sa node e hlakotsoeng), ebe u feta ka ketane ea litloholo tse letšehali tsa setloholo sena se nepahetseng. . Ka mohlala, re ne re tla ea node e nang le senotlolo sa 35, ebe re theohela lekhasi ka ketane ea bana ba eona ba letšehali - tabeng ena, ketane ena e na le feela node e nang le senotlolo sa 30. Ha e le hantle, re shebile bakeng sa node e nyenyane ka ho fetisisa sehlopheng sa li-node tse kholo ho feta tseo re li batlang.
Mokhoa oa ho batla oa mohlahlami:
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;
}
Khoutu e felletseng ea mokhoa oa ho hlakola:
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;
}
Ho rarahana ho ka lekanyetsoa ho O(log(n)).
Ho fumana boholo/bonyane sefateng
Ho totobetse mokhoa oa ho fumana bonyane / boholo ba boleng sefateng - o hloka ho tsamaea ka tatellano ho latela ketane ea likarolo tse letšehali / tse nepahetseng tsa sefate, ka ho latellana; ha u fihla lakane, e tla ba bonyane/boholo ba element.
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;
}
Ho rarahana - O(log(n))
Symmetrical bypass
Traversal e etela node ka 'ngoe ea sefate ho etsa ketso e itseng ka eona.
Recursive symmetric traversal algorithm:
- Etsa ketso ho ngoana ea letšehali
- Etsa ketso le uena
- Etsa ketso ho ngoana ea nepahetseng
Khoutu:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
fihlela qeto e
Qetellong! Haeba ha ke e-s'o hlalose letho kapa ke na le litlhaloso, ka kopo li tlohele litlhaloso. Joalokaha ke tšepisitse, ke fana ka khoutu e felletseng.
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());
}
}
}
PES
Phetoho ho O(n)
Ba bangata ba lona ba ka 'na ba hlokomela: ho thoe'ng haeba u etsa hore sefate se se ke sa leka-lekana? Ka mohlala, beha li-node tse nang le linotlolo tse ntseng li eketseha sefateng: 1,2,3,4,5,6 ... Joale sefate se tla batla se tšoana le lenane le amanang. 'Me e, sefate se tla lahleheloa ke sebopeho sa sefate, ka hona, katleho ea ho fihlella ha data. Ho rarahana ha ts'ebetso ea ho batla, ho kenya, le ho hlakola ho tla tšoana le ho hokahana ha lenane: O(n). Ena ke e 'ngoe ea bohlokoa ka ho fetisisa, ka maikutlo a ka, mefokolo ea lifate tsa binary.
Ke basebelisi ba ngolisitsoeng feela ba ka kenyang letsoho phuputsong. ka kopo.
Ha ke so be setsing nako e telele, 'me ke kopa ho tseba hore na ke lihlooho life tseo u ka ratang ho li bona haholoanyane?
-
Mehaho ea Boitsebiso
-
Algorithms (DP, recursion, compression data, joalo-joalo)
-
Tšebeliso ea libopeho tsa data le li-algorithms bophelong ba sebele
-
Ho hlophisa Lisebelisoa tsa Android ho Java
-
Lisebelisoa tsa marang-rang ho Java
Basebelisi ba 2 ba khethile. Mosebedisi a le 1 o hanne.
Mohloli: www.habr.com